-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathkruskal-s-algorithm.html
More file actions
128 lines (111 loc) · 26.6 KB
/
kruskal-s-algorithm.html
File metadata and controls
128 lines (111 loc) · 26.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Kruskal's Algorithm</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Optimal, disjoint-set based implementation, Simple, more detailed implementation, Simple, disjoint-set based implementation, Simple, high level implementation">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Kruskal's Algorithm">
<meta property="og:description" content="Optimal, disjoint-set based implementation, Simple, more detailed implementation, Simple, disjoint-set based implementation, Simple, high level implementation">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/kruskal-s-algorithm.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Kruskal's Algorithm">
<meta name="twitter:description" content="Optimal, disjoint-set based implementation, Simple, more detailed implementation, Simple, disjoint-set based implementation, Simple, high level implementation">
<meta name="twitter:url" content="/algorithm/kruskal-s-algorithm.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/48.0bbbed97.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" aria-current="page" class="active sidebar-link">Kruskal's Algorithm</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/kruskal-s-algorithm.html#optimal-disjoint-set-based-implementation" class="sidebar-link">Optimal, disjoint-set based implementation</a></li><li class="sidebar-sub-header"><a href="/algorithm/kruskal-s-algorithm.html#simple-more-detailed-implementation" class="sidebar-link">Simple, more detailed implementation</a></li><li class="sidebar-sub-header"><a href="/algorithm/kruskal-s-algorithm.html#simple-disjoint-set-based-implementation" class="sidebar-link">Simple, disjoint-set based implementation</a></li><li class="sidebar-sub-header"><a href="/algorithm/kruskal-s-algorithm.html#simple-high-level-implementation" class="sidebar-link">Simple, high level implementation</a></li></ul></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="kruskal-s-algorithm"><a href="#kruskal-s-algorithm" class="header-anchor">#</a> Kruskal's Algorithm</h1> <h2 id="optimal-disjoint-set-based-implementation"><a href="#optimal-disjoint-set-based-implementation" class="header-anchor">#</a> Optimal, disjoint-set based implementation</h2> <p>We can do two things to improve the simple and sub-optimal disjoint-set subalgorithms:</p> <li>
**Path compression heuristic**: `findSet` does not need to ever handle a tree with height bigger than `2`. If it ends up iterating such a tree, it can link the lower nodes directly to the root, optimizing future traversals;
<div class="language-cpp extra-class"><pre class="language-cpp"><code>subalgo <span class="token function">findSet</span><span class="token punctuation">(</span>v<span class="token operator">:</span> a node<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> v<span class="token punctuation">.</span>parent <span class="token operator">!=</span> v
v<span class="token punctuation">.</span>parent <span class="token operator">=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>v<span class="token punctuation">.</span>parent<span class="token punctuation">)</span>
<span class="token keyword">return</span> v<span class="token punctuation">.</span>parent
</code></pre></div></li> <li>
**Height-based merging heuristic**: for each node, store the height of its subtree. When merging, make the taller tree the parent of the smaller one, thus not increasing anyone's height.
<div class="language-cpp extra-class"><pre class="language-cpp"><code>subalgo <span class="token function">unionSet</span><span class="token punctuation">(</span>u<span class="token punctuation">,</span> v<span class="token operator">:</span> nodes<span class="token punctuation">)</span><span class="token operator">:</span>
vRoot <span class="token operator">=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span>
uRoot <span class="token operator">=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span>
<span class="token keyword">if</span> vRoot <span class="token operator">==</span> uRoot<span class="token operator">:</span>
<span class="token keyword">return</span>
<span class="token keyword">if</span> vRoot<span class="token punctuation">.</span>height <span class="token operator"><</span> uRoot<span class="token punctuation">.</span>height<span class="token operator">:</span>
vRoot<span class="token punctuation">.</span>parent <span class="token operator">=</span> uRoot
<span class="token keyword">else</span> <span class="token keyword">if</span> vRoot<span class="token punctuation">.</span>height <span class="token operator">></span> uRoot<span class="token punctuation">.</span>height<span class="token operator">:</span>
uRoot<span class="token punctuation">.</span>parent <span class="token operator">=</span> vRoot
<span class="token keyword">else</span><span class="token operator">:</span>
uRoot<span class="token punctuation">.</span>parent <span class="token operator">=</span> vRoot
uRoot<span class="token punctuation">.</span>height <span class="token operator">=</span> uRoot<span class="token punctuation">.</span>height <span class="token operator">+</span> <span class="token number">1</span>
</code></pre></div></li> <p>This leads to <code>O(alpha(n))</code> time for each operation, where <code>alpha</code> is the inverse of the fast-growing Ackermann function, thus it is very slow growing, and can be considered <code>O(1)</code> for practical purposes.</p> <p>This makes the entire Kruskal's algorithm <code>O(m log m + m) = O(m log m)</code>, because of the initial sorting.</p> <p><strong>Note</strong></p> <p>Path compression may reduce the height of the tree, hence comparing heights of the trees during union operation might not be a trivial task. Hence to avoid the complexity of storing and calculating the height of the trees the resulting parent can be picked randomly:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>subalgo <span class="token function">unionSet</span><span class="token punctuation">(</span>u<span class="token punctuation">,</span> v<span class="token operator">:</span> nodes<span class="token punctuation">)</span><span class="token operator">:</span>
vRoot <span class="token operator">=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span>
uRoot <span class="token operator">=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span>
<span class="token keyword">if</span> vRoot <span class="token operator">==</span> uRoot<span class="token operator">:</span>
<span class="token keyword">return</span>
<span class="token keyword">if</span> <span class="token function">random</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">2</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token operator">:</span>
vRoot<span class="token punctuation">.</span>parent <span class="token operator">=</span> uRoot
<span class="token keyword">else</span><span class="token operator">:</span>
uRoot<span class="token punctuation">.</span>parent <span class="token operator">=</span> vRoot
</code></pre></div><p>In practice this randomised algorithm together with path compression for <code>findSet</code> operation will result in comparable performance, yet much simpler to implement.</p> <h2 id="simple-more-detailed-implementation"><a href="#simple-more-detailed-implementation" class="header-anchor">#</a> Simple, more detailed implementation</h2> <p>In order to efficiently handle cycle detection, we consider each node as part of a tree. When adding an edge, we check if its two component nodes are part of distinct trees. Initially, each node makes up a one-node tree.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>algorithm kruskalMST<span class="token number">'</span><span class="token punctuation">(</span>G<span class="token operator">:</span> a graph<span class="token punctuation">)</span>
sort G<span class="token number">'</span>s edges by their value
MST <span class="token operator">=</span> a forest of trees<span class="token punctuation">,</span> initially each tree is a node in the graph
<span class="token keyword">for</span> each edge e in G<span class="token operator">:</span>
<span class="token keyword">if</span> the root of the tree that e<span class="token punctuation">.</span>first belongs to is <span class="token operator">not</span> the same
as the root of the tree that e<span class="token punctuation">.</span>second belongs to<span class="token operator">:</span>
connect one of the roots to the other<span class="token punctuation">,</span> thus merging two trees
<span class="token keyword">return</span> MST<span class="token punctuation">,</span> which now a single<span class="token operator">-</span>tree forest
</code></pre></div><h2 id="simple-disjoint-set-based-implementation"><a href="#simple-disjoint-set-based-implementation" class="header-anchor">#</a> Simple, disjoint-set based implementation</h2> <p>The above forest methodology is actually a disjoint-set data structure, which involves three main operations:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>subalgo <span class="token function">makeSet</span><span class="token punctuation">(</span>v<span class="token operator">:</span> a node<span class="token punctuation">)</span><span class="token operator">:</span>
v<span class="token punctuation">.</span>parent <span class="token operator">=</span> v <span class="token operator"><</span><span class="token operator">-</span> make a <span class="token keyword">new</span> tree rooted at v
subalgo <span class="token function">findSet</span><span class="token punctuation">(</span>v<span class="token operator">:</span> a node<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> v<span class="token punctuation">.</span>parent <span class="token operator">==</span> v<span class="token operator">:</span>
<span class="token keyword">return</span> v
<span class="token keyword">return</span> <span class="token function">findSet</span><span class="token punctuation">(</span>v<span class="token punctuation">.</span>parent<span class="token punctuation">)</span>
subalgo <span class="token function">unionSet</span><span class="token punctuation">(</span>v<span class="token punctuation">,</span> u<span class="token operator">:</span> nodes<span class="token punctuation">)</span><span class="token operator">:</span>
vRoot <span class="token operator">=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span>
uRoot <span class="token operator">=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span>
uRoot<span class="token punctuation">.</span>parent <span class="token operator">=</span> vRoot
algorithm kruskalMST<span class="token string">''</span><span class="token punctuation">(</span>G<span class="token operator">:</span> a graph<span class="token punctuation">)</span><span class="token operator">:</span>
sort G<span class="token number">'</span>s edges by their value
<span class="token keyword">for</span> each node n in G<span class="token operator">:</span>
<span class="token function">makeSet</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span>
<span class="token keyword">for</span> each edge e in G<span class="token operator">:</span>
<span class="token keyword">if</span> <span class="token function">findSet</span><span class="token punctuation">(</span>e<span class="token punctuation">.</span>first<span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token function">findSet</span><span class="token punctuation">(</span>e<span class="token punctuation">.</span>second<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token function">unionSet</span><span class="token punctuation">(</span>e<span class="token punctuation">.</span>first<span class="token punctuation">,</span> e<span class="token punctuation">.</span>second<span class="token punctuation">)</span>
</code></pre></div><p>This naive implementation leads to <code>O(n log n)</code> time for managing the disjoint-set data structure, leading to <code>O(m*n log n)</code> time for the entire Kruskal's algorithm.</p> <h2 id="simple-high-level-implementation"><a href="#simple-high-level-implementation" class="header-anchor">#</a> Simple, high level implementation</h2> <p>Sort the edges by value and add each one to the MST in sorted order, if it doesn't create a cycle.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>algorithm <span class="token function">kruskalMST</span><span class="token punctuation">(</span>G<span class="token operator">:</span> a graph<span class="token punctuation">)</span>
sort G<span class="token number">'</span>s edges by their value
MST <span class="token operator">=</span> an empty graph
<span class="token keyword">for</span> each edge e in G<span class="token operator">:</span>
<span class="token keyword">if</span> adding e to MST does <span class="token operator">not</span> create a cycle<span class="token operator">:</span>
add e to MST
<span class="token keyword">return</span> MST
</code></pre></div><h4 id="remarks"><a href="#remarks" class="header-anchor">#</a> Remarks</h4> <p>Kruskal's Algorithm is a <strong>greedy</strong> algorithm used to find <strong>Minimum Spanning Tree (MST)</strong> of a graph. A minimum spanning tree is a tree which connects all the vertices of the graph and has the minimum total edge weight.</p> <p>Kruskal's algorithm does so by repeatedly picking out edges with <strong>minimum weight</strong> (which are not already in the MST) and add them to the final result if the two vertices connected by that edge are not yet connected in the MST, otherwise it skips that edge. Union - Find data structure can be used to check whether two vertices are already connected in the MST or not. A few properties of MST are as follows:</p> <ol><li>A MST of a graph with <code>n</code> vertices will have exactly <code>n-1</code> edges.</li> <li>There exists a unique path from each vertex to every other vertex.</li></ol></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/kruskal-s-algorithm.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/applications-of-dynamic-programming.html" class="prev">
Applications of Dynamic Programming
</a></span> <span class="next"><a href="/algorithm/greedy-algorithms.html">
Greedy Algorithms
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/48.0bbbed97.js" defer></script>
</body>
</html>