数据结构面试之九——图的常见操作3之最小生成树
数据结构面试之九——图的常见操作3之最小生成树
题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。
九、图的常见操作3之最小生成树
最小生成树——包含带权图中的全部顶点并不能形成环，且权值之和最小的图。
求解最小生成树的方法包括：Prim算法和Kruskal算法。
对于Prim算法思想：1）从源结点集中选定一个源结点（初始源节点集合中只有设定一个结点）；2）从剩余结点中选择与源节点集有连接的且权值最小的边。将该源节点加入源节点集合中。然后迭代执行1），2）。
如下图的图结构，含有7个顶点，下图示为图的邻接矩阵存储结构。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 0
0
6
5
2
∞
∞
∞
Vertex 1
6
0
∞
∞
2
∞
4
Vertex 2
5
∞
0
∞
∞
7
5
Vertex 3
2
∞
∞
0
8
∞
∞
Vertex 4
∞
2
∞
8
0
10
∞
Vertex 5
∞
∞
7
∞
10
0
∞
Vertex 6
∞
4
5
∞
∞
∞
0
模拟执行步骤如下：
前提：源节点集合VertexSet中初始只有设定的0（假定，可以任意取0à6中任意值）。起初初始的边结合EdgeSet为空。
步骤1：从与0相连的边集合中，选定权值最小的边，对应上图Vertex0行显然为2。所以选择的顶点为Vertex3。
VertexSet
EdgeSet
SumWeight
0,3
（0,3）
2
步骤2：从与{0,3}相连的边集合中，选定权值最小的边，如下图，显然权值为5。所以选择的顶点为Vertex2。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 0
0
6
5√
×
∞
∞
∞
Vertex 3
×
∞
∞
0
8
∞
∞
集合变为：
VertexSet
EdgeSet
SumWeight
0,3,2
（0,3）(0,2)
2+5
步骤3：从与{0,3,2}相连的边集合中，选定权值最小的边，如下图，显然权值为4。所以选择的顶点为Vertex6。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 0
0
6
×
×
∞
∞
∞
Vertex 2
×
∞
0
∞
∞
7
5,√
Vertex 3
×
∞
∞
0
8
∞
∞
集合变为：
VertexSet
EdgeSet
SumWeight
0,3,2,6
（0,3）(0,2)（2,6）
2+5+5
步骤4：从与{0,3,2,6}相连的边集合中，选定权值最小的边，如下图，显然权值为5。所以选择的顶点为Vertex1。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 0
0
6
×
×
∞
∞
∞
Vertex 2
×
∞
0
∞
∞
7
×
Vertex 3
×
∞
∞
0
8
∞
∞
Vertex 6
∞
4√
×
∞
∞
∞
0
集合变为：
VertexSet
EdgeSet
SumWeight
0,3,2,6,1
（0,3）(0,2)（2,6）(6,1)
2+5+5+4
步骤5：从与{0,3,2,6,1}相连的边集合中，选定权值最小的边，如下图，显然权值为2。所以选择的顶点为Vertex4。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 0
0
6
×
×
∞
∞
∞
Vertex 1
6
0
∞
∞
2√
∞
×
Vertex 2
×
∞
0
∞
∞
7
×
Vertex 3
×
∞
∞
0
8
∞
∞
Vertex 6
∞
×
×
∞
∞
∞
0
集合变为：
VertexSet
EdgeSet
SumWeight
0,3,2,6,1,4
（0,3）(0,2)（2,6）(6,1)（1,4）
2+5+5+4+2
步骤6：从与{0,3,2,6,1,4}相连的边集合中，选定权值最小的边，如下图，显然权值为2。所以选择的顶点为Vertex4。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 0
0
6
×
×
∞
∞
∞
Vertex 1
6
0
∞
∞
×
∞
×
Vertex 2
×
∞
0
∞
∞
7√
×
Vertex 3
×
∞
∞
0
8
∞
∞
Vertex 4
∞
×
∞
8
0
10
∞
Vertex 6
∞
×
×
∞
∞
∞
0
集合变为：
VertexSet
EdgeSet
SumWeight
0,3,2,6,1,4,5
（0,3）(0,2)（2,6）(6,1)（1,4）(2,5)
2+5+5+4+2+7
最后：遍历后的结果如下2图：即包含所有顶点，没有环路，且权值最小。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 0
0
6
×
×
∞
∞
∞
Vertex 1
6
0
∞
∞
×
∞
×
Vertex 2
×
∞
0
∞
∞
×
×
Vertex 3
×
∞
∞
0
8
∞
∞
Vertex 4
∞
×
∞
8
0
10
∞
Vertex 5
∞
∞
×
∞
10
0
∞
Vertex 6
∞
×
×
∞
∞
∞
0
VertexSet
EdgeSet
SumWeight
0,3,2,6,1,4,5
（0,3）(0,2)（2,6）(6,1)（1,4）(2,5)
2+5+5+4+2+7=25
template <class vType, int size>voidmsTreeType<vType,size>::printTreeAndWeight(){ inttreeWeight = 0; minimalSpanning(source); cout<< "Source vertex: " << source << endl; cout<< "Edges\t\tWeight" << endl; for(int j = 0; j < gSize; j++) { if(edgeWeights[j]!= 0) { treeWeight= treeWeight + edgeWeights[j]; cout<< "(" << j << ", " <<edges[j] << ")\t\t"<< edgeWeights[j] << endl; } } cout<< endl; cout<< "Tree Weight: " << treeWeight << endl;}