实验4图的应用.docVIP

实验四：图的应用 一、实验预备知识 1 复习C++中的全局变量的概念。 2 复习图的邻接矩阵和邻接表两种存储方式。 3 复习图的两种遍历方法和求图的最小生成树的方法。 二、实验目的 1 掌握图的邻接矩阵和邻接表两种存储方法。 2 掌握有关图的操作算法并用高级语言实现。 3 熟悉图的构造算法，了解实际问题的求解效率与采用何种存储结构与算法有着密切联系。 4 掌握图的两种有哪些信誉好的足球投注网站路径的遍历算法。 5 掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法。 三、实验内容 1 创建给定图的存储结构，从邻接表和邻接矩阵两种存储方式中选择一种。 2 对所创建的图进行深度和广度优先有哪些信誉好的足球投注网站遍历，给出遍历过程中的顶点序列。 3 求图的最小生成树，按构造顺序输出边的序列。（两种方法都要求！） 3 编写一个主函数，将上面函数连在一起，构成一个完整程序。 4 将实验源程序调试并运行。 四、实验要求 所建立的图为： 用邻接表存储结构时，所创建的单链表以结点的从小到大排列。 注意标志数组visited[n+1] 的定义和赋值。 将顶点1作为起点。 五、实验结果 #includeiostream using namespace std; const int Max=20; const int max=200; typedef int Vertextype; typedef int Edgetype; bool visited[Max]; typedef struct { Vertextype vertex[Max]; Edgetype edges[Max][Max]; int Vnum,Enum;//顶点和边 }Graph; //邻接矩阵 typedef struct { int v1; int v2; Edgetype cost; }edge; edge edges[Max]; void Create(Graph G) { int i,j,k,m; cout请输入顶点数和边数：endl; cout顶点数：; cinG.Vnum; cout边数：; cinG.Enum; for(i=0;iG.Vnum;i++) G.vertex[i]=i+1; for(i=0;iG.Vnum;i++) for(j=0;jG.Vnum;j++) { G.edges[i][j]=max; G.edges[i][i]=0; } for(k=0;kG.Enum;k++) { cout请输入第k+1条边的信息（顶点1、顶点2、权值）:; cinijm; G.edges[i][j]=m; G.edges[j][i]=m; } } int PrintfMGraph(Graph G) { cout建立的图邻接矩阵为：endl; cout********-1代表无穷大********endl; for(int i=0;iG.Vnum;++i) cout G.vertex[i] ; coutendl; for(i=0;iG.Vnum;++i) { cout|G.vertex[i] ; for(int j=0;jG.Vnum;++j) { coutG.edges[i][j] ; } cout|endl; } return 1; } void DFSAL(Graph G,int i) { int j; cout-G.vertex[i]; visited[i]=true; for(j=0;jG.Vnum;j++) if(G.edges[i][j]!=0G.edges[i][j]!=max!visited[j]) DFSAL(G,j); } 深度优先遍历算法： void DFSTG(Graph G) { int i; for(i=0;iG.Vnum;i++) visited[i]=false; for(i=0;iG.Vnum;i++) if(!visited[i]) DFSAL(G,i); coutendl; } 广度优先遍历算法： void BFST(Graph G) { int i,j,k; for(i=0;iG.Vnum;i++) visited[i]=false; for(i=0;iG.Vnum;i++) { if(!visited[i]) { int Queue[Max]; int front=-1,rear=-1; cout-G.vertex[i]; visited[i]=true; Queue[++rear]=i; while(front!=rear) {