以Prim's Algorithm來求最小成本擴張樹

 
 #include "stdafx.h"
#include <iostream>
#include <stdio.h>
#define INF 10000000

using namespace std;

//一個undirected graph的adjacency matrix
int adjMatrix[8][8] =
{
 {0, 300, 1000, INF, INF, INF, INF, 1700},
 {300, 0, 800, INF, INF, INF, INF, INF},
 {1000, 800, 0, 1200, INF, INF, INF, INF},
 {INF, INF, 1200, 0, 1500, 1000, INF, INF},
 {INF, INF, INF, 1500, 0, 250, INF, INF},
 {INF, INF, INF, 1000, 250, 0, 900, 1400},
 {INF, INF, INF, INF, INF, 900, 0, 1000},
 {1700, INF, INF, INF, INF, 1400, 1000, 0},
 
};

int addedVertices[8] = {0};
int addedVerticesNum = 1;       //紀錄成為spanning tree的各邊中其中一點的數目數目。第一個點為0

bool isAdded(int v)
{
 //檢驗這個點是不是已被加入spanning tree的邊中其中一個點

 for (int i = 0 ; i < addedVerticesNum; i ++)
 {
  if (addedVertices[i] == v)
   return true;
 }

 return false;
}


//紀錄會成為spanning tree的7條邊。若頂點數目是n則是n-1條邊
struct Edge
{
 int node1;
 int node2;

} edge[7];


int main(int argc, char* argv[])
{

 int p1, p2;   //紀錄被檢驗的邊的兩點
 int lowestWeight; //在下面的三層迴圈中，暫存與已被加入spanning tree的邊相連的邊中，weight最低的
 int thep1, thep2; //紀錄這一次要被加入minimum cost spanning tree的邊的兩個頂點  
  
 
 for (int i = 0 ; i < 8 ; i ++)
 { 
  lowestWeight = INF;

  for (int count = 0; count < addedVerticesNum; count++)
  {
   //從幾個已被加的點開始找
   p1 = addedVertices[count];

   for (p2 = 0; p2 < 8 ; p2++)
   {
    if ( p2 != p1 && adjMatrix[p1][p2] < lowestWeight && !isAdded(p2) )
    { 
     //這個要被加入spanninf tree的邊的兩個點不同，所以 p2 != p1
     //兩個點之間須有邊相連，所以 adjMatrix[p1][p2] < INF。
     //adjMatrix[p1][p2] < lowestWeight則是為了找出權重最低的邊
     //在加一條新的邊時，依prim的演算法必須一點是已被加入spanning tree的邊中的其中一點，另一點不是。
     //而p1 = addedVertices[count] 和 !isAdded(p2)代表p1是其中一點，p2不是

     lowestWeight = adjMatrix[p1][p2];
     thep1 = p1;
     thep2 = p2;
    } 
   }


  }
  

  if (lowestWeight < INF)
  {
   edge[addedVerticesNum - 1].node1 = thep1;
   edge[addedVerticesNum - 1].node2 = thep2;
   //thep1是新加入spanning tree的邊中，已和其中一條被加入spanning tree的邊相連的點，
   //thep2則是尚未與被加入spanning tree的邊相連的另一點

   addedVertices[addedVerticesNum] = thep2; 
   addedVerticesNum++;
  }
  else //若lowestWeight = INF，表示p1未與其他任何點相連，所以整個圖必定沒有spanning tree
   break;
   
 }
  
  
 

 if (addedVerticesNum < 8 )
  cout << "No spanning tree\n";
 else
 {
  cout << "The edges of the spanning tree are:\n";

  for (int i = 0 ; i < 7; i++ )
   cout << "edge " << edge[i].node1 << edge[i].node2 << endl;
 
 }

 //以文章最上面的圖為例，就會輸出
 //the edges of the spanning tree are:
 //edge 01
 //edge 12
 //edge 23
 //edge 35
 //edge 54
 //edge 56
 //edge 67


 system("PAUSE");
 return 0;
}