Understanding Topological Sort, With Examples

Key Points

• Topological sort is used to arrange data values according to their relative dependencies, often used with directed acyclic graphs (DAGs).
• Topological sort can be implemented using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithms.
• Applications of topological sort include task scheduling, project management, and organizing curriculums.
• The time complexity of topological sort is O(V + E), while the space complexity is O(V), where V is the number of vertices and E is the number of edges.

Sorting is a fundamental concept in computer science, to help us understand and work with our data better. While sorting into ascending or descending order is common, sometimes this isn’t appropriate for our situation. Being able to sort data values according to their relative dependencies can be useful when we need to highlight the relationship between elements or illustrate the sequential steps in a process. One way to achieve this is through the topological sort algorithm. In this article, we’re going to explain how Topological sort works, ways to implement it, and its applications.

What Is Topological Sort?

In computer science, topology refers to the arrangement and connection of nodes in a graph, which represent elements. We use Topological sort with directed acyclic graphs (DAGs), which have nodes connected to each other in specific directions. There are also no cycles present, meaning we cannot traverse through some combination of directed edges and end up at the same vertex.

The general idea behind Topological sort is finding a logical sequence between the nodes. The elements are arranged so that each directed edge points logically from previous elements to later elements. We can also describe this as only visiting a node once all the nodes directly pointing to it have been visited. Topological sort can be implemented with either DFS (Depth-First Search) or BFS (Breadth-First Search), depending on your needs. Let’s examine both of these next.

DFS-Based Topological Sort

As the name implies, DFS works by prioritizing “depth”, meaning that it fully explores one branch leading off a vertex as far as it can before going down another branch. By keeping track of visited and unvisited nodes, we can use DFS to identify graph cycles and find connections, or in this case, for topological sorting.

We can break the pseudocode down as follows:

function topologicalSortDFS(graph):
    visited = []
    stack = []

    for each vertex in graph:
        if vertex is not visited:
            DFS(vertex, visited, stack, graph)

    return reverse(stack)

function DFS(vertex, visited, stack, graph):
    mark vertex as visited

    for each neighbor in graph[vertex]:
        if neighbor is not visited:
            DFS(neighbor, visited, stack, graph)

    push vertex onto stack

First, we must define the sort function, and use a list to keep track of visited nodes. We must also implement a stack structure to store the sorted nodes in reverse order. This is because stacks work by the Last-In-First-Out (LIFO) principle, meaning the last visited vertex will be added to the top of the stack. Therefore, we must reverse the order to obtain the correct sequence.

We use a for loop to iterate over every vertex. If the vertex has not been visited, we perform the DFS algorithm on it. This algorithm takes the current vertex, the list of visited vertices, the stack, and the graph as parameters. We also performed the algorithm on each neighboring vertex that hasn’t been visited. Once this is complete, we add the vertex to the stack.

Finally, we reverse the obtained stack as mentioned before to obtain our topological sorting.

Example Implementation

For a simple example, consider this graph:

We have 5 nodes here – A, B, C, D, and E. This is a directed graph where each node points to another node, with the exception of nodes B and C. We can carry out topological sort using DFS in Python on this graph as follows:

def dfs_topological_sort(graph):
    visited = set()
    stack = []

    def dfs(vertex):
        visited.add(vertex)

        if vertex in graph:
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    dfs(neighbor)

        stack.append(vertex)

    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)

    return stack[::-1]

graph = {
    'C': ['D', 'A'],
    'D': ['A', 'B'],
    'A': ['B', 'E']
}

sorted_vertices = dfs_topological_sort(graph)
print(sorted_vertices)

As briefly mentioned before, we define the algorithm, in this case, “dfs_topological_sort”, and implement a list and a stack.

The first line of the DFS function adds the current vertex to the visited list. DFS is then called for each neighbor to this vertex that hasn’t been visited yet. The vertex is then added to the stack, and every other vertex is visited. We’ve inputted our graph data at the end as a dictionary, called the sort function, and printed the sorted vertices. We can see these in the order [C, D, A, E, B] in the image below.

BFS-Based Topological Sort

The other way to implement topological sort is by using the BFS algorithm. Instead of fully exploring the depth of the branches first, BFS works by exploring the nodes at each depth “level” before moving down a level. Instead of a stack, we use a queue to keep track of the visited vertices.

We can write the pseudocode for this as follows:

