最小生成树的Kruskal算法实验报告

大 连 民 族 学 院 计算机科学与工程学院实验报告 实 验 题 目 ： 最 小 生 成 树 的 Kruskal 算 法 课 程 名 称 ： 离 散 数 学 实 验 类 型 ： □ 演 示 性 □ 验 证 性 □ 操 作 性 ■ 设 计 性 □ 综 合 性 专 业 ： 软 件 工 程 班 级 ： 111 学 生 姓 名 ： xx 学 号 ： xx 实 验 日 期 ： 2012 年 12 月 6-28 日 实 验 地 点 ： 金 石 滩 校 区 机 房 201 实 验 学 时 ： 10 学 时 实 验 成 绩 ： 指 导 教 师 ： 焉 德 军 姜 楠 2012 年 12 月 28 日 [实验原理] 设所给定无向连通加权图具有n 个结点，m 条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1 条边时，我们所得到的就是一棵最小生成树。 [实验内容] 给定无向连通加权图，编程设计求出其一棵最小生成树。 [实验目的] 通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal 算法的理解。 [实验步骤] （1） 边依小到大顺序得l1，l2，…，lm。 （2） 置初值：S，0i，1j。 （3） 若 i=n-1，则转（6）。 （4） 若生成树边集 S 并入一条新的边lj之后产生的回路，则j+1j，并转（4）。 （5） 否则，i+1i；ljS（i）；j+1j，转（3）。 （6） 输出最小生成树S。 （7） 结束。 具体程序的C++实现如下： #include using namespace std; const int MaxVertex = 20; const int MaxEdge = 100; const int MaxSize = 100; struct EdgeType { int from; int to; int weight; }; struct EdgeGraph { char vertex[MaxVertex]; EdgeType edge[MaxEdge]; int vertexNum; int edgeNum; }; int FindRoot(int parent[], int v); void InputInfo(); void Kruskal(EdgeGraph G) { int vex1,vex2,f,t; int i,num; int parent[MaxVertex]; for(i=0; i