Kruskal的最小生成树算法

有一个连通图G(V,E)并给出了每个边的权重或成本。Kruskal的算法将使用图形和成本找到最小生成树。

这是合并树方法。最初，有不同的树，此算法将采用成本最小的那些边合并它们，并形成一棵树。

在此问题中，所有边均根据其成本列出并排序。从列表中，取出成本最低的边并添加到树中，然后每一次检查是否形成边，如果形成一个循环，则从列表中丢弃边并移至下一条边。

该算法的时间复杂度为O（E log E）或O（E log V），其中E是许多边，V是许多顶点。

输入输出

Input:
Adjacency matrixOutput:
Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15

算法

kruskal(g: Graph, t: Tree)

输入-给定图g和空树t

输出-具有选定边的树t

Begin
   create set for each vertices in graph g
   for each set of vertex u do
      add u in the vertexSet[u]
   done

   sort the edge list.
   count := 0
   while count <= V – 1 do    //as tree must have V – 1 edges
      ed := edgeList[count]   //take an edge from edge list
      if the starting vertex and ending vertex of ed are in same set then
         merge vertexSet[start] and vertexSet[end]
         add the ed into tree t
      count := count +1
   done
End

示例

#include<iostream>
#define V 7
#define INF 999
using namespace std;

//图的成本矩阵
int costMat[V][V] = {
   {0, 1, 3, 4, INF, 5, INF},
   {1, 0, INF, 7, 2, INF, INF},
   {3, INF, 0, INF, 8, INF, INF},
   {4, 7, INF, 0, INF, INF, INF},
   {INF, 2, 8, INF, 0, 2, 4},
   {5, INF, INF, INF, 2, 0, 3},
   {INF, INF, INF, INF, 4, 3, 0}
};

typedef struct {
   int u, v, cost;
}edge;

void swapping(edge &e1, edge &e2) {
   edge temp;
   temp = e1;
   e1 = e2;
   e2 = temp;
}

class Tree {
   int n;
   edge edges[V-1];    //as a tree has vertex-1 edges
   public:
      Tree() {
         n = 0;
      }

      void addEdge(edge e) {
         edges[n] = e;   //add edge e into the tree
         n++;
      }

      void printEdges() {    //print edge, cost and total cost
         int tCost = 0;

         for(int i = 0; i<n; i++) {
            cout << "Edge: " << char(edges[i].u+'A') << "--" <<char(edges[i].v+'A');
            cout << " And Cost: " << edges[i].cost << endl;
            tCost += edges[i].cost;
         }
         cout << "Total Cost: " << tCost << endl;
      }
};

class VSet {
   int n;
   int set[V];    //a set can hold maximum V vertices
   public:
      VSet() {
         n = -1;
      }

      void addVertex(int vert) {
         set[++n] = vert;    //add vertex to the set
      }

      int deleteVertex() {
         return set[n--];
      }

      friend int findVertex(VSet *vertSetArr, int vert);
      friend void merge(VSet &set1, VSet &set2);
};

void merge(VSet &set1, VSet &set2) {
   //将两个顶点集合并在一起
   while(set2.n >= 0)
      set1.addVertex(set2.deleteVertex());
      //addToSet（vSet1，delFromSet(vSet2)）; 
}

int findVertex(VSet *vertSetArr, int vert) {
   //在不同的顶点集中找到顶点
   for(int i = 0; i<V; i++)
      for(int j = 0; j<=vertSetArr[i].n; j++)
         if(vert == vertSetArr[i].set[j])
            return i;   //node found in i-th vertex set
}

int findEdge(edge *edgeList) {
   //从Graph的成本矩阵中找到边并存储到edgeList-
   int count = -1, i, j;
   for(i = 0; i<V; i++)
      for(j = 0; j<i; j++)
         if(costMat[i][j] != INF) {
            count++;
            //填充位置“计数”的边缘列表
            edgeList[count].u = i; edgeList[count].v = j;
            edgeList[count].cost = costMat[i][j];
         }
   return count+1;
}

void sortEdge(edge *edgeList, int n) {
   //以成本的升序对图的边缘进行排序
   int flag = 1, i, j;

   for(i = 0; i<(n-1) && flag; i++) {   //modified bubble sort is used
      flag = 0;
      for(j = 0; j<(n-i-1); j++)
         if(edgeList[j].cost > edgeList[j+1].cost) {
            swapping(edgeList[j], edgeList[j+1]);
            flag = 1;
         }
   }
}

void kruskal(Tree &tr) {
   int ecount, maxEdge = V*(V-1)/2;   //max n(n-1)/2 edges can have in a graph
   edge edgeList[maxEdge], ed;
   int uloc, vloc;
   VSet VSetArray[V];
   ecount = findEdge(edgeList);

   for(int i = 0; i < V; i++)
      VSetArray[i].addVertex(i);    //each set contains one element
   sortEdge(edgeList, ecount);      //ecount number of edges in the graph
   int count = 0;

   while(count <= V-1) {
      ed = edgeList[count];
      uloc = findVertex(VSetArray, ed.u);
      vloc = findVertex(VSetArray, ed.v);

      if(uloc != vloc) {    //check whether source abd dest is in same set or not
         merge(VSetArray[uloc], VSetArray[vloc]);
         tr.addEdge(ed);
      }
      count++;
   }
}

int main() {
   Tree tr;
   kruskal(tr);
   tr.printEdges();
}

输出结果

Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15