一、概念

最小生成樹：一個有 n 個結(jié)點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結(jié)點，并且有保持圖連通的最少的邊。

生成樹的特點：
1、圖是連通圖;
2、圖中包含了了N個頂點;
3、圖中邊的數(shù)量等于N-1條邊.

求最小生成樹的算法有prim(普里姆)算法和kruskal(克魯斯卡爾)算法

二、prim(普里姆)算法

1、思路

• 定義2個數(shù)組; adjvex ?來保存相關(guān)頂點下標(biāo); lowcost 保存頂點之間的權(quán)值
• 初始化2個數(shù)組, 從v0開始尋找最??成樹, 默認(rèn)v0是最??成樹上第?個頂點
• 循環(huán)lowcost 數(shù)組,根據(jù)權(quán)值,找到頂點 k;
• 更新lowcost 數(shù)組
• 循環(huán)所有頂點,找到與頂點k 有關(guān)系的頂點. 并更新lowcost 數(shù)組與adjvex 數(shù)組;
  2、代碼實現(xiàn)

void MiniSpanTree_Prim(MGraph G){
    int min;
    int sum = 0;

    int adjvex[MAXVEX];//保存相關(guān)頂點下標(biāo)，如頂點0和頂點相連，則adjvex[1] = 0;
    int lowcost[MAXVEX];//保存相關(guān)頂點的權(quán)值
    
    //當(dāng)v0加入生成樹，adjvex和lowcost數(shù)組的值初始化
    for (int i = 0; i<G.numNodes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }
    
    //循環(huán)除0以外的全部頂點，找到lowcost數(shù)組中最小的頂點k
    for (int i = 1; i<G.numNodes; i++) {
        min = INFINITYC;
        int j = 1;
        int k = 0;
        while (j<G.numNodes) {
            if (lowcost[j] != 0 && lowcost[j]<min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("v%d - v%d = %d\n",adjvex[k],k,G.arc[adjvex[k]][k]);
        sum += G.arc[adjvex[k]][k];
        lowcost[k] = 0; //頂點k已加入生成樹
        
        //更新lowcost數(shù)組和adjvex數(shù)組
        for (j = 1; j<G.numNodes; j++) {
            if (lowcost[j] != 0 && G.arc[k][j]<lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n",sum);
}

三、kruskal(克魯斯卡爾)算法

1、思路

• 將鄰接矩陣 轉(zhuǎn)化成 邊表數(shù)組;
• 對邊表數(shù)組根據(jù)權(quán)值按照從?到?的順序排序;
• 遍歷所有的邊, 通過parent 數(shù)組找到邊的連接信息; 避免閉環(huán)問題;
• 如果不存在閉環(huán)問題,則加?到最??成樹中. 并且修改parent 數(shù)組

2、代碼實現(xiàn)

邊表數(shù)組Edge結(jié)構(gòu)的定義

typedef struct
{
  int begin;
  int end;
  int weight;
}Edge;

根據(jù)權(quán)值進(jìn)行排序

void sort(Edge edges[],MGraph G)
{
  //對權(quán)值進(jìn)行排序(從小到大)
  int i, j;
  Edge temp;
  for ( i = 0; i < G.numEdges; i++)
  {
      for ( j = i + 1; j < G.numEdges; j++)
      {
          if (edges[i].weight > edges[j].weight)
          {
              temp = edges[i];
              edges[i] = edges[j];
              edges[j] = temp;
          }
      }
  }
  
  printf("邊集數(shù)組根據(jù)權(quán)值排序之后的為:\n");
  for (i = 0; i < G.numEdges; i++)
  {
      printf("v%d - v%d = %d\n", edges[i].begin, edges[i].end, edges[i].weight);
  }
}

根據(jù)頂點f以及parent數(shù)組,可以找到當(dāng)前頂點的尾部下標(biāo); 幫助我們判斷兩點之間是否存在閉環(huán)問題

int Find(int *parent, int f)
{
  while ( parent[f] > 0)
  {
      f = parent[f];
  }
  return f;
}

kruskal算法

void MiniSpanTree_Kruskal(MGraph G){
  int sum = 0;
  /* 定義一數(shù)組用來判斷邊與邊是否形成環(huán)路,用來記錄頂點間的連接關(guān)系. 通過它來防止最小生成樹產(chǎn)生閉環(huán);*/
  int parent[MAXVEX];
  //邊表數(shù)組
  Edge edges[MAXVEX];
  int k = 0;
  //根據(jù)鄰接矩陣生成邊表數(shù)組
  for (int i = 0; i<G.numNodes; i++) {
      for (int j = i+1; j<G.numNodes; j++) {
          if (G.arc[i][j]<INFINITYC) {
              edges[k].begin = i;
              edges[k].end = j;
              edges[k].weight = G.arc[i][j];
              k++;
          }
      }
  }
  
  //將邊表數(shù)組排序
  sort(edges, G);
  
  //初始化parent 值為0
  for (int i = 0; i<MAXVEX; i++) {
      parent[i] = 0;
  }
  int n,m;
  for (int i = 0; i<G.numEdges; i++) {
      n = Find(parent, edges[i].begin);
      m = Find(parent, edges[i].end);
      if (n != m) {
          parent[n] = m; //更新parent數(shù)組
          //非閉環(huán)情況下，且根據(jù)權(quán)值從小到大的排序邊表數(shù)組，此時的邊i是沒有加入到生成樹的最小邊
          sum  += edges[i].weight; //邊i加入的生成樹
      }
  }
  printf("sum = %d\n",sum);
}