loading...

Topological Sorting of Directed Acyclic Graphs (DAGs)

jjb profile image JB Updated on ・3 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources:

  1. MIT video explaining topological sort
  2. Video explanation and walkthrough
  3. Video explanation and implementation

Takeaways:

  • Topological sort is an algorithm that produces a linear ordering of a graph's vertices such that for every directed edge v -> u, vertex v comes before vertex u in the ordering.
  • There can be more than one valid topological ordering of a graph's vertices.
  • Topological sort only works for Directed Acyclic Graphs (DAGs)
  • Undirected graphs, or graphs with cycles (cyclic graphs), have edges where there is no clear start and end. Think of v -> u, in an undirected graph this edge would be v <--> u. The same is true for a graph with a back edge (cycle) - we do not know what the order should be as it is ambiguous as to which vertex comes before the other.
  • Here is a visualization of what a topological sort might produce:

DAG before topological sort

DAG

Three valid topological orderings of the DAG's vertices

Topological ordering


  • One important thing to consider when thinking about topological ordering is the in-degree and out-degree of each vertex.
    • In-degree is how many edges point to a vertex (incoming edges).
    • Out-degree is how many edges point from a vertex (outgoing edges).
  • Vertices with an in-degree of 0 will tend to be towards the beginning of a topological ordering, because no other vertex points to them.
  • Vertices with an out-degree of 0 will be towards the end of a topological ordering, because they don't point to any vertices - they are solely destination vertices in directed edges.
  • There are two main ways to perform topological sort: Kahn's Algorithm & Depth-First Search (DFS).
  • Roberet Tarjan is credited with being the first to write about using DFS for topological sorting.
  • Kahn's algorithm relies on pre-calculating the in-degree of each vertex.
  • Tarjan's approach uses DFS to a achieve a topological ordering of a graph's vertices.
  • In this post I will be covering DFS and not Kahn's algorithm.
  • If you wish to learn more about Kahn's algorithm see this explanation.
  • Using DFS for topological sorting is actually almost identical to vanilla DFS, the main difference is that we keep track of a collection of vertices to return (which will be the topological ordering of vertices).
  • In Tarjan's approach we loop through each vertex of the graph
    • If we haven't visited the vertex before we run DFS on that vertex.
    • We mark each vertex in the DFS routine as visited before exploring each of the vertex's neighbours.
    • If a neighbour has already been visited, it is skipped.
    • Before each DFS execution completes, it will add the current vertex to a Stack or prepend it to a List.
    • The List or Stack represents the topological ordering of vertices.
    • If we use a Stack we can pop each vertex from the stack, and the order in which they are popped will be the topological order.
    • For List, if we always prepend (add new vertices at the start), then the list will represent our topological ordering at completion of the algorithm.
    • Stack has cost after adding all vertices to it. List has a cost each time we add to it (can't append, have to prepend).
    • We could also append to a collection (like List) and then reverse it after adding all vertices.
    • Either way we choose will incur an O(v) cost - so it is a matter of preference.
  • Run time of DFS for topological sort of an adjacency list is linear O(v + e) - where v is number of vertices and e is number of edges. Space complexity is O(v). For an adjacency matrix, both are O(v^2).
  • Some applications of topological sort:
    • Can be used to detect cycles and find strongly connected components in graphs.
    • School: class prerequisites & what order you have to take the classes in.
    • Build systems: What order should the dependencies get built in? Also helps to enforce that there are no circular dependencies (as topological sort detects cycles).

Below are implementations of DFS for topological sorting of adjacency list & adjacency matrix representations of graphs:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Feb 11 by:

Discussion

markdown guide