《图的遍历操作实验报告.docx》由会员分享，可在线阅读，更多相关《图的遍历操作实验报告.docx（19页珍藏版）》请在三一办公上搜索。
1、图的遍历操作实验报告图的遍历操作实验报告 实验三、图的遍历操作 一、 目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。 二、 要求 采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。 三、 DFS和BFS 的基本思想 深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被
2、访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。 广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，Vt；再依次访问与V1，V2，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。 四、 示例程序 1 邻接矩阵作为存储结构的程序示例 #includestdio.h #includestdlib.h #define MaxVertexNum 100 /定义最大顶点数 typedef struct char vexsMaxVertexNum
3、; /顶点表 int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数e MGraph; /用邻接矩阵表示的图的类型 /=建立邻接矩阵= void CreatMGraph(MGraph *G) int i,j,k; char a; printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /输入顶点数和边数 scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) scanf(
4、%c,&a); G-vexsi=a; /读入顶点信息，建立顶点表 for(i=0;in;i+) 1 for(j=0;jn;j+) G-edgesij=0; /初始化邻接矩阵 printf(Input edges,Creat Adjacency Matrixn); for(k=0;ke;k+) /读入e条边，建立邻接矩阵 scanf(%d%d,&i,&j); /输入边的顶点序号 G-edgesij=1; G-edgesji=1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量= typedef enumFALSE,TRUE Boolean; Boolean
5、 visitedMaxVertexNum; /=DFS：深度优先遍历的递归算法= void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j; printf(%c,G-vexsi); /访问顶点Vi visitedi=TRUE; /置已访问标志 for(j=0;jn;j+) /依次搜索Vi的邻接点 if(G-edgesij=1 & ! visitedj) DFSM(G,j); /E，且Vj未访问过，故Vj为新出发点 void DFS(MGraph *G) int i; for(i=0;in;i+) visitedi
6、=FALSE; /标志向量初始化 for(i=0;in;i+) if(!visitedi) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索 /=BFS：广度优先遍历= void BFS(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定义队列 for(i=0;in;i+) visitedi=FALSE; /标志向量初始化 for(i=0;in;i+) cqi=-1; /队列初始化 printf(%c,G-vexsk); /访问源点Vk visitedk=TRU
7、E; 2 cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) /队非空则执行 i=cqf; f=f+1; /Vf出队 for(j=0;jn;j+) /依次Vi的邻接点Vj if(G-edgesij=1 & !visitedj) /Vj未访问 printf(%c,G-vexsj); /访问Vj visitedj=TRUE; r=r+1; cqr=j; /访问过Vj入队 /=main= void main int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /为图G申请内存空间 CreatMGraph
8、(G); /建立邻接矩阵 printf(Print Graph DFS: ); DFS(G); /深度优先遍历 printf(n); printf(Print Graph BFS: ); BFS(G,3); /以序号为3的顶点开始广度优先遍历 printf(n); 执行顺序： Input VertexNum(n) and EdgesNum(e): 8，9 V0 Input Vertex string: 01234567 V2 Input edges,Creat Adjacency Matrix V1 0 1 V3 0 2 V6 V4 V5 1 3 1 4 2 5 V7 2 6 3 7 图G的示
9、例 4 7 5 6 Print Graph DFS:01374256 Print Graph BFS:31704256 2 邻接链表作为存储结构程序示例 3 #includestdio.h #includestdlib.h #define MaxVertexNum 50 /定义最大顶点数 typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域 EdgeNode; typedef struct vnode /顶点表结点 char vertex; /顶点域 EdgeNode *firstedge; /边表头指针 Vert
10、exNode; typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型 typedef struct AdjList adjlist; /邻接表 int n,e; /图中当前顶点数和边数 ALGraph; /图类型 /=建立图的邻接表= void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定义边表结点 printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /读入顶点数和边数 scan
11、f(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /建立边表 scanf(%c,&a); G-adjlisti.vertex=a; /读入顶点信息 G-adjlisti.firstedge=NULL; /边表置为空表 printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /建立边表 scanf(%d%d,&i,&j); /读入边的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点 s-adjvex=j; /邻接点序号为j
12、 s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /邻接点序号为i s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /将新结点*S插入顶点Vj的边表头部 4 /=定义标志向量，为全局变量= typedef enumFALSE,TRUE Boolean; Boolean visitedMaxVertexNum; /=DFS：深度优先遍历的递归算
13、法= void DFSM(ALGraph *G,int i) /以Vi为出发点对邻接链表表示的图G进行DFS搜索 EdgeNode *p; printf(%c,G-adjlisti.vertex); /访问顶点Vi visitedi=TRUE; /标记Vi已访问 p=G-adjlisti.firstedge; /取Vi边表的头指针 while(p) /依次搜索Vi的邻接点Vj，这里j=p-adjvex if(! visitedp-adjvex) /若Vj尚未被访问 DFSM(G,p-adjvex); /则以Vj为出发点向纵深搜索 p=p-next; /找Vi的下一个邻接点 void DFS(A
14、LGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; /标志向量初始化 for(i=0;in;i+) if(!visitedi) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索 /=BFS：广度优先遍历= void BFS(ALGraph *G,int k) /以Vk为源点对用邻接链表表示的图G进行广度优先搜索 int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /定义FIFO队列 for(i=0;in;i+) visitedi=FALSE; /标志向量初始化 for(i=0;in;i+
15、) cqi=-1; /初始化标志向量 printf(%c,G-adjlistk.vertex); /访问源点Vk visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 5 while(cqf!=-1) 队列非空则执行 i=cqf; f=f+1; /Vi出队 p=G-adjlisti.firstedge; /取Vi的边表头指针 while(p) /依次搜索Vi的邻接点Vj if(!visitedp-adjvex) /若Vj未访问过 printf(%c,G-adjlistp-adjvex.vertex); /访问Vj visitedp-adjvex=TRU
16、E; r=r+1; cqr=p-adjvex; /访问过的Vj入队 p=p-next; /找Vi的下一个邻接点 /endwhile /=主函数= void main int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatALGraph(G); printf(Print Graph DFS: ); DFS(G); printf(n); printf(Print Graph BFS: ); BFS(G,3); printf(n); 执行顺序： Input VertexNum(n) and EdgesNum(e): 8，9 Inpu
17、t Vertex string: 01234567 Input edges,Creat Adjacency List V0 0 1 0 2 V1 V2 1 3 V3 1 4 V6 V4 V5 2 5 2 6 3 7 4 7 V7 5 6 Print Graph DFS:02651473 Print Graph BFS:37140265 6 图G的示例 五、 修改后的代码 1 邻接矩阵作为存储结构的程序 #includestdio.h #includestdlib.h #define MaxVertexNum 100 /定义最大顶点数 typedef struct char vexsMaxVer
18、texNum; /顶点表 int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数e MGraph; /用邻接矩阵表示的图的类型 /=建立邻接矩阵= void CreatMGraph(MGraph *G) int i,j,k; char a; printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /输入顶点数和边数 scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+)
19、scanf(%c,&a); G-vexsi=a; /读入顶点信息，建立顶点表 for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; /初始化邻接矩阵 printf(Input edges,Creat Adjacency Matrixn); for(k=0;ke;k+) /读入e条边，建立邻接矩阵 scanf(%d%d,&i,&j); /输入边的顶点序号 G-edgesij=1; G-edgesji=1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量= typedef enumFALSE,TRUE Boolean; Boo
20、lean visitedMaxVertexNum; /=DFS：深度优先遍历的递归算法= void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j; printf(%c,G-vexsi); /访问顶点Vi 7 visitedi=TRUE; /置已访问标志 for(j=0;jn;j+) /依次搜索Vi的邻接点 if(G-edgesij=1 & ! visitedj) DFSM(G,j); /E，且Vj未访问过，故Vj为新出发点 void DFS(MGraph *G) int i; for(i=0;in;i+) vi
21、sitedi=FALSE; /标志向量初始化 for(i=0;in;i+) if(!visitedi) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索 /=BFS：广度优先遍历= void BFS(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定义队列 for(i=0;in;i+) visitedi=FALSE; /标志向量初始化 for(i=0;in;i+) cqi=-1; /队列初始化 printf(%c,G-vexsk); /访问源点Vk visite
22、dk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) /队非空则执行 i=cqf; f=f+1; /Vf出队 for(j=0;jn;j+) /依次Vi的邻接点Vj if(G-edgesij=1 & !visitedj) /Vj未访问 printf(%c,G-vexsj); /访问Vj visitedj=TRUE; r=r+1; cqr=j; /访问过Vj入队 /=main= void main MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /为图G申请内存空间 8 CreatMGraph(
23、G); /建立邻接矩阵 printf(Print Graph DFS: ); DFS(G); /深度优先遍历 printf(n); printf(Print Graph BFS: ); BFS(G,3); /以序号为3的顶点开始广度优先遍历 printf(n); 2 邻接链表作为存储结构程序 #includestdio.h #includestdlib.h #define MaxVertexNum 50 /定义最大顶点数 typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域 EdgeNode; typedef st
24、ruct vnode /顶点表结点 char vertex; /顶点域 EdgeNode *firstedge; /边表头指针 VertexNode; typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型 typedef struct AdjList adjlist; /邻接表 int n,e; /图中当前顶点数和边数 ALGraph; /图类型 /=建立图的邻接表= void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定义边表结点 printf(Input Ver
25、texNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /读入顶点数和边数 scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /建立边表 scanf(%c,&a); G-adjlisti.vertex=a; /读入顶点信息 G-adjlisti.firstedge=NULL; /边表置为空表 printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /建立边表 9 scanf(%d%d,&i,&j); /读入边的顶点对
26、序号 s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点 s-adjvex=j; /邻接点序号为j s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /邻接点序号为i s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /将新结点*S插入顶点Vj的边表头部 /=定义标志向量，为全局变量= typedef e
27、numFALSE,TRUE Boolean; Boolean visitedMaxVertexNum; /=DFS：深度优先遍历的递归算法= void DFSM(ALGraph *G,int i) /以Vi为出发点对邻接链表表示的图G进行DFS搜索 EdgeNode *p; printf(%c,G-adjlisti.vertex); /访问顶点Vi visitedi=TRUE; /标记Vi已访问 p=G-adjlisti.firstedge; /取Vi边表的头指针 while(p) /依次搜索Vi的邻接点Vj，这里j=p-adjvex if(! visitedp-adjvex) /若Vj尚未被
28、访问 DFSM(G,p-adjvex); /则以Vj为出发点向纵深搜索 p=p-next; /找Vi的下一个邻接点 void DFS(ALGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; /标志向量初始化 for(i=0;in;i+) if(!visitedi) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索 DFSM(G,i); /=BFS：广度优先遍历= void BFS(ALGraph *G,int k) /以Vk为源点对用邻接链表表示的图G进行广度优先搜索 int i,f=0,r=0; EdgeNode *p; int
29、cqMaxVertexNum; /定义FIFO队列 for(i=0;in;i+) 10 visitedi=FALSE; /标志向量初始化 for(i=0;in;i+) cqi=-1; /初始化标志向量 printf(%c,G-adjlistk.vertex); /访问源点Vk visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) /队列非空则执行 i=cqf; f=f+1; /Vi出队 p=G-adjlisti.firstedge; /取Vi的边表头指针 while(p) /依次搜索Vi的邻接点Vj if(!visited
30、p-adjvex) /若Vj未访问过 printf(%c,G-adjlistp-adjvex.vertex); /访问Vj visitedp-adjvex=TRUE; r=r+1; cqr=p-adjvex; /访问过的Vj入队 p=p-next; /找Vi的下一个邻接点 /endwhile /=主函数= void main ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatALGraph(G); printf(Print Graph DFS: ); DFS(G); printf(n); printf(Print Graph BFS:
31、); BFS(G,3); printf(n); 六、 实验内容 1调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS和BFS的操作。 邻接矩阵作为存储结构的运行结果： 11 邻接链表作为存储结构的运行结果： 六、实验报告要求 画出你所设计的图，写出两种方法的遍历序列。 邻接矩阵： V0 V1 V3 V4 V5 V6 V2 V7 图G的示例 V0 V1 V2 V3 V4 V5 V6 V7 12 V0 0 V1 1 V2 1 V3 0 V4 1 V5 0 V6 0 V7 0 V0 0 V1 1 V2 2 V3 3 V4 4 V5 5 V6 6 V7 7 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 2 4 6 4 7 6 5 4 1 3 5 1 1 2 2 3 0 0 深度遍历为：02651473 广度遍历为：37140265 13
