KRUSKAL の最小スパニングツリー (MST) アルゴリズム

最小のスパニングツリー (MST) または重み付き接続無向グラフの最小重みスパニングツリーは、他のすべてのスパニングツリーの重み以下の重みを持つスパニングツリーです。ミニマムスパニングツリーの詳細については、を参照してください。 この記事 。

クラスカルのアルゴリズムの紹介:

ここで議論します クラスカルのアルゴリズム 指定された重み付きグラフの MST を見つけます。

クラスカルのアルゴリズムでは、指定されたグラフのすべてのエッジを昇順に並べ替えます。その後、新しく追加されたエッジがサイクルを形成しない場合は、MST に新しいエッジとノードを追加し続けます。最初に最小の重み付けされたエッジが選択され、最後に最大の重み付けされたエッジが選択されます。したがって、最適な解決策を見つけるために、各ステップで局所的に最適な選択が行われると言えます。したがって、これは以下は、Kruskal のアルゴリズムを使用して MST を見つける手順です。

すべてのエッジを重みの降順に並べ替えます。
最小のエッジを選択します。これまでに作成したスパニングツリーとサイクルを形成しているか確認してください。サイクルが形成されていない場合は、このエッジを含めます。それ以外の場合は破棄してください。
スパニングツリーに (V-1) 個のエッジができるまでステップ #2 を繰り返します。

ステップ2 を使用します Union-Find アルゴリズムサイクルを検出します。

したがって、前提条件として次の投稿を読むことをお勧めします。

ユニオン検索アルゴリズム |セット 1 (グラフ内の周期を検出)

ユニオン検索アルゴリズム |セット 2 (ランクによる結合とパス圧縮)

最小コストのスパニングツリーを見つける Kruskal のアルゴリズムでは、貪欲なアプローチが使用されます。貪欲な選択は、これまでに構築された MST でサイクルを引き起こさない最小の重みエッジを選択することです。例を挙げて理解してみましょう。

図：

以下に上記のアプローチを図示します。

入力グラフ:

グラフには 9 つの頂点と 14 のエッジが含まれています。したがって、形成される最小スパニングツリーは (9 – 1) = 8 つのエッジを持つことになります。
並べ替え後:

重さソース行き先

1 7 6

2 8 2

2 6 5

4 0 1

4 2 5

6 8 6

7 2 3

7 7 8

8 0 7

8 1 2

9 3 4

10 5 4

十一 1 7

14 3 5

次に、ソートされたエッジのリストからすべてのエッジを 1 つずつ選択します。

ステップ1： エッジ7-6をピックします。サイクルは形成されません、それを含めてください。

MST にエッジ 7-6 を追加

ステップ2： ピックエッジ8-2。 サイクルは形成されません、それを含めてください。

MST にエッジ 8-2 を追加

ステップ 3: エッジ6-5をピックします。 サイクルは形成されません、それを含めてください。

MST にエッジ 6-5 を追加

ステップ 4: エッジ 0-1 を選択します。 サイクルは形成されません、それを含めてください。

MST にエッジ 0-1 を追加

ステップ5: エッジ 2-5 を選択します。 サイクルは形成されません、それを含めてください。

MST にエッジ 2 ～ 5 を追加

ステップ6: エッジ8-6をピックします。 このエッジを含めるとサイクルが発生するため、破棄します。 エッジ 2 ～ 3 を選択します。 サイクルは形成されません、それを含めてください。

MST にエッジ 2 ～ 3 を追加

ステップ 7: エッジ7-8をピックします。 このエッジを含めるとサイクルが発生するため、破棄します。 エッジ 0 ～ 7 を選択します。 サイクルは形成されません、それを含めてください。

MST にエッジ 0 ～ 7 を追加

ステップ8: エッジ 1-2 を選択します。 このエッジを含めるとサイクルが発生するため、破棄します。 エッジ3-4をピックします。 サイクルは形成されません、それを含めてください。

MST にエッジ 3 ～ 4 を追加

注記： MST に含まれるエッジの数は (V – 1) に等しいため、アルゴリズムはここで停止します。

