实验四：图的深度优先与广度优先遍历

1、实验报告学院（系）名称： 计算机与通信工程学院姓名*学号*专业计算机科学与技术班级2015级*班实验项目实验四：图的深度优先与广度优先遍历课程名称数据结构与算法课程代码0661013实验时间2017年5月12日第5-6节实验地点7-216考核 标准实验过程25分程序运行20分回答问题15分实验报告30分特色 功能5分考勤违 纪情况5分成绩成绩 栏其它批改意见：教师签字：考核 内容评价在实验 课堂中的表 现，包括实 验态度、编 写程序过程 等内容等。功能完善，功能不全有小错无法运行O正确o基本正确O有提示o无法回答o完整o较完整o般o内容极少o无报告o有o无o有o无一、实验目的理解图的逻辑特点；

2、掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法二、实验题目与要求1.每位冋学按下述要求实现相应算法：根据从键盘输入的数据创建图（图的存储结构可采用 邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索1）问题描述：在主程序中提供下列菜单：1图的建立2深度优先遍历图3广度优先遍历图0结束2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程：CreateGraph（）:按从键盘的数据建立图 DFSGrahp（）:深度优先遍历图BFSGrahp（）:广度优先遍历图3）实验提示:图的存储可采用邻接表或邻接矩阵；图存储数据类型定义（邻接表存储）#

3、 define MAX_VERTEX_NUM 8顶点最大个数typedef struct ArcNode int adjvex;struct ArcNode *nextarc;int weight; / 边的权 ArcNode; / 表结点 # define VertexType int II 顶点元素类型 typedef struct VNode int degree,indegree; II顶点的度，入度 VertexType data;ArcNode *firstarc; Vnode I* 头结点 *I; typedef structVnode verticesMAX_VERTEX_NU

4、M;int vexnum,arcnum;顶点的实际数，边的实际数 ALGraph;4）注意问题： 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。2.拓扑排序：给出一个图的结构，输出其拓扑排序序列（顶点序列用空格隔开），要求在同等条件下，编号小的顶点在前。3 利用最小生成树算法解决通信网的总造价最低问题1） 问题描述：若在n个城市之间建通信网络，架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。2） 实验要求：利用Prim算法求网的最小生成树。3）实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见，图的顶点

5、数不超过10个，网中边的权值设置成小于100。三、实验过程与实验结果应包括如下主要内容：数据结构定义图是由定点集合及定点间的关系集合组成的一种数据结构，其形式化定义为Graph =（V,E）其中，V = x|x 某个数据对象是定点的有限非空集合； E = （x,y） |x,y V A Path（x,y）是顶点之间关系的有限集合，叫做便集。集合E中的Path （x,y）表示顶点x和顶点y之间有一条直接连线，即（x,y）表示一条边，它是有方向的。算法设计思路简介算法描述：可以用自然语言、伪代码或流程图等方式1、图的深度优先搜索：在访问图中某一起始点V后，由V出发，访问它的任一邻接顶点w1;再从w1

6、;出发，访问与w1邻接但还没有访问过得顶点w2 ;然后再从w2出发，进行类似的访问，,如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止；接着退回一步，回溯到 u的前一个邻接顶点，看它是否还有其他没有被访问过的邻接点。如果有，则访问此邻接点，之后再从 此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程， 直至图中所有和 V连通的顶点都被访问到。若此时图中尚有顶点未被访问，则说明该图不是连通图，另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被 访问过为止。图的广度优先搜索：使用广度优先搜索（BFS）在访问了起始顶点V之后，由V出发，依次

7、访问 V的各个未曾被访问过的邻接点 w1,w2,wt,然后再顺序访问 w1,w2,wt，的所有还为访问过的邻接点。再从这些顶点出发，访问它们还未访问过的邻接点，如此做下去，直到图中所有顶点都被访问过为止。2、（1）将没有前驱（入度为零）的顶点进栈。（2）从栈中退出栈顶元素输出，并把该顶点引出的所有弧删去，即把它的各个邻接点的入度减1,同时将当前已输出的顶点个数加1.（3）将新的入度为零的顶点再进栈。（4）重复（2）、（ 2）两步，直到栈为空为止。此时或者已经输出前部顶点，或者剩下的顶 点中没有入度为零的顶点。3、设置一个n*n的矩阵A（ k ），其中除对角线元素为0夕卜，其他元素 A（k）ij