function topologicalSortBFS(graph):
    inDegree = {}
    queue = []
    result = []

    for each vertex in graph:
        inDegree[vertex] = 0

    for each vertex in graph:
        for each neighbor in graph[vertex]:
            inDegree[neighbor] += 1

    for each vertex in graph:
        if inDegree[vertex] == 0:
            add vertex to queue

    while queue is not empty:
        current = remove vertex from front of queue
        add current to result list

        for each neighbor in graph[current]:
            decrement in-degree of neighbor
            if in-degree of neighbor becomes 0:
                add neighbor to queue

    return result

As we did before, we define the function. This time, we use a dictionary to store the in-degree values for each node. These are simply the number of directed edges pointing to the node. We also initialized an empty queue, as well as a list to store the results.

Three for loops are then used to iterate over each of the vertices. The first sets the in-degree value to 0, and the second increments this by 1 for each neighboring vertex. The third loop then adds each vertex with an in-degree value of 0 to the queue to be processed.

The while loop removes the vertex at the front of the queue, which has no dependencies, to be processed. This is then added to the sorted list, and the in-degree of its neighbors is decremented by 1. Neighbors with an in-degree of 0 are then added to the queue.

Example Implementation

Using the same example, here is the code block to implement topological sort using BFS:

from collections import deque

def bfs_topological_sort(graph):
    inDegree = {}
    queue = deque()
    result = []

    for vertex in graph:
        inDegree[vertex] = 0

    for vertex in graph:
        for neighbor in graph[vertex]:
            inDegree[neighbor] += 1

    for vertex in graph:
        if inDegree[vertex] == 0:
            queue.append(vertex)

    while queue:
        current = queue.popleft()
        result.append(current)

        for neighbor in graph[current]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                queue.append(neighbor)

    return result

graph = {
    'C': ['D', 'A'],
    'D': ['A', 'B'],
    'A': ['B', 'E'],
    'B': [],
    'E': []
}

sorted_vertices = bfs_topological_sort(graph)
print(sorted_vertices)

First, we must implement the “deque” class, which allows us to use a double-ended queue as the data structure.

We then define the BFS function, “bfs_topological_sort”, which takes “graph” as its input. Following that, we create the empty dictionary, “inDegree”, the empty queue, “queue”, and the empty list, “list”.

The first for loop adds each node as a key to the dictionary. The next two loops calculate the in-degree and add nodes with an in-degree of 0 to the queue.

We then remove vertices according to the while loop and add sorted vertices to the sorted list until the queue is empty. Neighboring nodes are explored once their dependencies become 0.

Finally, as before, we input our graph data, call the function and print the list of sorted vertices. We can see the output in the image.

Note that the BFS result of [C, D, A, B, E] differs from the DFS result of [C, D, A, E, B]. This is because of the different ways that the two algorithms work. Because DFS works by exploring as far down a branch as possible before backtracking, it visits A and E before it backtracks to visit B last. BFS, however, visits the nodes on each level before it moves down. Therefore, it still visits A after D, but B is at the same depth level as A, so it visits B before E.

Applications of Topological Sort

Since Topological sort is useful when we need a logical sequence, it can be used in many applications where we have tasks or events that follow a particular order. This can be something as simple as cooking according to a recipe, where certain instructions must come before others (e.g. mixing the cake batter before pouring it into the tin). Usually, Topological sort is used to handle more complex situations that revolve around workflows and task scheduling. If we’re managing a project, building a program or even organizing a student’s curriculum, certain elements must precede others for the entire process to make sense. These are all situations where Topological sort can be helpful.

Complexity of Topological Sort

The time and space complexity of Topological sort depends on the implementation, but for DFS and BFS, we can consider them identical. We must visit each vertex and edge of the graph once, whichever function we’re using. Therefore, the time complexity is O(V + E), or proportional to the number of vertices (V) and edges (E).

In terms of space complexity, both algorithms have O(V) complexity, since we require space to store the visited vertices in both the stack and the queue. Therefore, the complexity is proportional to the number of vertices.

Wrapping Up

In conclusion, topological sort is a well-known method used to organize tasks or events based on their dependencies and logical order. It’s widely used in not only computer science but also in all kinds of organizations to optimize their workflows and schedule their tasks and courses. Whenever you’re working with graphs or trying to solve efficiency problems, topological sort will probably come in handy.

The image featured at the top of this post is ©Song_about_summer/Shutterstock.com.