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