Topological Sort: Understanding the Concept and 2 Applications

Topological Sorting is an important concept in graph theory, especially for Directed Acyclic Graphs (DAGs). It gives a linear order of vertices so that for every directed edge u → v, vertex u comes before v in the order. This is useful when tasks or events need to happen in a specific sequence because of dependencies between them.

Key Points to Note

1. Cycle-Free Graphs: Topological sort can only be applied to DAGs. If the graph contains cycles, it is impossible to establish a valid order since the circular dependency makes it ambiguous to determine which node comes first.

2. Multiple Sort Orders: Depending on the graph structure, there can be multiple valid topological orderings. Each one respects the dependency constraints defined by the edges of the graph.

Uses of Topological Sorting

1. Task Scheduling: When tasks depend on each other, such as task B needing task A to be completed first, we can model this as:

   1.  A → B
      

2. Course Prerequisites: In academic settings, courses often have prerequisites. For example, if taking an Algebra (Al) course requires completing Basic Math (BM) first, the graph would be:

   1.  BM → Al
      

Algorithm for Topological Sorting

We will employ Depth-First Search (DFS) to perform topological sorting. The idea is to recursively visit each vertex, mark it as visited, and only add it to the topological order after all its dependencies have been visited. The topological order is obtained by reversing the stack in which the vertices are stored.

Steps:

1. Pick a vertex (v) from the graph and mark it as the current vertex.

2. If the current vertex has not been visited, do the following:

   • Add the vertex to a visited set.

   • Recursively visit all its child vertices.

   • Once all child vertices are processed, push the current vertex onto the stack.

3. After all vertices are processed, reverse the stack to get the topological order.

   C++ Code for Topological Sorting

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

// Function to perform DFS and store vertices in the stack after processing
void dfs(int vertex, const vector<vector<int>>& graph, unordered_set<int>& visited, stack<int>& Stack) {
    // Mark the current node as visited
    visited.insert(vertex);

    // Recur for all the vertices adjacent to this vertex
    for (int child : graph[vertex]) {
        if (visited.find(child) == visited.end()) {
            dfs(child, graph, visited, Stack);
        }
    }

    // Push the current vertex to the stack after all adjacent vertices are processed
    Stack.push(vertex);
}

// Function to perform topological sorting
vector<int> topologicalSort(const vector<vector<int>>& graph, int V) {
    unordered_set<int> visited;  // Set to keep track of visited nodes
    stack<int> Stack;            // Stack to store the topological order

    // Perform DFS for each vertex
    for (int i = 0; i < V; i++) {
        if (visited.find(i) == visited.end()) {
            dfs(i, graph, visited, Stack);
        }
    }

    // Extract the vertices from the stack to get the topological ordering
    vector<int> topoOrder;
    while (!Stack.empty()) {
        topoOrder.push_back(Stack.top());
        Stack.pop();
    }

    return topoOrder;  // Return the topological order
}

int main() {
    // Example DAG
    int V = 8;  // Number of vertices
    vector<vector<int>> graph(V);

    // Adding edges to the graph
    graph[0] = {1};        // 1 → 2
    graph[1] = {2, 3};     // 2 → 3, 4
    graph[2] = {3};        // 3 → 4
    graph[3] = {4};        // 4 → 5
    graph[4] = {5};        // 5 → 6
    graph[5] = {7};        // 6 → 8
    graph[6] = {5};        // 7 → 6

    // Perform Topological Sort
    vector<int> topologicalOrder = topologicalSort(graph, V);

    // Print the topological order
    cout << "Topological Order: ";
    for (int v : topologicalOrder) {
        cout << v + 1 << " ";  // Output the order with vertices 1-indexed
    }

    return 0;
}

Explanation:

1. Graph Representation: The graph is represented as an adjacency list, where each index in the vector corresponds to a vertex, and its value is a vector of vertices it points to.

2. DFS Function:

   • The dfs function is a recursive function that visits each vertex, marks it as visited, and recursively visits its adjacent vertices.

   • After visiting all adjacent vertices of a node, the node is pushed onto the stack.

3. Topological Sort Function:

   • The topologicalSort function iterates over all vertices and calls dfs on any unvisited vertex. After all vertices are processed, the stack contains the topological ordering.

4. Printing the Topological Order:

   • The vertices are extracted from the stack (in reverse order) to produce the topological sort, which is then printed.

Time Complexity:

• The time complexity of this approach is O(V + E), where V is the number of vertices and E is the number of edges, ensuring efficient traversal of all vertices and edges.

Thank you for reading! If you enjoyed this post, please consider sharing it with others or subscribing for future updates. Happy coding!