数据结构面试之九——图的常见操作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;
}