离散数学实验6 构造最小生成树
发布时间
阅读量：
阅读量
一、实验目的
了解并掌握最小生成树构建算法的实现方式，深入理解其生成过程的具体步骤。
二、实验内容
定义1 设T是一个连通且回路的无向图，则称T为无向树，简称树。树中度数为1的结点称为树叶，度数大于1的结点称为分枝点(或内点)。
定义2设G＝<V，E>是一个连通的无向图，若G的某个生成子图是一棵树，则称该树为G的生成树，记为TG。
定义3假定图G是具有n个结点的连通图。对应于G的每一条边e，指定一个正数C(e)，把C(e)称作边e的权，(可以是长度、运输量、费用等）。G的生成树也具有一个树权C(T)，它是T的所有边权的和。
定义4 在带权的图G的所有生成树中，树权最小的那棵生成树，称作最小生成树。
定理1 (Kruskal) 设图G有n个结点，执行如下步骤
⑴ 选取权重最小的边e1，并将边数i初始化为1；
⑵ 若i等于n-1则终止流程，否则进入步骤⑶；
⑶ 在已选定的边集合{e1,e2,…,ei}基础上，从图G中挑选一条未被选中的边ei+1，确保新增边后形成的集合{e1,e2,…,ei,ei+1}不构成环路，且ei+1在满足该条件的所有边中具有最小权重；
⑷ 将i的值递增1，返回步骤⑵继续执行。
``
全部评论 (0)
还没有任何评论哟~