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

}


上一篇:凯立德如何获取设备特征码、版本号、激活码?


下一篇:边缘云计算乘物联网东风而来,应用开发是下一个金矿?