資料結構面試之九——圖的常見操作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

6

5

2

∞

4

7

8

10

模拟執行步驟如下：

前提：源節點集合VertexSet中初始隻有設定的0（假定，可以任意取0à6中任意值）。起初初始的邊結合EdgeSet為空。

步驟1：從與0相連的邊集合中，標明權值最小的邊，對應上圖Vertex0行顯然為2。是以選擇的頂點為Vertex3。

VertexSet

EdgeSet

SumWeight

0,3

（0,3）

步驟2：從與{0,3}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為5。是以選擇的頂點為Vertex2。

5√

×

集合變為：

0,3,2

（0,3）(0,2)

2+5

步驟3：從與{0,3,2}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為4。是以選擇的頂點為Vertex6。

5,√

0,3,2,6

（0,3）(0,2)（2,6）

2+5+5

步驟4：從與{0,3,2,6}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為5。是以選擇的頂點為Vertex1。

4√

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。

2√

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。

7√

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圖：即包含所有頂點，沒有環路，且權值最小。

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.還需要存儲每次比較後的最小的權重值。

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.列印小生成樹

voidmsTreeType<vType,size>::printTreeAndWeight()

      inttreeWeight = 0;

      minimalSpanning(source);

      cout<< "Source vertex: " << source << endl;

      cout<< "Edges\t\tWeight" << endl;

             if(edgeWeights[j]!= 0)

                    treeWeight= treeWeight + edgeWeights[j];

                    cout<< "(" << j << ", " <<edges[j]  << ")\t\t"<< edgeWeights[j] << endl;

      cout<< endl;

      cout<< "Tree Weight: " << treeWeight << endl;