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

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

2、和邻接表，掌握图的构造、深度优先遍历、广度优先遍历算法实验题目与要求1. 每位同学按下述要*现相应算法：根据从键盘输入的数据创立图图的存储构造可采用邻接矩阵或邻接表，并对图进展深度优先搜索和广度优先搜索1问题描述：在主程序中提供以下菜单：1图的建立2深度优先遍历图3广度优先遍历图0完毕2实验要求：图的存储可采用邻接表或邻接矩阵；定义以下过程：CreateGraph(): 按从键盘的数据建立图DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图3实验提示: 图的存储可采用邻接表或邻接矩阵； 图存储数据类型定义邻接表存储 # define MA*_VERTE*_NUM 8 /

3、顶点最大个数typedef struct Arode int adjve*; struct Arode *ne*tarc; int weight; /边的权Arode; /表结点# define Verte*Type int /顶点元素类型typedef struct VNode int degree,indegree; /顶点的度，入度 Verte*Type data; Arode *firstarc; Vnode /*头结点*/; typedef struct Vnode verticesMA*_VERTE*_NUM; int ve*num,arum;/顶点的实际数，边的实际数ALGrap

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

5、括如下主要内容：数据构造定义图是由定点集合及定点间的关系集合组成的一种数据构造，其形式化定义为Graph = V，E其中，V = *|*个数据对象是定点的有限非空集合；E = *,y|*,yVPath(*,y)是顶点之间关系的有限集合，叫做便集。集合E中的Path*,y表示顶点*和顶点y之间有一条直接连线，即*,y表示一条边，它是有方向的。算法设计思路简介算法描述：可以用自然语言、伪代码或流程图等方式1、图的深度优先搜索：在访问图中*一起始点V后，由V出发，访问它的任一邻接顶点w1;再从w1；出发，访问与w1邻接但还没有访问过得顶点w2；然后再从w2出发，进展类似的访问，,如此进展下去，直至到

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

7、出发，访问它们还未访问过的邻接点，如此做下去，直到图中所有顶点都被访问过为止。2、1将没有前驱入度为零的顶点进栈。2从栈中退出栈顶元素输出，并把该顶点引出的所有弧删去，即把它的各个邻接点的入度减1，同时将当前已输出的顶点个数加1.3将新的入度为零的顶点再进栈。4重复2、2两步，直到栈为空为止。此时或者已经输出前部顶点，或者剩下的顶点中没有入度为零的顶点。3、设置一个n*n的矩阵Ak，其中除对角线元素为0外，其他元素A(k)ij表示顶点i到顶点j的路径长度，k表示运算步骤。开场时k = -1,A(-1)ij = arcsij,即A为图的邻接矩阵。以后逐步尝试在原路径中参加其他顶点作为中间点，如果

8、增加中间点顶点后，得到的路径比原来的路径短，则以此新路径代替原来路径，修改矩阵元素。具体做法为：第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的最短路径的长度。算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决方法等1、2、3、算法时间复杂度分析1、深度优先遍历：On*n.广度优先遍历：On*n.2、On+e.3、O(n*n

9、*n).四、收获与体会不想说什么，这章的程序太难了，每次一想起来数据构造还没做就烦，前两个题根本上一天能做一道题，第三题也就是骗骗OJ，实际上还有个小BUG，等有空再写个真正符合题意的程序吧。五、源代码清单1、#includeusingnamespace std;#define INFINITY INT_MA*#define MA*_VERTE*_NUM 20/typedef enum DG,DN,AG,ANGraphKind;typedefint Elemtype;typedefstruct QueueNodeElemtype data;struct QueueNode *ne*t;Queu

10、eNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-ne*t = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-re

11、ar)returntrue;elsereturnfalse;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-ne*t = NULL;Q-rear-ne*t = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-ne*t;*e = te

12、mp-data;Q-front-ne*t = temp-ne*t;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(QueueList *Q)QueueNode *temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-ne*t != NULL)temp = temp-ne*t;cout data endl;typedefstruct Arc int adj;Arc,AdjMatri*MA*_VERTE*_NUMMA*_VERTE*_NUM;typedefstruct i