8、表示顶点i到顶点j的路径长度，k表示运算步骤。开始时k = -1,A（-1）ij = arcsij,即A为图的邻接矩阵。以后逐步尝试在原路径中加入其他顶点作为中间点，如果增加中间点顶点后，得到的路径比 原来的路径短，则以此新路径代替原来路径，修改矩阵元素。具体做法为：第0步让所有路径上加入中间点 0,去Aij与Ai0 + Aoj中较小的值作 Aij的新值，完成后得到 A（0） 如此进行下去，当第n-1步完成后，得到 A（n-1）,A（n-1）即为所求的结果，A（n-1）ij表示从i到j路径上的中间顶点的序号小于或等于n-1的最短路径的长度，即A（n-1）ij表示从i到j的最短路径的长度。算法的

9、实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等1、6 61 21 32 43 44 54 61 2 4 5 6 31 2 3 4 5 6请按任意键继续.C :WI N DOWSsystc m 3 2c md. cxe1 61 22 33 41 55 66 712 3 15 6 712 5 3 6 4 了请按任靈犍继续.C3B C:QVINDOW£syyt(?nn32(:mdcc62 3 4 5 62 3 4 5 6请按仟竜键绅续.”3J C AWIN D 0V/Ssyste m 32c m d >exe7 67 45 44 22 11 31 65 7

10、4 2 1 3 6请按任豈键继续一SB 匚:WI N DOWStyste m i 2c m d. exe5 41 22 33 44 51 2 3 4 5请按任薫憔绽绽.SS C:WINDOWSsystem3cnnd.exe3 66 56 45 14 23 6 4 2 5 l请按任意健继续.31 C AWI IM D O WSsy s te in 3 2c md. exe6 5C 44 34 23 12 56 4 2 3 1 "青按任意腱醴续Sfl C :WI N DOWSsyste m 32c m d .cxe5 41 22 35 44 312 5 4 3请按任意键继续.3、|SB

11、C :WI N DOWStyste m 3 2c m d.«4 41 2 11 3 23 4 3E 4 46请按仟袁锦樂续311 C:WI N DOWSsystem32c md.c4 41 2 11 2 21 3 61 4 714请按ft意健继续.SB C :WI N D OWSsyste m 3 2c md. exc1 2 12 3 23 4 34 5 45 6 53 7 17 4 114诗按任意谴窒换.C AWIN D OWSsyste m 3 2c md. exe4 51 2 92 4 83 4 71 3 63 2 619请按仕意遵继续1 0u请按任意键继续.算法时间复杂度分析

12、1、深度优先遍历：0 (n*n ).广度优先遍历：0 (n*n ).2、0 (n+e).3、O(n*n*n).四、收获与体会不想说什么，这章的程序太难了，每次一想起来数据结构还没做就烦，前两个题基本上一天能做一道题, 第三题也就是骗骗 0J,实际上还有个小 BUG，等有空再写个真正符合题意的程序吧。五、源代码清单1、#in clude<iostream> usingn amespacestd;#defi ne INFINITY INT_MAX#defi ne MAX_VERTEX_NUM 20/typedef e num DG,DN,AG,ANGraphK ind; typedef

13、i nt Elemtype;typedefstruct QueueNodeElemtype data; struct QueueNode *n ext;QueueNode; typedefstruct QueueList QueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue() QueueList *Q;QueueNode *p;Q = (QueueList*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->fron

14、t = Q->rear = p;Q->fro nt->n ext = NULL; return Q;bool QueueEmpty(QueueList *Q)if(Q->fro nt = Q->rear) returntrue;elsereturnfalse;QueueList *En Queue(QueueList *Q, int eleme nt)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear-

15、>n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp; if(!QueueEmpty(Q)Jtemp = Q->fro nt->next;*e = temp->data;Q->fro nt->n ext = temp->next;if (Q->rear = temp)Q->rear = Q->fro nt; free(temp);return Q;void display(QueueList *Q

16、)QueueNode *temp; temp = Q->fro nt; if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext; cout << temp->data << en dl;typedefstruct Arc int adj; Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedefstruct in t vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;/ Gr

17、aphKi nd kind;Graph;void CreateAG(Graph &G, int n,int m)int i,j;G.vex num = n;G.arc num 二 m;for(i = 0;i < n ;i+)G.vertexi = i + 1;for(i = 0;i < n ;i+)for(j = 0;j < n;j+) G.arcsij.adj = 0;for(int k = 0;k < m;k+)cin >> i >> j;G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = 1;bool vis

18、itedMAX_VERTEX_NUM;int count = 0;void DFS(Graph G,i nt v)visitedv-1 = true; coun t+; cout << v;if (count < G.vexnum)cout <<""for(i nt i = v;i < G.vex nu m;i+)if (G.arcsv-1i.adj != 0 && !visitedi) DFS(G,G.verte xi);void DFSTraverse(Graph G)int v = 0;for(v = 0;v <

19、; G.vex nu m;v+) visitedv = false;v = 1;/遍历入口点DFS(G,v);void BFS(Graph G)int i,j;int k = 0;int v = 0;int u = 0;for(v = 0;v < G.vex nu m;v+) visitedv = false;QueueList *queue; queue = CreateQueue();v = 1;En Queue(queue,v); visitedv-1 = true; while(!QueueEmpty(queue) DeQueue(queue，&u);k+;cout &l

20、t;< u;if (k < G.vex num) cout <<""for(i nt i = u;i < G.vex nu m;i+) if(G.arcsu-1i.adj != 0 && !visitedi)En Queue(queue,G.vertexi); visitedi = true;int mai n()Graph G1;int m = 0;/ 边数int n二0;/顶点数cin >> n >> m;CreateAG(G1, n,m); DFSTraverse(G1); cout <<

21、; en dl;BFS(G1); return 0;2、#in clude<iostream> usingn amespacestd;#defi ne INFINITY INT_MAX#defi ne MAX_VERTEX_NUM 20 typedefi nt Elemtype; typedefstruct QueueNode Elemtype data; struct QueueNode *n ext;QueueNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *Cre

22、ateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->front = Q->rear = p;Q->fro nt->n ext = NULL; return Q;bool QueueEmpty(QueueList *Q)if (Q->fro nt 二二 Q->rear)returntrue;elsereturnfalse;QueueList *En Queue(Que

23、ueList *Q, int eleme nt) QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear- >n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp;if(!QueueEmpty(Q)temp = Q->fro nt->next;*e = temp->data;Q-

24、>fro nt->n ext = temp->next;if (Q->rear = temp)Q->rear = Q->fro nt; free(temp);return Q;void display(QueueList *Q)QueueNode *temp; temp = Q->fro nt;if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext;cout << temp->data << en dl; typedefstruct ArcNod

25、e int adjvex;struct ArcNode *n extarc;ArcNode;typedefstruct VNode int data;ArcNode *firstarc;VNode,AdjListMAX VERTEX NUM:typedefstruct AdjList vertex;int vex nu m,arc num;/GraphKi nd kind;Graph;void CreateDN(Graph &G, int ejnt n)int i,j;G.vex num = n;G.arc num 二 e;for(i = 0;i <n ;i+)G.vertexi

26、.data = i+1; G.verte xi .firstarc = NULL;for(i nt k = 0;k < e;k+)cin >> i >> j;ArcNode *s,*p;s = (ArcNode*)malloc( sizeof(ArcNode); s->adjvex = j-1;s->n extarc = NULL;if (G.verte xi-1.firstarc = NULL)G.vertexi-1.firstarc = s;elsep = G.vertexi-1.firstarc; while (p ->n extarc!=

27、 NULL) p =p->n extarc;p->n extarc = s;void Findln Degree(Graph G,i nt in degree)int i;ArcNode *p;for(i = 0;i < G.vex nu m;i+)in degreei = 0;for(i = 0;i < G.vex nu m;i+)p = G.vertexi.firstarc;while(p)in degreep->adjvex+:p = p->n extarc;void TopologicalSort(Graph G)int i,k,count,inde

28、greeMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;for(i = 0;i < G.vex nu m;i+) visitedi = false;ArcNode *p;count = 0;Findln Degree(G,i ndegree); while(co unt < G.vex num) for(i = 0;i < G.vex nu m;i+)if(i ndegreei = 0 && visitedi = false) cout << G.vertexi.data;if (count < G.vex

29、num-1) cout <<""coun t+;visitedi = true;for(p = G.vertexi.firstarc;p;p = p->n extarc) k = p->adjvex;in degreek-; break;int mai n()int n;/节点数int m;/关系数cin >> n >> m;Graph G1;CreateDN(G1,m, n);TopologicalSort(G1); return 0;#in clude<iostream>3、usingn amespacestd

30、; #defi ne INFINITY 1000 #defi ne MAX_VERTEX_NUM 20 typedefi nt Elemtype; typedefi nt Elemtype; typedefstruct QueueNodeElemtype data; struct QueueNode *n ext;QueueNode; typedefstruct QueueList QueueNode *front;QueueNode *rear; QueueList;QueueList *CreateQueue() QueueList *Q;QueueNode *p;Q = (QueueLi

31、st*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->front = Q->rear = p;Q->fro nt->n ext = NULL;return Q;bool QueueEmpty(QueueList *Q) if(Q->fro nt = Q->rear) returntrue;elsereturnfalse;QueueList *En Queue(QueueList *Q, int eleme nt) QueueNode *p;p = (QueueN

32、ode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear- >n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp;if(!QueueEmpty(Q)temp = Q->fro nt->n ext; *e 二 temp->data:Q->fro nt->n ext = temp->next;if (Q->

33、rear = temp) Q->rear = Q->fro nt;free(temp);return Q;void display(QueueList *Q)QueueNode *temp; temp = Q->fro nt; if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext; cout << temp->data << en dl;typedefstruct Arc int adj; Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_N

34、UM; typedefstruct in t vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;/ GraphKi nd kind;Graph;void CreateAN(Graph &G, int n,int m)int i,j;int w = 0;G.vex num = n;G.arc num 二 m;for(i = 0;i < n ;i+)G.vertexi = i+1;for(i = 0;i < n ;i+)for(j = 0;j < n;j+) G.arcsij.adj = INFINIT Y;

35、for(int k = 0;k < m;k+)cin >> i >> j >> w;if (G.arcsi-1j-1.adj > w)G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = w;void Floyd(Graph G,i nt n ,i nt m)int i,j;int max = 0;int AMAX_VERTEX_NUMMAX_VERTEX_NUM;int pathMAX_VERTEX_NUMMAX_VERTEX_NUM; for(i = 0;i < n ;i+)for(j = 0;j < n;j

36、+)Aij = G.arcsij.adj;if(Aij < INFINIT Y) pathij = i; else pathij = 0;int t;int sum;for(i = 0;i < n;i+)t = 0;sum = 0;for(j = 0;j < n;j+) if(Aij < 1000) t+;sum = sum + Aij;if(t >= n-1 && sum < 20)cout << sum; exit(0);elsecon ti nue;for(i nt k = 0;k < n ;k+) for(i = 0

37、;i < n ;i+) for(j = 0;j < n;j+) if(Aik + Akj < Aij) Aij = Aik + Akj; pathij = pathkj;/cout << "处？理 O'a后 '?" << endl;for(i 二 0;i < n:i+)/ for(j = 0;j < n;j+)/if(Aij < INFINIT Y)/cout << Aij << "t"/else/cout << 0 << "t&