{"payload":{"allShortcutsEnabled":false,"path":"src/algorithms/graph/kruskal","repo":{"id":303683642,"defaultBranch":"master","name":"javascript-algorithms","ownerLogin":"bxtaylor","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2020-10-13T11:41:01.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/401092?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"merge","listCacheKey":"v0:1613705505.946548","canEdit":false,"refType":"branch","currentOid":"477f30b0bdac6024874d2976de1eca7afe0176dd"},"tree":{"items":[{"name":"__test__","path":"src/algorithms/graph/kruskal/__test__","contentType":"directory"},{"name":"README.md","path":"src/algorithms/graph/kruskal/README.md","contentType":"file"},{"name":"kruskal.js","path":"src/algorithms/graph/kruskal/kruskal.js","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.md","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eKruskal's Algorithm\u003c/h1\u003e\u003ca id=\"user-content-kruskals-algorithm\" class=\"anchor\" aria-label=\"Permalink: Kruskal's Algorithm\" href=\"#kruskals-algorithm\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eKruskal's algorithm is a minimum-spanning-tree algorithm which\nfinds an edge of the least possible weight that connects any two\ntrees in the forest. It is a greedy algorithm in graph theory\nas it finds a minimum spanning tree for a connected weighted\ngraph adding increasing cost arcs at each step. This means it\nfinds a subset of the edges that forms a tree that includes every\nvertex, where the total weight of all the edges in the tree is\nminimized. If the graph is not connected, then it finds a\nminimum spanning forest (a minimum spanning tree for each\nconnected component).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/b7d429c14d678c4ed6aaf503386708c74709718b6a35e7388fee5d4f313fac9a/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f352f35632f4d53545f6b7275736b616c5f656e2e676966\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/b7d429c14d678c4ed6aaf503386708c74709718b6a35e7388fee5d4f313fac9a/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f352f35632f4d53545f6b7275736b616c5f656e2e676966\" alt=\"Kruskal Algorithm\" data-animated-image=\"\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/5/5c/MST_kruskal_en.gif\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/ae09c6e4fd3dd82a5ef262fce6be398dadb59b3754a679495bf7ccd91c8b078d/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f622f62622f4b7275736b616c44656d6f2e676966\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/ae09c6e4fd3dd82a5ef262fce6be398dadb59b3754a679495bf7ccd91c8b078d/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f622f62622f4b7275736b616c44656d6f2e676966\" alt=\"Kruskal Demo\" data-animated-image=\"\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/b/bb/KruskalDemo.gif\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eA demo for Kruskal's algorithm based on Euclidean distance.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eMinimum Spanning Tree\u003c/h2\u003e\u003ca id=\"user-content-minimum-spanning-tree\" class=\"anchor\" aria-label=\"Permalink: Minimum Spanning Tree\" href=\"#minimum-spanning-tree\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eA \u003cstrong\u003eminimum spanning tree\u003c/strong\u003e (MST) or minimum weight spanning tree\nis a subset of the edges of a connected, edge-weighted\n(un)directed graph that connects all the vertices together,\nwithout any cycles and with the minimum possible total edge\nweight. That is, it is a spanning tree whose sum of edge weights\nis as small as possible. More generally, any edge-weighted\nundirected graph (not necessarily connected) has a minimum\nspanning forest, which is a union of the minimum spanning\ntrees for its connected components.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/096d6e691d004234325790e6e9c8197ffab02612646c538f6e75d99a91117bf2/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f642f64322f4d696e696d756d5f7370616e6e696e675f747265652e737667\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/096d6e691d004234325790e6e9c8197ffab02612646c538f6e75d99a91117bf2/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f642f64322f4d696e696d756d5f7370616e6e696e675f747265652e737667\" alt=\"Minimum Spanning Tree\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/d/d2/Minimum_spanning_tree.svg\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eA planar graph and its minimum spanning tree. Each edge is\nlabeled with its weight, which here is roughly proportional\nto its length.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/41e066610a5bdaf910a7531738fefc79e8a57ce44ada43bca84a715f3cfeff83/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f632f63392f4d756c7469706c655f6d696e696d756d5f7370616e6e696e675f74726565732e737667\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/41e066610a5bdaf910a7531738fefc79e8a57ce44ada43bca84a715f3cfeff83/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f632f63392f4d756c7469706c655f6d696e696d756d5f7370616e6e696e675f74726565732e737667\" alt=\"Minimum Spanning Tree\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/c/c9/Multiple_minimum_spanning_trees.svg\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThis figure shows there may be more than one minimum spanning\ntree in a graph. In the figure, the two trees below the graph\nare two possibilities of minimum spanning tree of the given graph.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eReferences\u003c/h2\u003e\u003ca id=\"user-content-references\" class=\"anchor\" aria-label=\"Permalink: References\" href=\"#references\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Minimum_spanning_tree\" rel=\"nofollow\"\u003eMinimum Spanning Tree on Wikipedia\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Kruskal%27s_algorithm\" rel=\"nofollow\"\u003eKruskal's Algorithm on Wikipedia\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.youtube.com/watch?v=fAuF0EuZVCk\u0026amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\" rel=\"nofollow\"\u003eKruskal's Algorithm on YouTube by Tushar Roy\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.youtube.com/watch?v=71UQH7Pr9kU\u0026amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\" rel=\"nofollow\"\u003eKruskal's Algorithm on YouTube by Michael Sambol\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Kruskal's Algorithm","anchor":"kruskals-algorithm","htmlText":"Kruskal's Algorithm"},{"level":2,"text":"Minimum Spanning Tree","anchor":"minimum-spanning-tree","htmlText":"Minimum Spanning Tree"},{"level":2,"text":"References","anchor":"references","htmlText":"References"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fbxtaylor%2Fjavascript-algorithms%2Ftree%2Fmerge%2Fsrc%2Falgorithms%2Fgraph%2Fkruskal"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"src/algorithms/graph":{"items":[{"name":"articulation-points","path":"src/algorithms/graph/articulation-points","contentType":"directory"},{"name":"bellman-ford","path":"src/algorithms/graph/bellman-ford","contentType":"directory"},{"name":"breadth-first-search","path":"src/algorithms/graph/breadth-first-search","contentType":"directory"},{"name":"bridges","path":"src/algorithms/graph/bridges","contentType":"directory"},{"name":"depth-first-search","path":"src/algorithms/graph/depth-first-search","contentType":"directory"},{"name":"detect-cycle","path":"src/algorithms/graph/detect-cycle","contentType":"directory"},{"name":"dijkstra","path":"src/algorithms/graph/dijkstra","contentType":"directory"},{"name":"eulerian-path","path":"src/algorithms/graph/eulerian-path","contentType":"directory"},{"name":"floyd-warshall","path":"src/algorithms/graph/floyd-warshall","contentType":"directory"},{"name":"hamiltonian-cycle","path":"src/algorithms/graph/hamiltonian-cycle","contentType":"directory"},{"name":"kruskal","path":"src/algorithms/graph/kruskal","contentType":"directory"},{"name":"prim","path":"src/algorithms/graph/prim","contentType":"directory"},{"name":"strongly-connected-components","path":"src/algorithms/graph/strongly-connected-components","contentType":"directory"},{"name":"topological-sorting","path":"src/algorithms/graph/topological-sorting","contentType":"directory"},{"name":"travelling-salesman","path":"src/algorithms/graph/travelling-salesman","contentType":"directory"}],"totalCount":15},"src/algorithms":{"items":[{"name":"cryptography","path":"src/algorithms/cryptography","contentType":"directory"},{"name":"graph","path":"src/algorithms/graph","contentType":"directory"},{"name":"linked-list","path":"src/algorithms/linked-list","contentType":"directory"},{"name":"math","path":"src/algorithms/math","contentType":"directory"},{"name":"search","path":"src/algorithms/search","contentType":"directory"},{"name":"sets","path":"src/algorithms/sets","contentType":"directory"},{"name":"sorting","path":"src/algorithms/sorting","contentType":"directory"},{"name":"string","path":"src/algorithms/string","contentType":"directory"},{"name":"tree","path":"src/algorithms/tree","contentType":"directory"},{"name":"uncategorized","path":"src/algorithms/uncategorized","contentType":"directory"}],"totalCount":10},"src":{"items":[{"name":"algorithms","path":"src/algorithms","contentType":"directory"},{"name":"data-structures","path":"src/data-structures","contentType":"directory"},{"name":"playground","path":"src/playground","contentType":"directory"},{"name":"utils","path":"src/utils","contentType":"directory"}],"totalCount":4},"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"assets","path":"assets","contentType":"directory"},{"name":"src","path":"src","contentType":"directory"},{"name":".babelrc","path":".babelrc","contentType":"file"},{"name":".editorconfig","path":".editorconfig","contentType":"file"},{"name":".eslintrc","path":".eslintrc","contentType":"file"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".huskyrc.json","path":".huskyrc.json","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"BACKERS.md","path":"BACKERS.md","contentType":"file"},{"name":"CODE_OF_CONDUCT.md","path":"CODE_OF_CONDUCT.md","contentType":"file"},{"name":"CONTRIBUTING.md","path":"CONTRIBUTING.md","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.es-ES.md","path":"README.es-ES.md","contentType":"file"},{"name":"README.fr-FR.md","path":"README.fr-FR.md","contentType":"file"},{"name":"README.ja-JP.md","path":"README.ja-JP.md","contentType":"file"},{"name":"README.ko-KR.md","path":"README.ko-KR.md","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"README.pl-PL.md","path":"README.pl-PL.md","contentType":"file"},{"name":"README.pt-BR.md","path":"README.pt-BR.md","contentType":"file"},{"name":"README.zh-CN.md","path":"README.zh-CN.md","contentType":"file"},{"name":"README.zh-TW.md","path":"README.zh-TW.md","contentType":"file"},{"name":"jest.config.js","path":"jest.config.js","contentType":"file"},{"name":"package-lock.json","path":"package-lock.json","contentType":"file"},{"name":"package.json","path":"package.json","contentType":"file"}],"totalCount":25}},"fileTreeProcessingTime":6.035927,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/bxtaylor/javascript-algorithms/branches":{"post":"5Wp9EyEEWzqkmfuV8lF-Yt8j5-mAbL9cu4SASa5sgkLI1ZPvtQood4nlWd0MeOr-EbfOSKemAXsEtCMi8EfBUg"},"/bxtaylor/javascript-algorithms/branches/fetch_and_merge/merge":{"post":"lVsH-Und3bVz_-tDt5lBW0JjAesUsBJ-xAzUmZMrYQkgP3d39P6ql6avERbF4V802YlI1h48ZVMhyat5l1zZhA"},"/bxtaylor/javascript-algorithms/branches/fetch_and_merge/merge?discard_changes=true":{"post":"quHvS30Pae3j-la-IpHq2s5fyZ71rHCnB_V6UsO1Mk4fhZ_FwCwezzaqrOtQ6fS1VbWAo_8gB4riMAWyx8KKww"}}},"title":"javascript-algorithms/src/algorithms/graph/kruskal at merge · bxtaylor/javascript-algorithms","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-b84e9496fc59.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
You can’t perform that action at this time.