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

实验报告

学院（系）名称：计算机与通信工程学院 姓名 班级 ** 2015级*班 课程名称 学号 实验项目 ******** 专业 计算机科学与技术 实验四：图的深度优先与广度优先遍历 课程代码 0661013 数据结构与算法 实验时间 考核标准 成绩栏 实验过程 25分 程序运行 20分 2017年5 月 12日第5-6节 回答问题 15分 ○正确 ○基本正确 ○有提示 ○无法回答 实验报告 30分 ○完整 ○较完整 ○一般 ○内容极少 ○无报告 实验地点 特色 功能 5分 考勤违纪情况 5分 7-216 成绩 其它批改意见: 考核内容 评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。 □功能完善, □功能不全 □有小错 □无法运行 ○有 ○无 ○有 ○无 教师签字： 一、 实验目的 理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法 二、 实验题目与要求 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 vertices[MAX_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,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 usingnamespace std; #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 //typedef enum {DG,DN,AG,AN}GraphKind; typedefint Elemtype; typedefstruct QueueNode { Elemtype data; struct QueueNode *next; }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->front = Q->rear = p; Q->front->next = NULL; return Q; } bool QueueEmpty(QueueList *Q) { if(Q->front == Q->rear) returntrue; else returnfalse; } 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 << temp->data << endl; } } } typedefstruct Arc { int adj; }Arc,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct { int vertex[MAX_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.vertex[i] = i + 1; } for(i = 0;i < n;i++) for(j = 0;j < n;j++) G.arcs[i][j].adj = 0; for(int k = 0;k < m;k++) { cin >> i >> j; G.arcs[i-1][j-1].adj = G.arcs[j-1][i-1].adj = 1; } } bool visited[MAX_VERTEX_NUM]; int count = 0; void DFS(Graph G,int v) { visited[v-1] = true; count++; cout << v; if(count < G.vexnum) cout <<\; for(int i = v;i < G.vexnum;i++) if(G.arcs[v-1][i].adj != 0 && !visited[i]) DFS(G,G.vertex[i]); } void DFSTraverse(Graph G) { int v = 0; for(v = 0;v < G.vexnum;v++) { visited[v] = 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++) { visited[v] = false; } QueueList *queue; queue = CreateQueue(); v = 1; EnQueue(queue,v); visited[v-1] = true; while(!QueueEmpty(queue)) { DeQueue(queue,&u); k++; cout << u; if(k < G.vexnum) cout <<\; for(int i = u;i < G.vexnum;i++) if(G.arcs[u-1][i].adj != 0 && !visited[i]) { EnQueue(queue,G.vertex[i]); visited[i] = true; } } } int main() { Graph G1; } 2、 int m = 0;//边数 int n = 0;//顶点数 cin >> n >> m; CreateAG(G1,n,m); DFSTraverse(G1); cout << endl; BFS(G1); return 0; #include usingnamespace std; #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedefint Elemtype; typedefstruct QueueNode { Elemtype data; struct QueueNode *next; }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->front = Q->rear = p; Q->front->next = NULL; return Q; } bool QueueEmpty(QueueList *Q) { if(Q->front == Q->rear)

returntrue; else returnfalse; } 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 << temp->data << endl; } } } typedefstruct ArcNode { int adjvex; struct ArcNode *nextarc; }ArcNode; typedefstruct VNode { int data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct { 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 > i >> j; ArcNode *s,*p; s = (ArcNode*)malloc(sizeof(ArcNode)); s->adjvex = j-1; s->nextarc = NULL; if(G.vertex[i-1].firstarc == NULL) { G.vertex[i-1].firstarc = s; } else { p = G.vertex[i-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++) indegree[i] = 0; for(i = 0;i < G.vexnum;i++) { p = G.vertex[i].firstarc; while(p) { indegree[p->adjvex]++; p = p->nextarc; } } } void TopologicalSort(Graph G) { int i,k,count,indegree[MAX_VERTEX_NUM]; bool visited[MAX_VERTEX_NUM]; for(i = 0;i < G.vexnum;i++) visited[i] = false; ArcNode *p; count = 0; FindInDegree(G,indegree); while(count < G.vexnum) { for(i = 0;i < G.vexnum;i++) { if(indegree[i] == 0 && visited[i] == false) { cout << G.vertex[i].data; if(count < G.vexnum-1) cout <<\; count++; visited[i] = true; for(p = G.vertex[i].firstarc;p;p = p->nextarc) { k = p->adjvex; indegree[k]--; } break; } } } } int main() { } int n;//节点数 int m;//关系数 cin >> n >> m; Graph G1; CreateDN(G1,m,n); TopologicalSort(G1); return 0; 3、 #include usingnamespace std; #define INFINITY 1000 #define MAX_VERTEX_NUM 20 typedefint Elemtype; typedefint Elemtype; typedefstruct QueueNode { Elemtype data; struct QueueNode *next; }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->front = Q->rear = p; Q->front->next = NULL; return Q; } bool QueueEmpty(QueueList *Q) { if(Q->front == Q->rear) returntrue; else returnfalse; } 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 << temp->data << endl; } } } typedefstruct Arc { int adj; }Arc,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct { int vertex[MAX_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.vertex[i] = i+1; } for(i = 0;i < n;i++) for(j = 0;j < n;j++) { G.arcs[i][j].adj = INFINITY; } for(int k = 0;k < m;k++) { cin >> i >> j >> w; if(G.arcs[i-1][j-1].adj > w)

G.arcs[i-1][j-1].adj = G.arcs[j-1][i-1].adj = w; } } void Floyd(Graph G,int n,int m) { int i,j; int max = 0; int A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; for(i = 0;i < n;i++) for(j = 0;j < n;j++) { A[i][j] = G.arcs[i][j].adj; if(A[i][j] < INFINITY) path[i][j] = i; else path[i][j] = 0; } int t; int sum; 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); } else continue; } } for(int k = 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]; } // cout << \处?|理¤¨a后¨?\ //for(i = 0;i < n;i++) //{ // for(j = 0;j < n;j++) // if(A[i][j] < INFINITY) // cout << A[i][j] << \ // else // cout << 0 << \ // cout << endl; //} //cout << \ //for(i = 0;i < n;i++) //{ // for(j = 0;j < n;j++) // cout << path[i][j] << \ // cout << endl; //} for(i = 0;i < n;i++) for(j = 0;j < n;j++) if(A[i][j] > max) max = A[i][j]; cout << max; } bool visited[MAX_VERTEX_NUM]; int count = 0; void DFS(Graph G,int v) { visited[v-1] = true; count++; cout << v; if(count < G.vexnum) cout <<\; for(int i = v;i < G.vexnum;i++) if(G.arcs[v-1][i].adj != 0 && !visited[i]) DFS(G,G.vertex[i]); } void DFSTraverse(Graph G) { int v = 0; for(v = 0;v < G.vexnum;v++) { visited[v] = false; } v = 1;//遍à¨|历¤¨2入¨?口¨2点ì? 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++) { visited[v] = false; } QueueList *queue; queue = CreateQueue(); v = 1; EnQueue(queue,v); visited[v-1] = true; while(!QueueEmpty(queue)) { DeQueue(queue,&u); k++; cout << u; if(k < G.vexnum) cout <<\; for(int i = u;i < G.vexnum;i++) if(G.arcs[u-1][i].adj != 0 && !visited[i]) { EnQueue(queue,G.vertex[i]); visited[i] = true; } } } int main() { } int n;//节¨2点ì?数oy int m;//关?系|ì数oy cin >> n >> m; Graph G1; CreateAN(G1,n,m); if(m == 0) { cout << 0; exit(0); } else { Floyd(G1,n,m); } return 0;

本文来源：https://www.bwwdw.com/article/ccu6.html