数据结构面试之九——图的常见操作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
//inifinity 代表权值无穷大，即不可达。
int g_WeightMatrix[7][7] ={0,6,5,2,infinity,infinity,infinity,
6,0,infinity,infinity,2,infinity,4,
5,infinity,0,infinity,infinity,7,5,
2,infinity,infinity,0,8,infinity,infinity,
infinity,2,infinity,8,0,10,infinity,
infinity,infinity,7,infinity,10,0,infinity,
infinity,4,5,infinity,infinity,infinity,0};
template<class vType, int size>
class msTreeType : publicgraphType<vType, size>
{
public:
voidcreateSpanningGraph();
voidminimalSpanning(vType sVertex);
voidprintTreeAndWeight();
protected:
vTypesource; //
intweights[size][size]; //权重数组
intedges[size]; //边的集合,edges[0]=5即代表0-5之间有边存在。
intedgeWeights[size]; //存储从某顶点开始的权重.
};
1.创建权重图
创建权重图的时候，我们做了简化处理。只是将给定的权重数组赋值过来了。[此处稍作修改，便可以改为手动输入顶点及邻接边的关系]。图的存储形式：邻接矩阵存储！
template <class vType, int size>
voidmsTreeType<vType,size>::createSpanningGraph()
{
gSize= size;
source= 0; //记录初始点为0.
for(int i = 0; i < size; i++)
{
for(int j =0; j < size; j++)
{
weights[i][j]= g_WeightMatrix[i][j];
if(weights[i][j]!= 0 && weights[i][j] != infinity)
{
edges[i]= j; //代表i--j之间的连线存在
// cout << "edges[ " <<i << " ]=" << edges[i] << "\t";
}
cout<< weights[i][j] << "\t";
}
cout<< endl;
}
}
2.最小生成树
1.巧妙的记录源结点、目标结点的方法(通过数组下标和结果值）；2.还需要存储每次比较后的最小的权重值。
template <class vType, int size>
voidmsTreeType<vType,size>::minimalSpanning(vType sVertex)
{
vType startVertex, endVertex;
int minWeight;
source = sVertex;
//代表mstree的结点结合中是否存在点. mstv[5] =true,代表结点5在集合中已经存在。
//=false,则代表不存在.
bool mstv[size];
//初始化 0代表到自身, infinity代表不可达.
for(int j = 0; j < gSize; j++)
{
mstv[j]= false;
edges[j]= source;
edgeWeights[j]= weights[source][j];
}
mstv[source]= true;
edgeWeights[source]= 0; //初始设定
for(int i = 0; i < gSize-1; i++)
{
minWeight= infinity;
//从所有顶点中寻找权重最小且未被标识的顶点,v记录该顶点,minWeight记录权重值。
for(int j = 0; j < gSize; j++)
{
if(mstv[j])//mstv中已经存在的点j
{
for(intk=0; k < gSize; k++)
{
//寻找由已经存在的结点中到剩余结点权值最小的边。
if(!mstv[k]&& weights[j][k] < minWeight)
{
endVertex= k; //目的
startVertex= j; //源
minWeight= weights[j][k]; //最小权重
}
}//endfor k
}//endif(mstv[j])
}//endfor j
mstv[endVertex]= true;
edges[endVertex]= startVertex;
edgeWeights[endVertex]= minWeight;
}//endfor
}
3.打印小生成树
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;
}
