You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{"payload":{"allShortcutsEnabled":false,"path":"Minimum Spanning Tree","repo":{"id":466864423,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"zezzi","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2022-03-06T21:45:56.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/591679?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1646603162.973994","canEdit":false,"refType":"branch","currentOid":"e592ed665973fda36df3efa6d7c20ee08705d8db"},"tree":{"items":[{"name":"Images","path":"Minimum Spanning Tree/Images","contentType":"directory"},{"name":"MinimumSpanningTree.playground","path":"Minimum Spanning Tree/MinimumSpanningTree.playground","contentType":"directory"},{"name":"Kruskal.swift","path":"Minimum Spanning Tree/Kruskal.swift","contentType":"file"},{"name":"Prim.swift","path":"Minimum Spanning Tree/Prim.swift","contentType":"file"},{"name":"README.markdown","path":"Minimum Spanning Tree/README.markdown","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","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\"\u003eMinimum Spanning Tree (Weighted Graph)\u003c/h1\u003e\u003ca id=\"user-content-minimum-spanning-tree-weighted-graph\" class=\"anchor\" aria-label=\"Permalink: Minimum Spanning Tree (Weighted Graph)\" href=\"#minimum-spanning-tree-weighted-graph\"\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\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003eThis topic has been tutorialized \u003ca href=\"https://www.raywenderlich.com/169392/swift-algorithm-club-minimum-spanning-tree-with-prims-algorithm\" rel=\"nofollow\"\u003ehere\u003c/a\u003e\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003eA \u003ca href=\"https://en.wikipedia.org/wiki/Minimum_spanning_tree\" rel=\"nofollow\"\u003eminimum spanning tree\u003c/a\u003e (MST) of a connected undirected weighted graph has a subset of the edges from the original graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. There can be more than one MSTs of a graph.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThere are two popular algorithms to calculate MST of a graph - \u003ca href=\"https://en.wikipedia.org/wiki/Kruskal's_algorithm\" rel=\"nofollow\"\u003eKruskal's algorithm\u003c/a\u003e and \u003ca href=\"https://en.wikipedia.org/wiki/Prim's_algorithm\" rel=\"nofollow\"\u003ePrim's algorithm\u003c/a\u003e. Both algorithms have a total time complexity of \u003ccode\u003eO(ElogE)\u003c/code\u003e where \u003ccode\u003eE\u003c/code\u003e is the number of edges from the original graph.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eKruskal's Algorithm\u003c/h3\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\"\u003eSort the edges base on weight. Greedily select the smallest one each time and add into the MST as long as it doesn't form a cycle.\nKruskal's algoritm uses \u003ca href=\"https://github.com/raywenderlich/swift-algorithm-club/tree/master/Union-Find\"\u003eUnion Find\u003c/a\u003e data structure to check whether any additional edge causes a cycle. The logic is to put all connected vertices into the same set (in Union Find's concept). If the two vertices from a new edge do not belong to the same set, then it's safe to add that edge into the MST.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe following graph demonstrates the steps:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/zezzi/swift-algorithm-club/blob/master/Minimum%20Spanning%20Tree/Images/kruskal.png\"\u003e\u003cimg src=\"/zezzi/swift-algorithm-club/raw/master/Minimum%20Spanning%20Tree/Images/kruskal.png\" alt=\"Graph\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003ePreparation\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"// Initialize the values to be returned and Union Find data structure.\nvar cost: Int = 0\nvar tree = Graph\u0026lt;T\u0026gt;()\nvar unionFind = UnionFind\u0026lt;T\u0026gt;()\nfor vertex in graph.vertices {\n\n// Initially all vertices are disconnected.\n// Each of them belongs to it's individual set.\n unionFind.addSetWith(vertex)\n}\"\u003e\u003cpre\u003e// Initialize the values to be returned and Union Find data structure.\n\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ecost\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etree\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eGraph\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eunionFind\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUnionFind\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003evertex\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e graph\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003evertices \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n\n// Initially all vertices are disconnected.\n// Each of them belongs to it's individual set.\n unionFind\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eaddSetWith\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evertex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eSort the edges\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight \u0026lt; $1.weight })\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esortedEdgeListByWeight\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e graph\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eedgeList\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003esorted\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eby\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e $0\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e $1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTake one edge at a time and try to insert it into the MST.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"for edge in sortedEdgeListByWeight {\n let v1 = edge.vertex1\n let v2 = edge.vertex2 \n \n // Same set means the two vertices of this edge were already connected in the MST.\n // Adding this one will cause a cycle.\n if !unionFind.inSameSet(v1, and: v2) {\n // Add the edge into the MST and update the final cost.\n cost += edge.weight\n tree.addEdge(edge)\n \n // Put the two vertices into the same set.\n unionFind.unionSetsContaining(v1, and: v2)\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eedge\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e sortedEdgeListByWeight \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ev1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e edge\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003evertex1\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ev2\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e edge\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003evertex2 \n \n // Same set means the two vertices of this edge were already connected in the MST.\n // Adding this one will cause a cycle.\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e !unionFind\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003einSameSet\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ev1\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e and\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e v2\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n // Add the edge into the MST and update the final cost.\n cost \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e edge\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight\n tree\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eaddEdge\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eedge\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \n // Put the two vertices into the same set.\n unionFind\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eunionSetsContaining\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ev1\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e and\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e v2\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003ePrim's Algorithm\u003c/h3\u003e\u003ca id=\"user-content-prims-algorithm\" class=\"anchor\" aria-label=\"Permalink: Prim's Algorithm\" href=\"#prims-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\"\u003ePrim's algorithm doesn't pre-sort all edges. Instead, it uses a \u003ca href=\"https://github.com/raywenderlich/swift-algorithm-club/tree/master/Priority%20Queue\"\u003ePriority Queue\u003c/a\u003e to maintain a running sorted next-possile vertices.\nStarting from one vertex, loop through all unvisited neighbours and enqueue a pair of values for each neighbour - the vertex and the weight of edge connecting current vertex to the neighbour. Each time it greedily select the top of the priority queue (the one with least weight value) and add the edge into the final MST if the enqueued neighbour hasn't been already visited.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe following graph demonstrates the steps:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/zezzi/swift-algorithm-club/blob/master/Minimum%20Spanning%20Tree/Images/prim.png\"\u003e\u003cimg src=\"/zezzi/swift-algorithm-club/raw/master/Minimum%20Spanning%20Tree/Images/prim.png\" alt=\"Graph\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003ePreparation\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"// Initialize the values to be returned and Priority Queue data structure.\nvar cost: Int = 0\nvar tree = Graph\u0026lt;T\u0026gt;()\nvar visited = Set\u0026lt;T\u0026gt;()\n\n// In addition to the (neighbour vertex, weight) pair, parent is added for the purpose of printing out the MST later.\n// parent is basically current vertex. aka. the previous vertex before neigbour vertex gets visited.\nvar priorityQueue = PriorityQueue\u0026lt;(vertex: T, weight: Int, parent: T?)\u0026gt;(sort: { $0.weight \u0026lt; $1.weight })\"\u003e\u003cpre\u003e// Initialize the values to be returned and Priority Queue data structure.\n\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ecost\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etree\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eGraph\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003evisited\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eSet\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n// In addition to the (neighbour vertex, weight) pair, parent is added for the purpose of printing out the MST later.\n// parent is basically current vertex. aka. the previous vertex before neigbour vertex gets visited.\n\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epriorityQueue\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003ePriorityQueue\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evertex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e weight\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e parent\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003esort\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e $0\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e $1\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eStart from any vertex\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"priorityQueue.enqueue((vertex: graph.vertices.first!, weight: 0, parent: nil))\"\u003e\u003cpre\u003epriorityQueue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eenqueue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evertex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e graph\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003evertices\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003efirst!\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e weight\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e parent\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003enil\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"// Take from the top of the priority queue ensures getting the least weight edge.\nwhile let head = priorityQueue.dequeue() {\n let vertex = head.vertex\n if visited.contains(vertex) {\n continue\n }\n\n // If the vertex hasn't been visited before, its edge (parent-vertex) is selected for MST.\n visited.insert(vertex)\n cost += head.weight\n if let prev = head.parent { // The first vertex doesn't have a parent.\n tree.addEdge(vertex1: prev, vertex2: vertex, weight: head.weight)\n }\n\n // Add all unvisted neighbours into the priority queue.\n if let neighbours = graph.adjList[vertex] {\n for neighbour in neighbours {\n let nextVertex = neighbour.vertex\n if !visited.contains(nextVertex) {\n priorityQueue.enqueue((vertex: nextVertex, weight: neighbour.weight, parent: vertex))\n }\n }\n }\n}\"\u003e\u003cpre\u003e// Take from the top of the priority queue ensures getting the least weight edge.\n\u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e head \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e priorityQueue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003edequeue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003evertex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e head\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003evertex\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e visited\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003econtains\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evertex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003econtinue\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // If the vertex hasn't been visited before, its edge (parent-vertex) is selected for MST.\n visited\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003einsert\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evertex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n cost \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e head\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e prev \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e head\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eparent \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // The first vertex doesn't have a parent.\n tree\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eaddEdge\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evertex1\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e prev\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e vertex2\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e vertex\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e weight\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e head\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // Add all unvisted neighbours into the priority queue.\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e neighbours \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e graph\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eadjList\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003evertex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eneighbour\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e neighbours \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enextVertex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e neighbour\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003evertex\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e !visited\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003econtains\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003enextVertex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n priorityQueue\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eenqueue\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evertex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e nextVertex\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e weight\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e neighbour\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eweight\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e parent\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e vertex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Minimum Spanning Tree (Weighted Graph)","anchor":"minimum-spanning-tree-weighted-graph","htmlText":"Minimum Spanning Tree (Weighted Graph)"},{"level":3,"text":"Kruskal's Algorithm","anchor":"kruskals-algorithm","htmlText":"Kruskal's Algorithm"},{"level":3,"text":"Prim's Algorithm","anchor":"prims-algorithm","htmlText":"Prim's Algorithm"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fzezzi%2Fswift-algorithm-club%2Ftree%2Fmaster%2FMinimum%2520Spanning%2520Tree"}},"totalCount":5,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"A-Star","path":"A-Star","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Closest Pair","path":"Closest Pair","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"CounterClockWise","path":"CounterClockWise","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Genetic","path":"Genetic","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Myers Difference Algorithm","path":"Myers Difference Algorithm","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Points Lines Planes","path":"Points Lines Planes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yar
36F8
d","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":120}},"fileTreeProcessingTime":4.118654,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/zezzi/swift-algorithm-club/branches":{"post":"2k5ozqQ-5x5fmMrtowM7YuKv0rhV1CEyFneiFx0PwISMlO4CIyUftEHhbcefHjO5HizDv2c3N7_txgeu7_LRAQ"},"/zezzi/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"JlX-vT1E_rWb6Cr7Gn8wyx9Dq1u87PUiTHcCgjsgpO1N-LfG8s4bFAkKmupaOAaAVG6ykGNwZq3qXn16EA4IsA"},"/zezzi/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"Qg9nQFEf1jAwr1fZ-OTTXjCLlT1rJEvNAVIXIcS3Jjwpoi47npUzkaJN58i4o-UVe6aM9rS42EKne2jZ75mKYQ"}}},"title":"swift-algorithm-club/Minimum Spanning Tree at master · zezzi/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}