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

 

//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;
}