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

实验报告学院（系）名称：计算机与通信工程学院姓名* *学号* *专业计算机科学与技术班级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）实验提示: 图的存储可采用邻接表或邻接矩阵； 图存储数据类型定义 （邻接表存储） # define MAX_VERTEX_NUM 8 /顶点最大个数 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; int weight; /边的权 ArcNode; /表结点 # define VertexType int /顶点元素类型 typedef struct VNode int degree,indegree; /顶点的度，入度 VertexType data; ArcNode *firstarc; Vnode /*头结点*/; typedef struct Vnode verticesMAX_VERTEX_NUM; int vexnum,arcnum;/顶点的实际数，边的实际数 ALGraph; 4）注意问题: 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。 2. 拓扑排序：给出一个图的结构，输出其拓扑排序序列（顶点序列用空格隔开），要求在同等 条件下，编号小的顶点在前。 3利用最小生成树算法解决通信网的总造价最低问题 1）问题描述：若在 n 个城市之间建通信网络，架设 n-1 条线路即可。如何以最低的经济代价建 设这个通信网，是一个网络的最小生成树问题。 2）实验要求：利用 Prim 算法求网的最小生成树。 3) 实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。 为简单起见，图的顶点数不超过 10 个，网中边的权值设置成小于 100。三、 实验过程与实验结果 应包括如下主要内容： 数据结构定义 图是由定点集合及定点间的关系集合组成的一种数据结构，其形式化定义为Graph = （V，E）其中，V = x|x某个数据对象是定点的有限非空集合；E = （x,y）|x,yVPath(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)ij表示顶点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的最短路径的长度。 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 1、 2、 3、 算法时间复杂度分析 1、 深度优先遍历：O（n*n）. 广度优先遍历：O（n*n）. 2、 O（n+e）. 3、 O(n*n*n).四、收获与体会不想说什么，这章的程序太难了，每次一想起来数据结构还没做就烦，前两个题基本上一天能做一道题，第三题也就是骗骗OJ，实际上还有个小BUG，等有空再写个真正符合题意的程序吧。五、源代码清单1、#includeusing namespace std;#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20/typedef enum DG,DN,AG,ANGraphKind;typedef int Elemtype;typedef struct QueueNodeElemtype data;struct QueueNode *next;QueueNode;typedef struct 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-next = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)return true;elsereturn false;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-next = NULL;Q-rear-next = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-next;*e = temp-data;Q-front-next = temp-next;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-next != NULL)temp = temp-next;cout data endl;typedef struct Arc int adj;Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct int vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;/GraphKind kind;Graph;void CreateAG(Graph &G,int n,int m)int i,j;G.vexnum = n;G.arcnum = 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 i j;G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = 1;bool visitedMAX_VERTEX_NUM;int count = 0;void DFS(Graph G,int v)visitedv-1 = true;count+;cout v;if(count G.vexnum)cout ;for(int i = v;i G.vexnum;i+)if(G.arcsv-1i.adj != 0 & !visitedi)DFS(G,G.vertexi);void DFSTraverse(Graph G)int v = 0;for(v = 0;v G.vexnum;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.vexnum;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.vexnum)cout ;for(int i = u;i n m;CreateAG(G1,n,m);DFSTraverse(G1);cout endl;BFS(G1);return 0;2、#includeusing namespace std;#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef int Elemtype;typedef struct QueueNodeElemtype data;struct QueueNode *next;QueueNode;typedef struct 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-next = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)return true;elsereturn false;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-next = NULL;Q-rear-next = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-next;*e = temp-data;Q-front-next = temp-next;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-next != NULL)temp = temp-next;cout data endl;typedef struct ArcNode int adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNode int data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertex;int vexnum,arcnum;/GraphKind kind;Graph;void CreateDN(Graph &G,int e,int n)int i,j;G.vexnum = n;G.arcnum = e;for(i = 0;i n;i+)G.vertexi.data = i+1;G.vertexi.firstarc = NULL;for(int k = 0;k i j;ArcNode *s,*p;s = (ArcNode*)malloc(sizeof(ArcNode);s-adjvex = j-1;s-nextarc = NULL;if(G.vertexi-1.firstarc = NULL)G.vertexi-1.firstarc = s;else p = G.vertexi-1.firstarc;while(p -nextarc!= NULL)p =p-nextarc;p-nextarc = s;void FindInDegree(Graph G,int indegree)int i;ArcNode *p;for(i = 0;i G.vexnum;i+)indegreei = 0;for(i = 0;i adjvex+;p = p-nextarc;void TopologicalSort(Graph G)int i,k,count,indegreeMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;for(i = 0;i G.vexnum;i+)visitedi = false;ArcNode *p;count = 0;FindInDegree(G,indegree);while(count G.vexnum)for(i = 0;i G.vexnum;i+)if(indegreei = 0 & visitedi = false)cout G.vertexi.data;if(count G.vexnum-1)cout nextarc)k = p-adjvex;indegreek-;break;int main()int n;/节点数int m;/关系数cin n m;Graph G1;CreateDN(G1,m,n);TopologicalSort(G1);return 0;3、#includeusing namespace std;#define INFINITY 1000#define MAX_VERTEX_NUM 20typedef int Elemtype;typedef int Elemtype;typedef struct QueueNodeElemtype data;struct QueueNode *next;QueueNode;typedef struct 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-next = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)return true;elsereturn false;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-next = NULL;Q-rear-next = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-next;*e = temp-data;Q-front-next = temp-next;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-next != NULL)temp = temp-next;cout data endl;typedef struct Arc int adj;Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct int vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;/GraphKind kind;Graph;void CreateAN(Graph &G,int n,int m)int i,j;int w = 0;G.vexnum = n;G.arcnum = 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 = 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 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+)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;exit(0);elsecontinue;for(int k = 0;k n;k+)for(i = 0;i n;