图的遍历操作技巧实验报告.doc

《图的遍历操作技巧实验报告.doc》由会员分享，可在线阅读，更多相关《图的遍历操作技巧实验报告.doc（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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; /顶点表 int edgesMaxVertexNumMaxV

3、ertexNum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数eMGraph; /用邻接矩阵表示的图的类型/=建立邻接矩阵=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(%c,&a); G-vexsi=a; /读入顶点信息，建立顶点表 fo

4、r(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); /输入边（Vi，Vj）的顶点序号 G-edgesij=1; G-edgesji=1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的

5、递归算法=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); /（Vi，Vj）E，且Vj未访问过，故Vj为新出发点void DFS(MGraph *G) int i; for(i=0;in;i+)visitedi=FALSE; /标志向量初始化 for(i=0;in;i+)i

6、f(!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=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 w

7、hile(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(G); /建立邻接矩阵 printf(Print Graph DFS: )

8、; DFS(G); /深度优先遍历 printf(n); printf(Print Graph BFS: ); BFS(G,3); /以序号为3的顶点开始广度优先遍历 printf(n);执行顺序：Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: 01234567Input edges,Creat Adjacency Matrix0 10 21 31 42 52 63 74 75 6Print Graph DFS:01374256Print Graph BFS:317042562 邻接链表作为存储结构程序示例#include

9、stdio.h#includestdlib.h#define MaxVertexNum 50 /定义最大顶点数typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域EdgeNode;typedef struct vnode /顶点表结点 char vertex; /顶点域 EdgeNode *firstedge; /边表头指针VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型typedef struct AdjList adjlist;

10、/邻接表 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); /读入顶点数和边数 scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /建立边表 scanf(%c,&a);G-adjlisti.vertex=a; /读

11、入顶点信息G-adjlisti.firstedge=NULL; /边表置为空表 printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /建立边表 scanf(%d%d,&i,&j); /读入边（Vi，Vj）的顶点对序号s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点s-adjvex=j; /邻接点序号为js-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(siz

12、eof(EdgeNode); s-adjvex=i; /邻接点序号为is-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /将新结点*S插入顶点Vj的边表头部 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(ALGraph *G,int i) /以Vi为出发点对邻接链表表示的图G进行DFS搜索 EdgeNode *p; printf(%c,G-adjlisti.vertex); /访问顶

13、点Vi visitedi=TRUE; /标记Vi已访问 p=G-adjlisti.firstedge; /取Vi边表的头指针 while(p) /依次搜索Vi的邻接点Vj，这里j=p-adjvexif(! visitedp-adjvex) /若Vj尚未被访问 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); /以

14、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+)cqi=-1; /初始化标志向量 printf(%c,G-adjlistk.vertex); /访问源点Vk visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(c

15、qf!=-1) 队列非空则执行i=cqf; f=f+1; /Vi出队p=G-adjlisti.firstedge; /取Vi的边表头指针while(p) /依次搜索Vi的邻接点Vj（令p-adjvex=j） if(!visitedp-adjvex) /若Vj未访问过printf(%c,G-adjlistp-adjvex.vertex); /访问Vjvisitedp-adjvex=TRUE;r=r+1; cqr=p-adjvex; /访问过的Vj入队 p=p-next; /找Vi的下一个邻接点 /endwhile/=主函数=void main() int i; ALGraph *G; G=(AL

16、Graph *)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，9Input Vertex string: 01234567Input edges,Creat Adjacency List0 10 21 31 42 52 63 74 75 6Print Graph DFS:02651473Pr

17、int Graph BFS:37140265五、 修改后的代码1邻接矩阵作为存储结构的程序#includestdio.h#includestdlib.h#define MaxVertexNum 100 /定义最大顶点数typedef struct char vexsMaxVertexNum; /顶点表 int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数eMGraph; /用邻接矩阵表示的图的类型/=建立邻接矩阵=void CreatMGraph(MGraph *G) int i,j,k; char a; pri

