최소 스패닝 트리 (MST) 또는 가중 연결 무방향 그래프에 대한 최소 가중치 스패닝 트리는 가중치가 다른 모든 스패닝 트리의 가중치보다 작거나 같은 스패닝 트리입니다. 최소 스패닝 트리에 대해 자세히 알아보려면 다음을 참조하세요. 이 기사 .
크루스칼 알고리즘 소개:
여기서 우리는 논의할 것입니다 크루스칼의 알고리즘 주어진 가중치 그래프의 MST를 찾습니다.
크루스칼 알고리즘에서는 주어진 그래프의 모든 가장자리를 오름차순으로 정렬합니다. 그런 다음 새로 추가된 가장자리가 순환을 형성하지 않으면 MST에 새 가장자리와 노드를 계속 추가합니다. 처음에는 최소 가중치 간선을 선택하고 마지막에는 최대 가중치 간선을 선택합니다. 따라서 최적의 해를 찾기 위해 각 단계에서 국지적으로 최적의 선택을 한다고 말할 수 있습니다. 따라서 이것은 다음은 Kruskal 알고리즘을 사용하여 MST를 찾는 단계입니다.
- 가중치가 감소하지 않는 순서로 모든 모서리를 정렬합니다.
- 가장 작은 가장자리를 선택합니다. 지금까지 형성된 스패닝 트리와 순환을 형성하는지 확인합니다. 순환이 형성되지 않은 경우 이 간선을 포함합니다. 그렇지 않으면 폐기하십시오.
- 스패닝 트리에 (V-1) 에지가 있을 때까지 2단계를 반복합니다.
2 단계 을 사용합니다 Union-Find 알고리즘 주기를 감지합니다.
따라서 전제 조건으로 다음 게시물을 읽어 보는 것이 좋습니다.
- Union-Find 알고리즘 | 세트 1(그래프에서 주기 감지)
- Union-Find 알고리즘 | 세트 2(순위 및 경로 압축별 통합)
최소 비용 스패닝 트리를 찾는 Kruskal의 알고리즘은 탐욕적 접근 방식을 사용합니다. Greedy Choice는 지금까지 구성한 MST에서 Cycle을 일으키지 않는 가장 작은 가중치 Edge를 선택하는 것입니다. 예를 들어 이해해 보겠습니다.
삽화:
다음은 위 접근 방식의 그림입니다.
입력 그래프:
그래프에는 9개의 꼭짓점과 14개의 간선이 포함되어 있습니다. 따라서 형성된 최소 스패닝 트리는 (9 – 1) = 8개의 모서리를 갖게 됩니다.
정렬 후:문자열 비교 C#
무게 원천 목적지 1 7 6 2 8 2 2 6 5 4 0 1 4 2 5 6 8 6 7 2 삼 7 7 8 8 0 7 8 1 2 9 삼 4 10 5 4 열하나 1 7 14 삼 5 이제 정렬된 가장자리 목록에서 모든 가장자리를 하나씩 선택하세요.
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>> edgelist; 정수 V; 공개: 그래프(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 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; // 두 세트의 순위가 동일할 경우 // 순위가 증가하므로 순위[u]++; } } // MST를 찾는 함수 void kruskalAlgo(int n, int edge[n][3]) { // 먼저 가장자리 배열을 오름차순으로 정렬하여 // 최소 거리/비용에 액세스할 수 있도록 합니다. qsort(edge , n, sizeof(edge[0]), 비교기); int 부모[n]; 정수 순위[n]; // parent[] 및 Rank[]를 초기화하는 함수 makeSet(parent, Rank, n); // 최소 비용을 저장하려면 int minCost = 0; printf( '다음은 구성된 MST의 가장자리입니다
'); for (int i = 0; i int v1 = findParent(parent, edge[i][0]); int v2 = findParent(parent, edge[i][1]); int wt = edge[i][2] ; // 부모가 다르면 // 서로 다른 세트에 있음을 의미하므로 // 결합합니다. if (v1 != v2) { UnionSet(v1, v2, parent, Rank, n) minCost += wt; '%d -- %d == %d
', edge[i][0], edge[i][1], wt) } } printf('최소 비용 스패닝 트리: %d n', minCost); } // 드라이버 코드 int main() { int edge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } }; kruskalAlgo(5, edge) }> |
>
>
자바
// 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> |
>
>
파이썬3
# 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]>순위[y]: parent[y] = x # 순위가 동일하면 루트로 순위를 만들고 # 순위를 하나씩 증가시킵니다. else: parent[y] = x 순위[x] += 1 # 구성할 주요 함수 MST # Kruskal 알고리즘 사용 def KruskalMST(self): # 결과 MST 결과가 저장됩니다. = [] # 정렬된 가장자리에 사용되는 인덱스 변수 i = 0 # 결과에 사용되는 인덱스 변수[] e = 0 # 가중치가 감소하지 않는 순서로 # 모든 간선을 정렬합니다 # self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] 순위 = [] # 단일 요소로 V 하위 집합을 만듭니다. for node in range(self.V): parent.append(node) Rank.append(0) # 취할 간선의 수는 V-1보다 작습니다. while e |
>
>
씨#
// 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; // 순위가 동일하면 하나를 루트로 만들고 // 순위를 하나씩 증가시킵니다. else { 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 최소 비용 = 0; for (i = 0; i Console.WriteLine(result[i].src + ' -- ' + result[i].dest + ' == ' + result[i].weight); 최소 비용 += result[i].weight; } Console.WriteLine('최소 비용 스패닝 트리: ' + maximumCost); Console.ReadLine() } // 드라이버의 코드 public static void Main(String[] args) int V = 4; int E = 5; 그래프 그래프 = new Graph(V, E); // 가장자리 0-1 추가 graph.edge[0].src = 0; graph.edge[0].weight = 10; // 모서리 0~2 추가 graph.edge[1].src = 0; graph.edge[1].weight = 6 ; // 가장자리 0-3 추가 graph.edge[2].src = 0; graph.edge[2].weight = 5; edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 15; // 에지 2-3 추가 graph.edge[4].src = 2; .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)=>{ return a[2] - b[2]; }) //내장된 빠른 정렬 기능은 stdlib.h와 함께 제공됩니다. //https://www.techcodeview.com로 이동합니다. 모서리 정렬에는 O(E * logE) 시간이 걸립니다. 정렬 후에는 모든 모서리를 반복하고 find-union 알고리즘을 적용합니다. 찾기 및 결합 작업에는 최대 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 팀이 검토했습니다.>