13、nt verte*MA*_VERTE*_NUM;AdjMatri* arcs;int ve*num,arum;/GraphKind kind;Graph;void CreateAG(Graph &G,int n,int m)int i,j;G.ve*num = n;G.arum = m;for(i = 0;i n;i+)G.verte*i = i + 1;for(i = 0;i n;i+)for(j = 0;j n;j+)G.arcsij.adj = 0;for(int k = 0;k i j;G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = 1;bool visit

14、edMA*_VERTE*_NUM;int count = 0;void DFS(Graph G,int v)visitedv-1 = true;count+;cout v;if(count G.ve*num)cout ;for(int i = v;i G.ve*num;i+)if(G.arcsv-1i.adj != 0 & !visitedi)DFS(G,G.verte*i);void DFSTraverse(Graph G)int v = 0;for(v = 0;v G.ve*num;v+)visitedv = false;v = 1;/遍历入口点DFS(G,v);void BFS(Grap

15、h G)int i,j;int k = 0;int v = 0;int u = 0;for(v = 0;v G.ve*num;v+)visitedv = false;QueueList *queue;queue = CreateQueue();v = 1;EnQueue(queue,v);visitedv-1 = true;while(!QueueEmpty(queue)DeQueue(queue,&u);k+;cout u;if(k G.ve*num)cout ;for(int i = u;i n m;CreateAG(G1,n,m);DFSTraverse(G1);cout endl;BF

16、S(G1);return 0;2、#includeusingnamespace std;#define INFINITY INT_MA*#define MA*_VERTE*_NUM 20typedefint Elemtype;typedefstruct QueueNodeElemtype data;struct QueueNode *ne*t;QueueNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueList *Q;QueueNode *p;Q

17、 = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-ne*t = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)returntrue;elsereturnfalse;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueN

18、ode);p-data = element;p-ne*t = NULL;Q-rear-ne*t = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-ne*t;*e = temp-data;Q-front-ne*t = temp-ne*t;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(QueueList *Q)QueueNode

19、*temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-ne*t != NULL)temp = temp-ne*t;cout data endl;typedefstruct Arode int adjve*;struct Arode *ne*tarc;Arode;typedefstruct VNode int data;Arode *firstarc;VNode,AdjListMA*_VERTE*_NUM;typedefstruct AdjList verte*;int ve*num,arum;/GraphKind kind;Graph;void Cr

20、eateDN(Graph &G,int e,int n)int i,j;G.ve*num = n;G.arum = e;for(i = 0;i n;i+)G.verte*i.data = i+1;G.verte*i.firstarc = NULL;for(int k = 0;k i j;Arode *s,*p;s = (Arode*)malloc(sizeof(Arode);s-adjve* = j-1;s-ne*tarc = NULL;if(G.verte*i-1.firstarc = NULL)G.verte*i-1.firstarc = s;elsep = G.verte*i-1.fir

21、starc;while(p -ne*tarc!= NULL)p =p-ne*tarc;p-ne*tarc = s;void FindInDegree(Graph G,int indegree)int i;Arode *p;for(i = 0;i G.ve*num;i+)indegreei = 0;for(i = 0;i adjve*+;p = p-ne*tarc;void TopologicalSort(Graph G)int i,k,count,indegreeMA*_VERTE*_NUM;bool visitedMA*_VERTE*_NUM;for(i = 0;i G.ve*num;i+)

22、visitedi = false;Arode *p;count = 0;FindInDegree(G,indegree);while(count G.ve*num)for(i = 0;i G.ve*num;i+)if(indegreei = 0 & visitedi = false)cout G.verte*i.data;if(count G.ve*num-1)cout ne*tarc)k = p-adjve*;indegreek-;break;int main()int n;/节点数int m;/关系数cin n m;Graph G1;CreateDN(G1,m,n);Topological

23、Sort(G1);return 0;3、#includeusingnamespace std;#define INFINITY 1000#define MA*_VERTE*_NUM 20typedefint Elemtype;typedefint Elemtype;typedefstruct QueueNodeElemtype data;struct QueueNode *ne*t;QueueNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueLi

24、st *Q;QueueNode *p;Q = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-ne*t = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)returntrue;elsereturnfalse;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)

25、malloc(sizeof(QueueNode);p-data = element;p-ne*t = NULL;Q-rear-ne*t = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-ne*t;*e = temp-data;Q-front-ne*t = temp-ne*t;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(Que

26、ueList *Q)QueueNode *temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-ne*t != NULL)temp = temp-ne*t;cout data endl;typedefstruct Arc int adj;Arc,AdjMatri*MA*_VERTE*_NUMMA*_VERTE*_NUM;typedefstruct int verte*MA*_VERTE*_NUM;AdjMatri* arcs;int ve*num,arum;/GraphKind kind;Graph;void CreateAN(Graph &G,int

27、 n,int m)int i,j;int w = 0;G.ve*num = n;G.arum = m;for(i = 0;i n;i+) G.verte*i = i+1;for(i = 0;i n;i+)for(j = 0;j n;j+)G.arcsij.adj = INFINITY;for(int k = 0;k 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,int n,int m)int i,j;int ma* = 0;int AMA*_VERTE*_NUMMA*

28、_VERTE*_NUM;int pathMA*_VERTE*_NUMMA*_VERTE*_NUM;for(i = 0;i n;i+)for(j = 0;j n;j+)Aij = G.arcsij.adj;if(Aij INFINITY) 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 = n-1 & sum 20)cout sum;e*it(0);elsecontinue;for(int k = 0;k n;k+)for(i = 0;i n;i+)for(j = 0;j n