上記のアプローチの実装を以下に示します。

C++

// C++ program for the above approach> > #include> using> namespace> std;> > // DSU data structure> // path compression + rank by union> class> DSU {> > int> * parent;> > int> * rank;> > public> :> > DSU(> int> n)> > {> > parent => new> int> [n];> > rank => new> int> [n];> > > for> (> int>

i = 0; i   parent[i] = -1;   rank[i] = 1;   }   }     // Find function   int find(int i)   {   if (parent[i] == -1)   return i;     return parent[i] = find(parent[i]);   }     // Union function   void unite(int x, int y)   {   int s1 = find(x);   int s2 = find(y);     if (s1 != s2) {   if (rank[s1]   parent[s1] = s2;   }   else if (rank[s1]>ランク[s2]) { 親[s2] = s1;   } else {親[s2] = s1;   ランク[s1] += 1;   } } } };    クラス グラフ { Vectorint>> エッジリスト;   テレビで;    public: Graph(int V) { this->V = V; } // グラフにエッジを追加する関数 void addEdge(int x, int y, int w) {edgelist.push_back({ w, x, y });   } void kruskals_mst() { // すべてのエッジをソート sort(edgelist.begin(),edgelist.end());     // DSU を初期化します DSU s(V);   int ans = 0;   コート < < 'Following are the edges in the '  'constructed MST'   < < endl;   for (auto edge : edgelist) {   int w = edge[0];   int x = edge[1];   int y = edge[2];     // Take this edge in MST if it does   // not forms a cycle   if (s.find(x) != s.find(y)) {   s.unite(x, y);   ans += w;   cout  < < x  < < ' -- '  < < y  < < ' == '  < < w    < < endl;   }   }   cout  < < 'Minimum Cost Spanning Tree: '  < < ans;   }  };    // Driver code  int main()  {   Graph g(4);   g.addEdge(0, 1, 10);   g.addEdge(1, 3, 15);   g.addEdge(2, 3, 4);   g.addEdge(2, 0, 6);   g.addEdge(0, 3, 5);     // Function call   g.kruskals_mst();     return 0;  }>

C

// C code to implement Kruskal's algorithm> > #include> #include> > // Comparator function to use in sorting> int> comparator(> const> void> * p1,> const> void> * p2)> {> > const> int> (*x)[3] = p1;> > const> int> (*y)[3] = p2;> > > return> (*x)[2] - (*y)[2];> }> > // Initialization of parent[] and rank[] arrays> void> makeSet(> int> parent[],> int> rank[],> int> n)> {> > for> (> int>

i = 0; i   parent[i] = i;   rank[i] = 0;   }  }    // Function to find the parent of a node  int findParent(int parent[], int component)  {   if (parent[component] == component)   return component;     return parent[component]   = findParent(parent, parent[component]);  }    // Function to unite two sets  void unionSet(int u, int v, int parent[], int rank[], int n)  {   // Finding the parents   u = findParent(parent, u);   v = findParent(parent, v);     if (rank[u]   parent[u] = v;   }   else if (rank[u]>ランク[v]) { 親[v] = u;   } else {親[v] = u;     // 2 つのセットのランクが同じ場合、 // ランクは増加するため、 Rank[u]++;   } } // MST を見つける関数 void kruskalAlgo(int n, intedge[n][3]) { // まず、最小距離/コストにアクセスできるように、 // エッジ配列を昇順にソートします。 qsort(edge 、n、sizeof(edge[0])、コンパレータ);     int 親[n];   int ランク[n];     //parent[]とrank[]を初期化する関数 makeSet(parent,rank,n);     // 最小コストを保存するには int minCost = 0;     printf( '以下は構築された MST のエッジです
');   for (int i = 0; i int v1 = findParent(親, エッジ[i][0]); int v2 = findParent(親, エッジ[i][1]); int wt = エッジ[i][2] ; // 親が異なる場合は、 // それらが異なるセットにあることを意味しますので、 // それらを結合します if (v1, v2,parent, Rank, n); '%d -- %d == %d
',edge[i][0],edge[i][1], wt) } } printf('最小コストスパニングツリー: %d n', minCost); } // ドライバーコード int main() { intedge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } }; 戻り値 0;

