一个连通且无回路的无向图称为树。在树中度数为 1的节点为叶,度数大于1的节点称为分枝点或内节点。
给定图 T,以下关于树的定义是等价的。
(1)无回路的连通图。
(2)无回路且e=v-1,其中e为边数,v为节点数
(3)连通且e=v-1。
(4)无回路且增加一条新边,得到一个且仅一个回路
(5)连通且删去任何一个边后不连通。
(6)每一对节点之间有且仅有一条路。
在带权的图 G的所有生成树中,树权最小的那棵生成树称作最小生成树。
求连通的带权无向图的最小代价生成树的算法有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
1.普里姆算法
设已知 G=(V,E)是一个带权连通无向图,顶点 {0,1,2,··,n-1}。设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时,U只包含一个出发顶点。设T是构造生成树过程中已被考虑在生成树上的边的集合,初始时 T为空。如果边(i,j)具有最小代价,且i∈U,j∈V-U,那么最小代价生成树应包含边(i,j)。把j加到U中,把(i,j)加到T中。重复上述过程,直到U等于为止。这时,T即为要求的最小代价生成树的边的集合。
普里姆算法的特点是当前形成的集合 T始终是一棵树。因为每次添加的边是使树中的权尽可能小,因此这是一种贪心的策略。普里姆算法的时间复杂度为 O(n2),与图中边数无关,所以适合于稠密图。
2.克鲁斯卡尔算法
设 T的初始状态只有 n个顶点而无边的森林 T=(V,ψ),按边长递增的顺序选择E中的 n-1 条安全边(u,v)加入 T,生成最小生成。所谓安全边,是指两个端点分别是森林T里两棵树中的顶点的边。加入安全边,可将森林中的两棵树连接成一棵更大的树,因为每一次添加到 T中的边均是当前权值最小的安全边,MST 性质也能保证最终的 7是一棵最小生成树。
克鲁斯卡尔算法的特点是当前形成的集合 T 除最后的结果外,始终是一个森林克鲁斯卡尔算法的时间复杂度为 O(elog2e),与图中顶点数无关,所以较适合于稀疏图。
例如,使用普里姆算法构造图18-1小成的过程如图18-2至18-6