数据结构实验四图的应用

华北水利水电学院 数据结构 实验报告20 10 20 11 学年 第 一 学期 2008级 计算机 专业班级： 学号： 姓名： 实验四 图的应用一、 实验目的：1掌握图的存储结构及其构造方法2掌握图的两种遍历算法及其执行过程二、 实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。三、 实验要求：1 各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。2 C/ C+完成算法设计和程序设计并上机调试通过。3 撰写实验报告，提供实验结果和数据。4 写出算法设计小结和心得。四、 程序源代码：第 4 页 共 4 页#includetypedef char vextype;const MAXVER=21;typedef struct listnode int adjvex; listnode* next; listnode;/表结点 typedef struct vextype data; listnode *first;headnode;/头结点typedef struct headnode vexsMAXVER; int vexnum,arcnum; ALgraph;/图void createALgraph(ALgraph &G) int i, s, d; listnode *p,*q; coutG.vexnumG.arcnum; for(i=1;i=G.vexnum;i+) coutn输入第iG.vexsi.data; G.vexsi.first=NULL; /输入第i个结点值并初始化第i个单链表为空 for(i=1; i=G.arcnum; i+) coutn输入第isd;/s为始点，d为终点 p=new listnode; p-adjvex=d; p-next=G.vexss.first; G.vexss.first=p; /将新建的以d为信息的表结点p插入s单链表的头结点后 q=new listnode; q-adjvex=s; q-next=G.vexsd.first; G.vexsd.first=q; /将新建的以s为信息的表结点q插入d单链表的头结点后 int visitedMAXVER;/定义全局数组遍历visitedvoid dfs(ALgraph G, int v)/被遍历的图G采用邻接表作为存储结构，v为出发顶点编号 listnode *p; coutadjvex=0) dfs(G,p-adjvex); /若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfs p=p-next; void dfsTraverse(ALgraph G) int v; /遍历图之前初始化各未访问的顶点 for(v=1; v=G.vexnum; v+) visitedv=0; /从各个未被访问过的顶点开始进行深度遍历 for(v=1;v=G.vexnum;v+) if(visitedv=0) dfs(G,v);void BFS(ALgraph G, int v)/从顶点编号v出发，广度遍历邻接表存储的图G int queueMAXVER, front ,rear; listnode* p; front=rear=0; coutadjvex=0) v=p-adjvex; coutnext; void BFSTraverse(ALgraph G) int v; /遍历G以前，初始化visited数组为0 for(v=1;v=G.vexnum;v+) visitedv=0; for(v=1;v=G.vexnum;v+) if(visitedv=0) BFS(G,v);void main() ALgraph g; createALgraph(g); coutendl深度遍历结果为：; dfsTraverse(g); coutendl广度遍历结果为：; BFSTraverse(g); coutendl;五、 程序运行情况（写出输入数据及运行结果）六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）本次实验是对邻接表和邻接矩阵的应用，使用邻接表为存储结构实现无向连通图的深度优先和广度优先搜索遍历，通过本次实验，我对图的存储结构及其构造方法有了进一步了解，对深度遍历和广度遍历的实现有了更深的认识。