>    
      
      
       
   
       
       
     
     
   
          // Java program for Kruskal's algorithm>   >   import>   java.util.ArrayList;>   import>   java.util.Comparator;>   import>   java.util.List;>   >   public>   class>   KruskalsMST {>   >   >  // Defines edge structure>   >  static>   class>   Edge {>   >  int>   src, dest, weight;>   >   >  public>   Edge(>  int>   src,>  int>   dest,>  int>   weight)>   >  {>   >  this>  .src = src;>   >  this>  .dest = dest;>   >  this>  .weight = weight;>   >  }>   >  }>   >   >  // Defines subset element structure>   >  static>   class>   Subset {>   >  int>   parent, rank;>   >   >  public>   Subset(>  int>   parent,>  int>   rank)>   >  {>   >  this>  .parent = parent;>   >  this>  .rank = rank;>   >  }>   >  }>   >   >  // Starting point of program execution>   >  public>   static>   void>   main(String[] args)>   >  {>   >  int>   V =>  4>  ;>   >  List graphEdges =>  new>   ArrayList(>   >  List.of(>  new>   Edge(>  0>  ,>  1>  ,>  10>  ),>  new>   Edge(>  0>  ,>  2>  ,>  6>  ),>   >  new>   Edge(>  0>  ,>  3>  ,>  5>  ),>  new>   Edge(>  1>  ,>  3>  ,>  15>  ),>   >  new>   Edge(>  2>  ,>  3>  ,>  4>  )));>   >   >  // Sort the edges in non-decreasing order>   >  // (increasing with repetition allowed)>   >  graphEdges.sort(>  new>   Comparator() {>   >  @Override>   public>   int>   compare(Edge o1, Edge o2)>   >  {>   >  return>   o1.weight - o2.weight;>   >  }>   >  });>   >   >  kruskals(V, graphEdges);>   >  }>   >   >  // Function to find the MST>   >  private>   static>   void>   kruskals(>  int>   V, List edges)>   >  {>   >  int>   j =>  0>  ;>   >  int>   noOfEdges =>  0>  ;>   >   >  // Allocate memory for creating V subsets>   >  Subset subsets[] =>  new>   Subset[V];>   >   >  // Allocate memory for results>   >  Edge results[] =>  new>   Edge[V];>   >   >  // Create V subsets with single elements>   >  for>   (>  int>   i =>  0>  ; i   subsets[i] = new Subset(i, 0);   }     // Number of edges to be taken is equal to V-1   while (noOfEdges 1) {     // Pick the smallest edge. And increment   // the index for next iteration   Edge nextEdge = edges.get(j);   int x = findRoot(subsets, nextEdge.src);   int y = findRoot(subsets, nextEdge.dest);     // If including this edge doesn't cause cycle,   // include it in result and increment the index   // of result for next edge   if (x != y) {   results[noOfEdges] = nextEdge;   union(subsets, x, y);   noOfEdges++;   }     j++;   }     // Print the contents of result[] to display the   // built MST   System.out.println(   'Following are the edges of the constructed MST:');   int minCost = 0;   for (int i = 0; i   System.out.println(results[i].src + ' -- '  + results[i].dest + ' == '  + results[i].weight);   minCost += results[i].weight;   }   System.out.println('Total cost of MST: ' + minCost);   }     // Function to unite two disjoint sets   private static void union(Subset[] subsets, int x,   int y)   {   int rootX = findRoot(subsets, x);   int rootY = findRoot(subsets, y);     if (subsets[rootY].rank   subsets[rootY].parent = rootX;   }   else if (subsets[rootX].rank     subsets[rootX].parent = rootY;   }   else {   subsets[rootY].parent = rootX;   subsets[rootX].rank++;   }   }     // Function to find parent of a set   private static int findRoot(Subset[] subsets, int i)   {   if (subsets[i].parent == i)   return subsets[i].parent;     subsets[i].parent   = findRoot(subsets, subsets[i].parent);   return subsets[i].parent;   }  }  // This code is contributed by Salvino D'sa>    
  
  
   
      
    
      
    
  Python3 
      
       
   
       
       
     
     
   
          # Python program for Kruskal's algorithm to find>   # Minimum Spanning Tree of a given connected,>   # undirected and weighted graph>   >   >   # Class to represent a graph>   class>   Graph:>   >   >  def>   __init__(>  self>  , vertices):>   >  self>  .V>  =>   vertices>   >  self>  .graph>  =>   []>   >   >  # Function to add an edge to graph>   >  def>   addEdge(>  self>  , u, v, w):>   >  self>  .graph.append([u, v, w])>   >   >  # A utility function to find set of an element i>   >  # (truly uses path compression technique)>   >  def>   find(>  self>  , parent, i):>   >  if>   parent[i] !>  =>   i:>   >   >  # Reassignment of node's parent>   >  # to root node as>   >  # path compression requires>   >  parent[i]>  =>   self>  .find(parent, parent[i])>   >  return>   parent[i]>   >   >  # A function that does union of two sets of x and y>   >  # (uses union by rank)>   >  def>   union(>  self>  , parent, rank, x, y):>   >   >  # Attach smaller rank tree under root of>   >  # high rank tree (Union by Rank)>   >  if>   rank[x]   parent[x] = y   elif rank[x]>Rank[y]:parent[y] = x #ランクが同じ場合、ルートとして 1 つを作成し、他の 1 つだけそのランクをインクリメントします:parent[y] = x Rank[x] += 1 #構築するメイン関数MST # Kruskal のアルゴリズムを使用します def KruskalMST(self): # これは MST の結果を保存します result = [] # ソートされたエッジに使用されるインデックス変数 i = 0 # result[] に使用されるインデックス変数 e = 0 # すべてのエッジを # 重みの非減少順にソートします self.graph =sorted(self.graph, key=lambda item: item[2])parent = [] Rank = [] # 単一の要素を持つ V 個のサブセットを作成しますfor node in range(self.V):parent.append(node)rank.append(0) # 取得されるエッジの数は V-1 未満ですが、e     
  
  
   
      
    
      
    
  C# 
      
       
   
       
       
     
     
   
          // C# Code for the above approach>   >   using>   System;>   >   class>   Graph {>   >   >  // A class to represent a graph edge>   >  class>   Edge : IComparable {>   >  public>   int>   src, dest, weight;>   >   >  // Comparator function used for sorting edges>   >  // based on their weight>   >  public>   int>   CompareTo(Edge compareEdge)>   >  {>   >  return>   this>  .weight - compareEdge.weight;>   >  }>   >  }>   >   >  // A class to represent>   >  // a subset for union-find>   >  public>   class>   subset {>   >  public>   int>   parent, rank;>   >  };>   >   >  // V->いいえ。頂点の数 & E-> エッジの数>>   >  int>   V, E;>   >   >  // Collection of all edges>   >  Edge[] edge;>   >   >  // Creates a graph with V vertices and E edges>   >  Graph(>  int>   v,>  int>   e)>   >  {>   >  V = v;>   >  E = e;>   >  edge =>  new>   Edge[E];>   >  for>   (>  int>   i = 0; i   edge[i] = new Edge();   }     // A utility function to find set of an element i   // (uses path compression technique)   int find(subset[] subsets, int i)   {   // Find root and make root as   // parent of i (path compression)   if (subsets[i].parent != i)   subsets[i].parent   = find(subsets, subsets[i].parent);     return subsets[i].parent;   }     // A function that does union of   // two sets of x and y (uses union by rank)   void Union(subset[] subsets, int x, int y)   {   int xroot = find(subsets, x);   int yroot = find(subsets, y);     // Attach smaller rank tree under root of   // high rank tree (Union by Rank)   if (subsets[xroot].rank   subsets[xroot].parent = yroot;   else if (subsets[xroot].rank>サブセット[yroot].rank) サブセット[yroot].parent = xroot;     // ランクが同じ場合は、ルートとして 1 つを作成し、 // ランクを 1 つ増やします。 { subsets[yroot].parent = xroot;   サブセット[xroot].rank++;   } } // MST を構築するメイン関数 // Kruskal のアルゴリズムを使用して void KruskalMST() { // これにより、 // 結果の MST が保存されます Edge[] result = new Edge[V];     // result[] int e = 0; に使用されるインデックス変数。     // ソートされたエッジに使用されるインデックス変数 int i = 0;   for (i = 0; i result[i] = new Edge(); // すべてのエッジを重みの減少しない順に並べ替えます。 // 指定されたグラフを変更することが許可されていない場合は、 // を作成できます。 // エッジの配列のコピー Array.Sort(edge); // V のサブセットを作成するためにメモリを割り当てます subset[] subsets = new subset[V] for (i = 0; i subsets[i] = new subset(); ; // 単一要素を持つ V 個のサブセットを作成 for (int v = 0; v subsets[v].parent = v; subsets[v].rank = 0; } i = 0; // 取得されるエッジの数は等しいto V-1 while (e // 最小のエッジを選択します。そして、 // 次の反復のインデックスをインクリメントします Edge next_edge = new Edge(); next_edge =edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); // このエッジを含めても循環が発生しない場合、 // 結果に含めて、次のエッジの結果のインデックスを // if (x != y) { result[e++] = next_edge; Union(subsets, x, y); } } // result[] の内容を出力して、 // 構築された MST Console.WriteLine('以下は ' + '構築された MST');     int minimumCost = 0;   for (i = 0; i Console.WriteLine(result[i].src + ' -- ' + result[i].dest + ' == ' + result[i].weight); minimumCost += result[i].weight; } Console.WriteLine('最小コスト スパニング ツリー: ' + minimumCost); // ドライバーのコード public static void Main(String[] args); int V = 4; int E = 5; グラフ chart = new Graph(V, E); // エッジ 0-1 を追加します。 chart.edge[0].weight = 10; // エッジ 0-2 を追加します。graph.edge[1].dest = 2; ; // エッジ 0-3 を追加します。graph.edge[2].src = 0;graph.edge[2].weight = 5; // エッジ 1-3 のグラフを追加します。 edge[3].src = 1;graph.edge[3].dest = 3; // エッジ 2-3 を追加します。 .edge[4].dest = 3;graph.edge[4].weight = 4; // 関数呼び出しgraph.KruskalMST() } } // このコードは Aakash Hasija によって提供されています。    
  
  
   
      
  >    
      
      
       
   
       
       
     
     
   
          >   // JavaScript implementation of the krushkal's algorithm.>   >   function>   makeSet(parent,rank,n)>   {>   >  for>  (let i=0;i  {   parent[i]=i;   rank[i]=0;   }  }    function findParent(parent,component)  {   if(parent[component]==component)   return component;     return parent[component] = findParent(parent,parent[component]);  }    function unionSet(u, v, parent, rank,n)  {   //this function unions two set on the basis of rank   //as shown below   u=findParent(parent,u);   v=findParent(parent,v);     if(rank[u]  {   parent[u]=v;   }   else if(rank[u]  {   parent[v]=u;   }   else  {   parent[v]=u;   rank[u]++;//since the rank increases if the ranks of two sets are same   }  }    function kruskalAlgo(n, edge)  {   //First we sort the edge array in ascending order   //so that we can access minimum distances/cost   edge.sort((a, b)=>{ a[2] - b[2] を返します;   }) // 組み込みのクイック ソート関数は stdlib.h に付属しています // https://www.techcodeview.com に移動します エッジのソートには O(E * logE) 時間がかかります。  ソート後、すべてのエッジを反復処理し、結合検索アルゴリズムを適用します。検索操作と結合操作には最大で O(logV) 時間がかかります。したがって、全体の複雑さは O(E * logE + E * logV) 時間です。  E の値は最大でも O(V2) であるため、O(logV) と O(logE) は同じです。したがって、全体の時間計算量は O(E * logE) または O(E*logV) 補助空間: O(V + E) になります。ここで、V は頂点の数、E はグラフ内のエッジの数です。この記事は Aashish Barnwal によって編集され、techcodeview.com チームによってレビューされました。>>