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

实验报告学院（系）名称：计算机与通讯工程学院姓名**学号********专业计算机科学与技术班级2015级*班实验项目实验四：图的深度优先与广度优先遍历课程名称数据结构与算法课程代码0661013实验时间2017年5月12日第5-6节实验地址7-216查核特点考勤违标准实验过程程序运转回答以下问题实验报告纪状况成绩功能25分20分15分30分5分5分成绩栏其余批阅建议:○完好评论在实验□功能完美,○正确讲堂中的表○较完好○基本正确□功能不全○有○有查核现，包含实○一般内容验态度、编□有小错○有提示○无○无教师署名：写程序过程○内容很少○没法回答□没法运转等内容等。○无报告一、实验目的理解图的逻辑特点；掌握理解图的两种主要储存结构（毗邻矩阵和毗邻表），掌握图的结构、深度优先遍历、广度优先遍历算法二、实验题目与要求1.每位同学按下述要务实现相应算法：依据从键盘输入的数据创立图（图的储存结构可采纳毗邻矩阵或毗邻表），并对图进行深度优先搜寻和广度优先搜寻1）问题描绘：在主程序中供给以下菜单：1图的成立2深度优先遍历图3广度优先遍历图0结束2）实验要求：图的储存可采纳毗邻表或毗邻矩阵；定义以下过程：CreateGraph( ):按从键盘的数据成立图DFSGrahp( )：深度优先遍历图BFSGrahp( )：广度优先遍历图3）实验提示:图的储存可采纳毗邻表或毗邻矩阵；图储存数据种类定义（毗邻表储存）defineMAX_VERTEX_NUM8拓扑排序：给出一个图的结构，输出其拓扑排序序列（极点序列用空格分开），要求在同样条件下，编号小的极点在前。3．利用最小生成树算法解决通讯网的总造价最低问题1）问题描绘：若在n个城市之间建通讯网络，架设n-1条线路即可。怎样以最低的经济代价建设这个通讯网，是一个网络的最小生成树问题。2）实验要求：利用Prim算法求网的最小生成树。实现提示：通讯线路一旦成立，必定是双向的。所以，结构最小生成树的网必定是无向网。为简单起见，图的极点数不超出10个，网中边的权值设置成小于100。三、实验过程与实验结果应包含以下主要内容：数据结构定义图是由定点会合及定点间的关系会合构成的一种数据结构，其形式化定义为Graph=（V，E）此中，V={x|x∈某个数据对象}是定点的有限非空会合；E={（x,y）|x,y∈V∧Path(x,y)}是极点之间关系的有限会合，叫做便集。会合E中的Path（x,y）表示极点x和极点y之间有一条直接连线，即（x,y）表示一条边，它是有方向的。算法设计思路简介算法描绘：能够用自然语言、伪代码或流程图等方式1、图的深度优先搜寻：在接见图中某一同始点V后，由V出发，接见它的任一毗邻极点w1;再从w1；出发，接见与w1毗邻但还没有接见过得极点w2；而后再从w2出发，进行近似的接见，,这样进行下去，直至抵达全部的毗邻极点都被接见过的极点u为止；接着退回一步，回溯到u的前一个毗邻极点，看它能否还有其余没有被接见过的毗邻点。假如有，则接见此毗邻点，以后再此后顶点出发，进行与前述近似的接见；假如没有，就再退回一步进行搜寻。重复上述过程，直至图中全部和V连通的极点都被接见到。若此时图中另有极点未被接见，则说明该图不是连通图，另选图中一个不曾被接见的极点作开端点，重复上述过程，直至图中全部极点都被接见过为止。图的广度优先搜寻：使用广度优先搜寻（BFS）在接见了开端极点V以后，由V出发，挨次接见V的各个不曾被接见过的毗邻点w1,w2,,wt,而后再次序接见w1,w2,,wt，的全部还为接见过的毗邻点。再从这些极点出发，接见它们还未接见过的毗邻点，，这样做下去，直到图中全部极点都被接见过为止。2、1）将没有前驱（入度为零）的极点进栈。2）从栈中退出栈顶元素输出，并把该极点引出的全部弧删去，即把它的各个毗邻点的入度减1，同时将目前已输出的极点个数加1.3）将新的入度为零的极点再进栈。4）重复（2）、（2）两步，直到栈为空为止。此时或许已经输出前部极点，或许剩下的极点中没有入度为零的极点。3、设置一个n*n的矩阵A（k），此中除对角线元素为0外，其余元素A(k)[i][j]表示极点i到极点j的路径长度，k表示运算步骤。开始时k=-1,A(-1)[i][j]=arcs[i][j],即A为图的毗邻矩阵。此后逐渐试试在原路径中加入其余极点作为中间点，假如增添中间点极点后，获得的路径比本来的路径短，

