数据结构实验报告1．实验要求（ 1）实验目的通过选择下面 5 个题目之一进行实现，掌握如下内容：掌握图基本操作的实现方法了解最小生成树的思想和相关概念了解最短路径的思想和相关概念学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。

图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试 main() 函数测试图的正确性2.程序分析2.1存储结构图：(1)带权值的无向图V096V12V2(2)带权值的有向图V063 94V12V2 2.2关键算法分析（1）深度优先遍历int visited[MAXSIZE]={false}; template<class T>void MGraph<T>::DFS(int v){cout<<vertex[v];visited[v]=true;for(int j=0;j<vNum;j++)if(arc[v][j]==1&&!visited[j])DFS(j);}时间复杂度： O(n2)（2）广度优先遍历int queue[MAXSIZE];int f=0,r=0;cout<<vertex[v];visit[v]=true;queue[++r]=v;while(f!=r){v=queue[++f];for(int j=0;j<vNum;j++){if(arc[v][j]==1&&!visit[j]){cout<<vertex[j];visit[j]=true;queue[++r]=j;}时间复杂度： O（ n2）（3）普利姆算法int adjvex[MAXSIZE];int lowcost[MAXSIZE];int MAX=10000;template<class T>int mininum(MGraph<T> G,int a[]){int min=MAX;int k=0;for(int i=0;i<G.vNum;i++){if(a[i]!=0&&a[i]<min)//寻找 U-{V-U} 中边权值最小的顶点{min=a[i];k=i;}}return k;}template<class T>void MGraph<T>:: Prim(MGraph G){for(int i=0;i<G.vNum;i++){adjvex[i]=0;lowcost[i]=G.arcs[0][i];}lowcost[0]=0;//初始化 U={vo}for(int i=1;i<G.vNum;i++){int k=mininum(G,lowcost);//求下一个边权值最小的邻接点cout<<'V'<<adjvex[k]<<"->V"<<k<<endl;lowcost[k]=0;for(int j=0;j<G.vNum;j++){if(lowcost[j]!=0&&G.arcs[k][j]<lowcost[j]){lowcost[j]=G.arcs[k][j];adjvex[j]=k;}}}}时间复杂度： O(n2)（4）克鲁斯卡尔算法template<class T>void GenSortEdge(MGraph<T> G,VEdge E[])//获取EdgeList{int k=0,i,j;for(i=0;i<G.vNum;i++)//边赋值for(j=i;j<G.vNum;j++)if(G.arcs[i][j]!=MAX){E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;i<G.arcNum-1;i++){for(j=i+1;j<G.arcNum;j++)if(E[i].weight>E[j].weight){VEdge t=E[i];E[i]=E[j];E[j]=t;}}}const int MAX_VERTEXT=20;template<class T>void MGraph<T>:: Kruskal(VEdge E[],int n,int e){int vset[MAX_VERTEXT];for(int i=0;i<n;i++) vset[i]=i;//初始化vset int k=0,j=0;while(k<n-1){int m=E[j].fromV,n=E[j].endV;int sn1=vset[m];//m int sn2=vset[n];//n if(sn1!=sn2){所属的集合所属的集合cout<<'V'<<m<<"->V"<<n<<endl;k++;for(int i=0;i<n;i++){if(vset[i]==sn2)//集合编号为sn2 的全部改为sn1 vset[i]=sn1;时间复杂度： O(n2 )（5）求最短路径，连通性判断int dist[MAXSIZE][MAXSIZE];int path[MAXSIZE][MAXSIZE];template<class T>void Floyd(MGraph<T> G){for(int i=0;i<G.vNum;i++)//寻找最短路径for(int j=0;j<G.vNum;j++){dist[i][j]=G.arcs[i][j];if(dist[i][j]!=MAX_VALUE)path[i][j]=i;elsepath[i][j]=-1;}for(int k=0;k<G.vNum;k++)for(int i=0;i<G.vNum;i++)for(int j=0;j<G.vNum;j++)if(dist[i][k]+dist[k][j]<dist[i][j])//更新迭代数组Disk[][]{dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}cout<<" 任意两点间的最短路径长度( 以矩阵表示）： "<<endl;int l=1;for(int i=0;i<G.arcNum;i++)for(int j=0;j<G.arcNum;j++){cout<<dist[i][j]<<" ";l++;if(l>G.arcNum) {cout<<endl;l=1;}}}时间复杂度： O(n3)3.程序运行结果（1）流程图：初始化带权值的无向图深度优先遍历，广度优先遍历用普利姆算法求最小生成树用克鲁斯卡尔算法求最小生成树初始化带权值的有向图用 Floyd 算法求任意两点间最短路径，并判断连通性删除图（2）本程序所用的图带权值的无向图V096V12V2带权值的有向图V06394V12V2（ 3）程序结果4.总结（1）遇到的问题：私有数据访问权的问题，在编程时应该注意（2）心得体会：通过这次实验，我掌握了图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念等等。

（3）改进：可以适当对某些步骤进行合并或省略，使程序更加简洁。

源代码：#include<iostream>using namespace std;const int MAXSIZE=20;const int MAX_EDGE=20;const int MAX_VALUE=1000;struct VEdge{int fromV;// int endV;// int weight;//起始顶点终止顶点边的权值};VEdge EdgeList[MAX_EDGE];template<class T>class MGraph{public:MGraph(T a[],int n,int e);MGraph(T a[],int n,int e,int h);void DFS(int v);void BFS(int v);void Prim(MGraph G);void Kruskal(VEdge E[],int n,int e);int vNum,arcNum;int arcs[MAXSIZE][MAXSIZE];//用于储存权值的数组int arc[MAXSIZE][MAXSIZE];private:T vertex[MAXSIZE];};template<class T> //构造带权值的有向图MGraph<T>::MGraph(T a[],int n,int e,int h){int i,j,k,l;vNum=n;arcNum=e;for(k=0;k<n;k++) vertex[k]=a[k];for(k=0;k<n;k++)for(j=0;j<n;j++) arc[k][j]=0;for(int i=0;i<MAXSIZE;i++){for(int j=0;j<MAXSIZE;j++){arcs[i][j]=MAX_VALUE;}}cout<<"请输入连通的两顶点下标(弧头-弧尾）及弧的权值(<1000)："<<endl;for(int i=0;i<MAXSIZE;i++){arcs[i][i]=0;}for(k=0;k<h;k++){cin>>i>>j>>l;arcs[i][j]=l;arc[i][j]=1;}}template<class T>//带权值的无向图MGraph<T>::MGraph(T a[],int n,int e){int i,j,k,l;vNum=n;arcNum=e;for(k=0;k<n;k++) vertex[k]=a[k];for(k=0;k<n;k++)for(j=0;j<n;j++) arc[k][j]=0;cout<<"请输入连通的两顶点下标及边的权值(<1000)： "<<endl;for(k=0;k<e;k++){cin>>i>>j>>l;arcs[i][j]=l;arcs[j][i]=arcs[i][j];arc[i][j]=1;arc[j][i]=arc[i][j];}}//深度广度遍历int visited[MAXSIZE]={false}; template<class T>void MGraph<T>::DFS(int v){cout<<vertex[v];visited[v]=true;for(int j=0;j<vNum;j++)if(arc[v][j]==1&&!visited[j])DFS(j);}int visit[MAXSIZE]={false};template<class T>void MGraph<T>::BFS(int v){int queue[MAXSIZE];int f=0,r=0;cout<<vertex[v];visit[v]=true;queue[++r]=v;while(f!=r){v=queue[++f];for(int j=0;j<vNum;j++){if(arc[v][j]==1&&!visit[j]){cout<<vertex[j];visit[j]=true;queue[++r]=j;}}}}//普利姆算法int adjvex[MAXSIZE];int lowcost[MAXSIZE];int MAX=10000;template<class T>int mininum(MGraph<T> G,int a[]){int min=MAX;int k=0;for(int i=0;i<G.vNum;i++){if(a[i]!=0&&a[i]<min)//寻找 U-{V-U} 中边权值最小的顶点{min=a[i];k=i;}}return k;}template<class T>void MGraph<T>:: Prim(MGraph G){for(int i=0;i<G.vNum;i++){adjvex[i]=0;lowcost[i]=G.arcs[0][i];}lowcost[0]=0;//初始化 U={vo}for(int i=1;i<G.vNum;i++){int k=mininum(G,lowcost);//求下一个边权值最小的邻接点cout<<'V'<<adjvex[k]<<"->V"<<k<<endl;lowcost[k]=0;for(int j=0;j<G.vNum;j++){if(lowcost[j]!=0&&G.arcs[k][j]<lowcost[j]){lowcost[j]=G.arcs[k][j];adjvex[j]=k;}}}}//克鲁斯卡尔算法template<class T>void GenSortEdge(MGraph<T> G,VEdge E[])//获取EdgeList{int k=0,i,j;for(i=0;i<G.vNum;i++)//边赋值for(j=i;j<G.vNum;j++)if(G.arcs[i][j]!=MAX){E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;i<G.arcNum-1;i++){for(j=i+1;j<G.arcNum;j++)if(E[i].weight>E[j].weight){VEdge t=E[i];E[i]=E[j];E[j]=t;}}}const int MAX_VERTEXT=20;template<class T>void MGraph<T>:: Kruskal(VEdge E[],int n,int e){int vset[MAX_VERTEXT];for(int i=0;i<n;i++) vset[i]=i;//初始化vset int k=0,j=0;while(k<n-1){int m=E[j].fromV,n=E[j].endV;int sn1=vset[m];//m int sn2=vset[n];//n if(sn1!=sn2){所属的集合所属的集合cout<<'V'<<m<<"->V"<<n<<endl;k++;for(int i=0;i<n;i++){if(vset[i]==sn2)//集合编号为sn2 的全部改为sn1 vset[i]=sn1;}}j++;}}//求最短路径//连通性判断int dist[MAXSIZE][MAXSIZE];int path[MAXSIZE][MAXSIZE];template<class T>void Floyd(MGraph<T> G){for(int i=0;i<G.vNum;i++)//寻找最短路径for(int j=0;j<G.vNum;j++){dist[i][j]=G.arcs[i][j];if(dist[i][j]!=MAX_VALUE)path[i][j]=i;elsepath[i][j]=-1;}for(int k=0;k<G.vNum;k++)for(int i=0;i<G.vNum;i++)for(int j=0;j<G.vNum;j++)if(dist[i][k]+dist[k][j]<dist[i][j])//更新迭代数组Disk[][]{dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}cout<<" 任意两点间的最短路径( 以矩阵表示）： "<<endl;int l=1;for(int i=0;i<G.arcNum;i++)for(int j=0;j<G.arcNum;j++){cout<<dist[i][j]<<" ";l++;if(l>G.arcNum) {cout<<endl;l=1;}}}void main(){int v,e;cout<<" 请输入顶点数(<21) 和边数 (<21) ：";cin>>v>>e;if(v>20||v<0||e<0||e>20)cout<<" 输入错误！ "<<endl;charch[20]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t'};MGraph<char> A(ch,v,e);cout<<"请输入深度优先遍历的起始顶点下标：";int s;cin>>s;cout<<" 深度优先遍历:"<<endl;A.DFS(s);cout<<endl;cout<<" 请输入广度优先遍历的起始顶点下标：";int k;cin>>k;cout<<" 广度优先遍历："<<endl;A.BFS(k);cout<<endl;cout<<" 普利姆算法求最小生成树："<<endl;A.Prim(A);cout<<" 克鲁斯卡尔算法求最小生成树："<<endl;VEdge EdgeList[MAX_EDGE];GenSortEdge(A,EdgeList);A.Kruskal(EdgeList,v,e);//初始化带权值的有向图cout<<" 构造带权值的有向图，请输入弧数：";int h;cin>>h;MGraph<char> B(ch,v,e,h);Floyd(B);}。