姓名: 陈中普学号: 2011303550 2011303550 2011303550 2011303550 实验时间: 2012/12/28 2012/12/28 2012/12/28 2012/12/28 实验三实验三实验三实验三最小生成树的最小生成树的最小生成树的最小生成树的 kruscal kruscal kruscal kruscal 算法算法算法算法 1. 1. 1. 1. 实验目的通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树,加深对求最小生成树的 Kruskal 算法的理解。 2. 2. 2. 2. 实验内容给定无向连通加权图,编程设计求出其一棵最小生成树。 3. 3. 3. 3. 实验原理设所给定无向连通加权图具有 n 个结点, m 条边, 首先, 将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时, 使得生成树形成回路, 则删除这条边。这样, 直至生成树具有 n-1 条边时, 我们所得到的就是一棵最小生成树。 4. 4. 4. 4. 实验设备及软件环境运行 windows 8 的 PC 机, Code Blocks 集成开发环境。 5. 5. 5. 5. 算法分析由实验原理,可得以下伪代码: 6. 6. 6. 6. 核心代码及结果演示当图为: 执行程序结果为: 即最小生成树为:
离散数学实验 kruskal算法 来自淘豆网m.daumloan.com转载请标明出处.