则以此新路径取代本来路径，

改正矩阵元素。详细做法为：第0步让全部路径上加入中间点

0，去

A[i][j]

与

A[i][0]+A[o][j]

中较小的值作

A[i][j]的新值，达成后获得

A(0)这样进行下去，当第

n-1

步达成后，获得

A(n-1),A(n-1)

即为所求的结果，

A(n-1)[i][j]

表示从

i到

j

路径上的中间极点的序号小于或等于

n-1

的最短路径的长度，即

A(n-1)[i][j]

表示从

i到j

的最短路径的长度。算法的实现和测试结果：包含算法运转时的输入、输出，实验中出现的问题及解决方法等1、2、3、算法时间复杂度剖析1、深度优先遍历：O（n*n）.广度优先遍历：O（n*n）.2、O（n+e）.3、O(n*n*n).四、收获与领会不想说什么，这章的程序太难了，每次一想起来数据结构还没做就烦，前两个题基本上一天能做一道题，第三题也就是骗骗OJ，实质上还有个小BUG，等有空再写个真实切合题意的程序吧。五、源代码清单1、#include<iostream>usingnamespacestd;#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20dj=0;for(intk=0;k<m;k++){cin>>i>>j;[i-1][j-1].adj=[j-1][i-1].adj=1;}}boolvisited[MAX_VERTEX_NUM];intcount=0;voidDFS(GraphG,int{

v)visited[v-1]=count++;cout<<v;if(count<cout<<"";

true;for(inti=v;i<;i++)if[v-1][i].adj!=0&&!visited[i])DFS(G,[i]);}voidDFSTraverse(GraphG){intv=0;for(v=0;v<;v++){visited[v]=

false

;}v=1;dj!=0&&!visited[i]){EnQueue(queue,[i]);visited[i]=true;}}}intmain( ){GraphG1;intm=0;ata=i+1;[i].firstarc=NULL;}for(intk=0;k<e;k++){cin>>i>>j;ArcNode*s,*p;s=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j-1;s->nextarc=NULL;if[i-1].firstarc==NULL){[i-1].firstarc=s;}else{p=[i-1].firstarc;while(p->nextarc!=NULL){p=p->nextarc;}p->nextarc=s;}}}voidFindInDegree(GraphG,intindegree[]){inti;ArcNode*p;for(i=0;i<;i++)indegree[i]=0;for(i=0;i<;i++){p=[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}voidTopologicalSort(GraphG){inti,k,count,indegree[MAX_VERTEX_NUM];boolvisited[MAX_VERTEX_NUM];for(i=0;i<;i++)visited[i]=ArcNode*p;

false;count=0;FindInDegree(G,indegree);while(count<{for(i=0;i<;i++){if(indegree[i]==0&&visited[i]=={

false)cout<<[i].data;if(count<cout<<"";count++;visited[i]=true;for(p=[i].firstarc;p;p=p->nextarc){k=p->adjvex;indegree[k]--;}break;}}}}intmain( ){intn;dj=INFINITY;}for(intk=0;k<m;k++){cin>>i>>j>>w;if[i-1][j-1].adj>w)[i-1][j-1].adj=[j-1][i-1].adj=w;}}voidFloyd(GraphG,intn,intm){inti,j;intmax=0;intA[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];for(i=0;i<n;i++)for(j=0;j<n;j++){A[i][j]=[i][j].adj;if(A[i][j]<INFINITY)path[i][j]=i;elsepath[i][j]=0;}intt;intsum;for(i=0;i<n;i++){t=0;sum=0;for(j=0;j<n;j++)if(A[i][j]<1000){t++;sum=sum+A[i][j];if(t>=n-1&&sum<20){cout<<sum;exit(0);}elsecontinue;}}for(intk=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][k]+A[k][j]<A[i][j]){A[i][j]=A[i][k]+A[k][j];path[i][j]=path[k][j];}dj!=0&&!visited[i])DFS(G,[i]);}voidDFSTraverse(GraphG){intv=0;for(v=