两种算法实现最小生成树.doc

数据结构上机实验报告 题目：两种算法实现最小生成树 学生姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 2014.12.9 目 录第一章 需求分析11.1 原题表述11.2 问题解决方案1第二章 概要设计22.1 抽象数据类型22.2 主要算法描述22.1.1 Prim算法实现22.1.2 Kruskal算法实现32.3 主要算法分析3第三章 概要设计43.1 程序代码43.1.1 Prim算法实现43.1.2 Kruskal算法实现6第四章 调试分析94.1 出现的问题及解决方法9第五章 测试分析105.1 测试样例10I第一章 需求分析1.1 原题表述某市为实现交通畅行，计划使全市中的任何两个村庄之间都实现公路互通，虽然不需要直接的公路相连，只要能够间接可达即可。现在给出了任意两个城镇之间修建公路的费用列表，以及此两个城镇之间的道路是否修通的状态，要求编写程序求出任意两村庄都实现公路互通的最小成本。输入参数：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1 N 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。当N为0时输入结束。输出参数：每个测试用例占输出的一行，输出实现后所需的最小成本值1.2 问题解决方案第一种方案：使用Prim算法首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。第二种方案：使用kruskal算法算法过程：1.将图各边按照权值进行排序2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。第二章 概要设计2.1 抽象数据类型ADT Graph 数据对象V：V是具有相同特性的数据元素的和，称为顶点级。数据关系R：R = VRVR = |v,w V 且 P（v,w），表示从v到w的弧，谓词P（v,w）定义了弧的意义或信息基本操作：CreatGraph（&G,V）初始条件：v是顶点数量操作结果：构造含有V个顶点的图GPrim(G)初始条件：图G存在操作结果：找到图G中最小生成树Kruskal（G）初始条件：图G存在操作结果：找到图G中最小生成树ADT Graph2.2 主要算法描述2.1.1 Prim算法实现2.2.2 Kruskal算法实现2.3 主要算法分析Prim算法时间复杂度为O（n2），与图中顶点个数有关，而与边数无关。Kruskal算法时间复杂度为O（eloge），与途中的边数有关，而与顶点数无关。 第三章 详细设计3.1 程序代码3.1.1 Prim算法实现#include#define NUM 200 /最大顶点数#define MAX 40000 /最大值/定义邻接矩阵的结构typedef struct int edgesNUMNUM; /邻接矩阵 int n; /顶点数 int e; /边数MGraph;/构造邻接矩阵，v表示顶点数void CreatGraph(MGraph &G, int v) G.n = v; G.e = v * (v - 1) / 2; for(int i = 1; i = G.n; i+) /初始化邻接矩阵 for(int j = 1; j = G.n; j+) G.edgesij = MAX; for(int i = 1; i = G.e; i+) /构造邻接矩阵 /v1,v2一条路连接的两村庄，cost修路费用，build修建状态 int v1, v2, cost, build; scanf(%d%d%d%d, &v1, &v2, &cost, &build); if(build = 1) cost = 0; G.edgesv1v2 = cost; G.edgesv2v1 = cost; int Prim(MGraph G) int result = 0; /用于记录修路成本 int lowcostNUM; /存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值 int vexNUM; /记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小) for(int i = 1; i = G.n; i+) /初始化lowcost,vex lowcosti = G.edges1i; vexi = 1; vex1 = -1; /加到生成树顶点集合 for(int i = 2; i = G.n; i+) /循环n-1次, 加入n-1条边 int min = MAX; int k; /存放最小生成树结点的变量 for(int j = 1; j = G.n; j+) if(vexj != -1 & lowcostj min) min = lowcostj; /求生成树外顶点到生成树内顶点具有最 k = j; /小权值的边, k是当前具最小权值的边 result = result + lowcostk; /将最小权值记录 vexk = -1; /该边加入生成树标记 for(int j = 1; j = G.n; j+) /修改lowcost, vex if(vexj != -1 & G.edgeskj lowcostj) lowcostj = G.edgeskj; vexj = k; return result;int main() while(true) int v; scanf(%d, &v); if(v = 0)break; MGraph G; CreatGraph(G, v); int cost = Prim(G); printf(%dn, cost); return 0;3.1.2 Kruskal算法实现#include#define NUM 200 /最大顶点个数#define EDGENUM 20000 /最大的边数#define MAX 40000 /最大值/定义邻接矩阵的结构typedef struct int edgesNUMNUM; /邻接矩阵 int n; /顶点数 int e; /边数MGraph;/定义边的结构typedef struct int begin; /边的起点 int end; /边的终点 int weight; /边的权值Edge;/构造邻接矩阵，v表示顶点数void CreatGraph(MGraph &G, int v) G.n = v; G.e = v * (v - 1) / 2; for(int i = 1; i = G.n; i+) /初始化邻接矩阵 for(int j = 1; j = G.n; j+) G.edgesij = MAX; for(int i = 1; i 0) k = parentk; return k;/Kruskal算法实现int Kruskal(MGraph G) Edge edgeEDGENUM; /图对应的所有边 int parentEDGENUM; /用于记录顶点的终点 int k = 1; /用于记录边的数量 for(int i = 1; i = G.n; i+) /构建边 for(int j = i + 1; j = G.n; j+) edgek.begin = i; edgek.end = j; edgek.weight = G.edgesij; k+; /根据边的权值大小对边数组进行从小到大排序 for(int i = 1; i k; i+) for(int j = i + 1; j edgej.weight) int temp; temp = edgei.begin; edgei.begin = edgej.begin; edgej.begin = temp; temp = edgei.end; edgei.end = edgej.end; edgej.end = temp; temp = edgei.weight; edgei.weight = edgej.weight; edgej.weight = temp; /初始化parent数组 for(int i = 1; i = G.n; i+) parenti = 0; int m, n; int result = 0; /用于记录修路成本 for(int i = 1; i = G.e; i+) /判断遍历的边是存在环 m = Find(parent, edgei.begin); n = Find(parent, edgei.end); if(m != n) parentn = m; result = result + edgei.weight; return result;int main() while(true) int v; scanf(%d, &v); if(v = 0)break; MGraph G; CreatGraph(G, v); int cost = Kruskal(G