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":"Topological Sort","repo":{"id":219288559,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"STjason","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-11-03T11:13:10.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/1157388?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1615725554.570706","canEdit":false,"refType":"branch","currentOid":"20bd018788f9d2c05e6772c23a731857966f624c"},"tree":{"items":[{"name":"Images","path":"Topological Sort/Images","contentType":"directory"},{"name":"Tests","path":"Topological Sort/Tests","contentType":"directory"},{"name":"Topological Sort.playground","path":"Topological Sort/Topological Sort.playground","contentType":"directory"},{"name":"Graph.swift","path":"Topological Sort/Graph.swift","contentType":"file"},{"name":"README.markdown","path":"Topological Sort/README.markdown","contentType":"file"},{"name":"TopologicalSort1.swift","path":"Topological Sort/TopologicalSort1.swift","contentType":"file"},{"name":"TopologicalSort2.swift","path":"Topological Sort/TopologicalSort2.swift","contentType":"file"},{"name":"TopologicalSort3.swift","path":"Topological Sort/TopologicalSort3.swift","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\"\u003eTopological Sort\u003c/h1\u003e\u003ca id=\"user-content-topological-sort\" class=\"anchor\" aria-label=\"Permalink: Topological Sort\" href=\"#topological-sort\"\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\"\u003eTopological sort is an algorithm that orders a directed graph such that for each directed edge \u003cem\u003eu→v\u003c/em\u003e, vertex \u003cem\u003eu\u003c/em\u003e comes before vertex \u003cem\u003ev\u003c/em\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIn other words, a topological sort places the vertices of a \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Graph\"\u003edirected acyclic graph\u003c/a\u003e on a line so that all directed edges go from left to right.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eConsider the graph in the following example:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/Images/Graph.png\"\u003e\u003cimg src=\"/STjason/swift-algorithm-club/raw/master/Topological%20Sort/Images/Graph.png\" alt=\"Example\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThis graph has two possible topological sorts:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/Images/TopologicalSort.png\"\u003e\u003cimg src=\"/STjason/swift-algorithm-club/raw/master/Topological%20Sort/Images/TopologicalSort.png\" alt=\"Example\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe topological orderings are \u003cstrong\u003eS, V, W, T, X\u003c/strong\u003e and \u003cstrong\u003eS, W, V, T, X\u003c/strong\u003e. Notice how the arrows all go from left to right.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe following is not a valid topological sort for this graph, since \u003cstrong\u003eX\u003c/strong\u003e and \u003cstrong\u003eT\u003c/strong\u003e cannot happen before \u003cstrong\u003eV\u003c/strong\u003e:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/Images/InvalidSort.png\"\u003e\u003cimg src=\"/STjason/swift-algorithm-club/raw/master/Topological%20Sort/Images/InvalidSort.png\" alt=\"Example\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eWhere is this used?\u003c/h2\u003e\u003ca id=\"user-content-where-is-this-used\" class=\"anchor\" aria-label=\"Permalink: Where is this used?\" href=\"#where-is-this-used\"\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\"\u003eLet's consider that you want to learn all the algorithms and data structures from the Swift Algorithm Club. This might seem daunting at first but we can use topological sort to get things organized.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSince you're learning about topological sort, let's take this topic as an example. What else do you need to learn first before you can fully understand topological sort? Well, topological sort uses \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Depth-First%20Search\"\u003edepth-first search\u003c/a\u003e as well as a \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Stack\"\u003estack\u003c/a\u003e. But before you can learn about the depth-first search algorithm, you need to know what a \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Graph\"\u003egraph\u003c/a\u003e is, and it helps to know what a \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Tree\"\u003etree\u003c/a\u003e is. In turn, graphs and trees use the idea of linking objects together, so you may need to read up on that first. And so on...\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIf we were to represent these objectives in the form of a graph it would look as follows:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/Images/Algorithms.png\"\u003e\u003cimg src=\"/STjason/swift-algorithm-club/raw/master/Topological%20Sort/Images/Algorithms.png\" alt=\"Example\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIf we consider each algorithm to be a vertex in the graph you can clearly see the dependencies between them. To learn something you might have to know something else first. This is exactly what topological sort is used for -- it will sort things out so that you know what to do first.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eHow does it work?\u003c/h2\u003e\u003ca id=\"user-content-how-does-it-work\" class=\"anchor\" aria-label=\"Permalink: How does it work?\" href=\"#how-does-it-work\"\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\"\u003e\u003cstrong\u003eStep 1: Find all vertices that have in-degree of 0\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe \u003cem\u003ein-degree\u003c/em\u003e of a vertex is the number of edges pointing at that vertex. Vertices with no incoming edges have an in-degree of 0. These vertices are the starting points for the topological sort.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIn the context of the previous example, these starting vertices represent algorithms and data structures that don't have any prerequisites; you don't need to learn anything else first, hence the sort starts with them.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eStep 2: Traverse the graph with depth-first search\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eDepth-first search is an algorithm that starts traversing the graph from a certain vertex and explores as far as possible along each branch before backtracking. To find out more about depth-first search, please take a look at the \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Depth-First%20Search\"\u003edetailed explanation\u003c/a\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe perform a depth-first search on each vertex with in-degree 0. This tells us which vertices are connected to each of these starting vertices.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eStep 3: Remember all visited vertices\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAs we perform the depth-first search, we maintain a list of all the vertices that have been visited. This is to avoid visiting the same vertex twice.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eStep 4: Put it all together\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe last step of the sort is to combine the results of the different depth-first searches and put the vertices in a sorted list.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eExample\u003c/h2\u003e\u003ca id=\"user-content-example\" class=\"anchor\" aria-label=\"Permalink: Example\" href=\"#example\"\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\"\u003eConsider the following graph:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/Images/Example.png\"\u003e\u003cimg src=\"/STjason/swift-algorithm-club/raw/master/Topological%20Sort/Images/Example.png\" alt=\"Graph Example\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eStep 1:\u003c/strong\u003e The vertices with 0 in-degree are: \u003cstrong\u003e3, 7, 5\u003c/strong\u003e. These are our starting vertices.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eStep 2:\u003c/strong\u003e Perform depth-first search for each starting vertex, without remembering vertices that have already been visited:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"Vertex 3: 3, 10, 8, 9\nVertex 7: 7, 11, 2, 8, 9\nVertex 5: 5, 11, 2, 9, 10\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eVertex 3: 3, 10, 8, 9\nVertex 7: 7, 11, 2, 8, 9\nVertex 5: 5, 11, 2, 9, 10\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eStep 3:\u003c/strong\u003e Filter out the vertices already visited in each previous search:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"Vertex 3: 3, 10, 8, 9\nVertex 7: 7, 11, 2\nVertex 5: 5\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eVertex 3: 3, 10, 8, 9\nVertex 7: 7, 11, 2\nVertex 5: 5\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eStep 4:\u003c/strong\u003e Combine the results of these three depth-first searches. The final sorted order is \u003cstrong\u003e5, 7, 11, 2, 3, 10, 8, 9\u003c/strong\u003e. (Important: we need to add the results of each subsequent search to the \u003cem\u003efront\u003c/em\u003e of the sorted list.)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe result of the topological sort looks like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/Images/GraphResult.png\"\u003e\u003cimg src=\"/STjason/swift-algorithm-club/raw/master/Topological%20Sort/Images/GraphResult.png\" alt=\"Result of the sort\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e This is not the only possible topological sort for this graph. For example, other valid solutions are \u003cstrong\u003e3, 7, 5, 10, 8, 11, 9, 2\u003c/strong\u003e and \u003cstrong\u003e3, 7, 5, 8, 11, 2, 9, 10\u003c/strong\u003e. Any order where all the arrows are going from left to right will do.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe code\u003c/h2\u003e\u003ca id=\"user-content-the-code\" class=\"anchor\" aria-label=\"Permalink: The code\" href=\"#the-code\"\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\"\u003eHere is how you could implement topological sort in Swift (see also \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/TopologicalSort1.swift\"\u003eTopologicalSort1.swift\u003c/a\u003e):\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"extension Graph {\n public func topologicalSort() -\u0026gt; [Node] {\n // 1\n let startNodes = calculateInDegreeOfNodes().filter({ _, indegree in\n return indegree == 0\n }).map({ node, indegree in\n return node\n })\n \n // 2\n var visited = [Node : Bool]()\n for (node, _) in adjacencyLists {\n visited[node] = false\n }\n \n // 3\n var result = [Node]()\n for startNode in startNodes {\n result = depthFirstSearch(startNode, visited: \u0026amp;visited) + result\n }\n\n // 4 \n return result\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eextension\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eGraph\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e topologicalSort\u003cspan class=\"pl-kos\"\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\u003e\u003cspan class=\"pl-smi\"\u003eNode\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n // 1\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estartNodes\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ecalculateInDegreeOfNodes\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\u003cspan class=\"pl-en\"\u003efilter\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 indegree \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e indegree \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003emap\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e node\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e indegree \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e node\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \n // 2\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-kos\"\u003e[\u003c/span\u003eNode \u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e Bool\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\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e\u003cspan class=\"pl-s1\"\u003e(node\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e _\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e adjacencyLists \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003evisited\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003enode\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \n // 3\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eNode\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\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estartNode\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e startNodes \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n result \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003edepthFirstSearch\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003estartNode\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e visited\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003evisited\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e result\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // 4 \n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e result\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\u003cp dir=\"auto\"\u003eSome remarks:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eFind the in-degree of each vertex and put all the vertices with in-degree 0 in the \u003ccode\u003estartNodes\u003c/code\u003e array. In this graph implementation, vertices are called \"nodes\". Both terms are used interchangeably by people who write graph code.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003evisited\u003c/code\u003e array keeps track of whether we've already seen a vertex during the depth-first search. Initially, we set all elements to \u003ccode\u003efalse\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eFor each of the vertices in the \u003ccode\u003estartNodes\u003c/code\u003e array, perform a depth-first search. This returns an array of sorted \u003ccode\u003eNode\u003c/code\u003e objects. We prepend that array to our own \u003ccode\u003eresult\u003c/code\u003e array.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003eresult\u003c/code\u003e array contains all the vertices in topologically sorted order.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e For a slightly different implementation of topological sort using depth-first search, see \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/TopologicalSort3.swift\"\u003eTopologicalSort3.swift\u003c/a\u003e. This uses a stack and does not require you to find all vertices with in-degree 0 first.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eKahn's algorithm\u003c/h2\u003e\u003ca id=\"user-content-kahns-algorithm\" class=\"anchor\" aria-label=\"Permalink: Kahn's algorithm\" href=\"#kahns-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\"\u003eEven though depth-first search is the typical way to perform a topological sort, there is another algorithm that also does the job.\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eFind out what the in-degree is of every vertex.\u003c/li\u003e\n\u003cli\u003ePut all the vertices that have no predecessors in a new array called \u003ccode\u003eleaders\u003c/code\u003e. These vertices have in-degree 0 and therefore do not depend on any other vertices.\u003c/li\u003e\n\u003cli\u003eGo through this list of leaders and remove them one-by-one from the graph. We don't actually modify the graph, we just decrement the in-degree of the vertices they point to. That has the same effect.\u003c/li\u003e\n\u003cli\u003eLook at the (former) immediate neighbor vertices of each leader. If any of them now have an in-degree of 0, then they no longer have any predecessors themselves. We'll add those vertices to the \u003ccode\u003eleaders\u003c/code\u003e array too.\u003c/li\u003e\n\u003cli\u003eThis repeats until there are no more vertices left to look at. At this point, the \u003ccode\u003eleaders\u003c/code\u003e array contains all the vertices in sorted order.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eThis is an \u003cstrong\u003eO(n + m)\u003c/strong\u003e algorithm where \u003cstrong\u003en\u003c/strong\u003e is the number of vertices and \u003cstrong\u003em\u003c/strong\u003e is the number of edges. You can see the implementation in \u003ca href=\"/STjason/swift-algorithm-club/blob/master/Topological%20Sort/TopologicalSort2.swift\"\u003eTopologicalSort2.swift\u003c/a\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSource: I first read about this alternative algorithm in the Algorithm Alley column in Dr. Dobb's Magazine from May 1993.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by Ali Hafizji and Matthijs Hollemans\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Topological Sort","anchor":"topological-sort","htmlText":"Topological Sort"},{"level":2,"text":"Where is this used?","anchor":"where-is-this-used","htmlText":"Where is this used?"},{"level":2,"text":"How does it work?","anchor":"how-does-it-work","htmlText":"How does it work?"},{"level":2,"text":"Example","anchor":"example","htmlText":"Example"},{"level":2,"text":"The code","anchor":"the-code","htmlText":"The code"},{"level":2,"text":"Kahn's algorithm","anchor":"kahns-algorithm","htmlText":"Kahn's algorithm"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2FSTjason%2Fswift-algorithm-club%2Ftree%2Fmaster%2FTopological%2520Sort"}},"totalCount":8,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","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":"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":"Roo
3A19
tish 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 Yard","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":118}},"fileTreeProcessingTime":7.260567,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/STjason/swift-algorithm-club/branches":{"post":"9TT0P2nTtpnQjl2UEExnsoi6LbmLR4B_lQBeu21mCdM4h4iIcdZgQbqj2epGMAM3VTwuoh8vuSr7S9PHdexh-A"},"/STjason/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"3RofHt7m5ByH7pIVSNqSni0540izim0enNOQYBOwQeOtPvF78JpsWAp93w1w81MeyBX7aFCPXAc9PBFAaq91kQ"},"/STjason/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"xy47zkbZWj6LxFOm0eRelJwzSdWqtYznBw_J4yXfqxe3CtWraKXSegZXHr7pzZ8UeR9R9Umwvf6m4EjDXMCfZQ"}}},"title":"swift-algorithm-club/Topological Sort at master · STjason/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}}}