18、ntf(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(%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条边，建立邻接矩阵 s

19、canf(%d%d,&i,&j); /输入边（Vi，Vj）的顶点序号 G-edgesij=1; G-edgesji=1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j; printf(%c,G-vexsi); /访问顶点Vi visitedi=TRUE; /置已访

20、问标志 for(j=0;jn;j+) /依次搜索Vi的邻接点if(G-edgesij=1 & ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未访问过，故Vj为新出发点void DFS(MGraph *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(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0

21、,r=0; int cqMaxVertexNum; /定义队列 for(i=0;in;i+)visitedi=FALSE; /标志向量初始化 for(i=0;in;i+)cqi=-1; /队列初始化 printf(%c,G-vexsk); /访问源点Vk visitedk=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);

22、 /访问Vj visitedj=TRUE; r=r+1; cqr=j; /访问过Vj入队 /=main=void main() MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /为图G申请内存空间 CreatMGraph(G); /建立邻接矩阵 printf(Print Graph DFS: ); DFS(G); /深度优先遍历 printf(n); printf(Print Graph BFS: ); BFS(G,3); /以序号为3的顶点开始广度优先遍历 printf(n);2邻接链表作为存储结构程序#includestdio.h#include

23、stdlib.h#define MaxVertexNum 50 /定义最大顶点数typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域EdgeNode;typedef struct vnode /顶点表结点 char vertex; /顶点域 EdgeNode *firstedge; /边表头指针VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型typedef struct AdjList adjlist; /邻接表 int n,e; /

24、图中当前顶点数和边数 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); /读入顶点数和边数 scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /建立边表 scanf(%c,&a);G-adjlisti.vertex=a; /读入顶点信息G-adjlisti

25、.firstedge=NULL; /边表置为空表 printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /建立边表 scanf(%d%d,&i,&j); /读入边（Vi，Vj）的顶点对序号s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点s-adjvex=j; /邻接点序号为js-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode);

26、s-adjvex=i; /邻接点序号为is-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /将新结点*S插入顶点Vj的边表头部 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(ALGraph *G,int i) /以Vi为出发点对邻接链表表示的图G进行DFS搜索 EdgeNode *p; printf(%c,G-adjlisti.vertex); /访问顶点Vi visitedi=TR

27、UE; /标记Vi已访问 p=G-adjlisti.firstedge; /取Vi边表的头指针 while(p) /依次搜索Vi的邻接点Vj，这里j=p-adjvexif(! visitedp-adjvex) /若Vj尚未被访问 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搜索DFS

28、M(G,i);/=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+)cqi=-1; /初始化标志向量 printf(%c,G-adjlistk.vertex); /访问源点Vk visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-

29、1) /队列非空则执行i=cqf; f=f+1; /Vi出队p=G-adjlisti.firstedge; /取Vi的边表头指针while(p) /依次搜索Vi的邻接点Vj（令p-adjvex=j） if(!visitedp-adjvex) /若Vj未访问过printf(%c,G-adjlistp-adjvex.vertex); /访问Vjvisitedp-adjvex=TRUE;r=r+1; cqr=p-adjvex; /访问过的Vj入队 p=p-next; /找Vi的下一个邻接点 /endwhile/=主函数=void main() ALGraph *G; G=(ALGraph *)mal

30、loc(sizeof(ALGraph); CreatALGraph(G); printf(Print Graph DFS: ); DFS(G); printf(n); printf(Print Graph BFS: ); BFS(G,3); printf(n);六、 实验内容1调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。邻接矩阵作为存储结构的运行结果：邻接链表作为存储结构的运行结果：六、实验报告要求画出你所设计的图，写出两种方法的遍历序列。邻接矩阵：V0V1V2V3V4V5V6V7V001100000V110011000V210000110V301000001V410000001V501000010V601000100V70001100V0021V11430V22650V3341V4471V5562V6652V7743深度遍历为：02651473广度遍历为：37140265