北邮数据结构实验第二次实验图.pdf

数据结构实验报告 1． 实验要求 （1）实验目的 通过选择下面 5 个题目之一进行实现，掌握如下内容： 掌握图基本操作的实现方法 了解最小生成树的思想和相关概念 了解最短路径的思想和相关概念 学习使用图解决实际问题的能力 (2) 实验内容 根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。 图的基本功能： 1、图的建立 2、图的销毁 3、深度优先遍历图 4、广度优先遍历图 5 、使用普里姆算法生成最小生成树 6、使用克鲁斯卡尔算法生成最小生成树 7、求指定顶点到其他各顶点的最短路径 8、其他：比如连通性判断等自定义操作 编写测试 main() 函数测试图的正确性 2. 程序分析 2.1 存储结构 图： (1) 带权值的无向图 V0 9 6 V1 2 V2 (2) 带权值的有向图 V0 6 3 9 4 V1 2 V2 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