Kruskal의 최소 스패닝 트리 알고리즘

연결된 그래프 G(V, E)가 있고 모든 모서리에 대한 가중치 또는 비용이 제공됩니다. Kruskal의 알고리즘은 그래프와 비용을 사용하여 최소 스패닝 트리를 찾습니다.

병합 트리 접근 방식입니다. 처음에는 다른 트리가 있는데 이 알고리즘은 비용이 최소인 가장자리를 취하여 병합하여 단일 트리를 형성합니다.

이 문제에서는 모든 간선이 비용에 따라 나열되고 정렬됩니다. 리스트에서 최소 비용의 edge를 뽑아서 트리에 추가하고, edge가 형성되는 주기를 체크하고 순환을 형성하면 list에서 edge를 버리고 다음 edge로 넘어간다. /P>

이 알고리즘의 시간 복잡도는 O(E log E) 또는 O(E log V)이며, 여기서 E는 에지의 개수이고 V는 정점의 개수입니다.

입력 및 출력

Input:
Adjacency matrix

Output:
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;

//Cost matrix of the graph
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) {
   //merge two vertex sets together
   while(set2.n >= 0)
      set1.addVertex(set2.deleteVertex());
      //addToSet(vSet1, delFromSet(vSet2));
}

int findVertex(VSet *vertSetArr, int vert) {
   //find the vertex in different vertex sets
   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) {
   //find the edges from the cost matrix of Graph and store to edgeList
   int count = -1, i, j;
   for(i = 0; i<V; i++)
      for(j = 0; j<i; j++)
         if(costMat[i][j] != INF) {
            count++;
            //fill edge list for the position 'count'
            edgeList[count].u = i; edgeList[count].v = j;
            edgeList[count].cost = costMat[i][j];
         }
   return count+1;
}

void sortEdge(edge *edgeList, int n) {
   //sort the edges of graph in ascending order of cost
   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