Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-05-13· OpenAIAi2 WildChat-4.8M (AI2)

Please provided detailed tutorial about topological sorting of a direct acyclic graph.…

  1. User

    Please provided detailed tutorial about topological sorting of a direct acyclic graph. Additionally, please provide a commented C++ code to clearly demonstrate it.

  2. Assistant

    Tutorial on Topological Sorting of a Directed Acyclic Graph (DAG)

    Topological Sorting: Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge ( u \rightarrow v ), vertex ( u ) comes before ( v ) in the ordering. Topological sorting is used in various applications like task scheduling, course prerequisite ordering, etc. Note that a topological sort is only possible for a graph if and only if the graph has no directed cycles (i.e., it is a DAG).

    Algorithms for Topological Sorting

    There are two primary algorithms for topological sorting:

    1. Kahn's Algorithm (Using In-degree):
    2. Depth-First Search (DFS) Based Algorithm:

    Depth-First Search (DFS) Based Algorithm:

    This algorithm leverages the property of DFS where it explores all vertices in depth before backtracking. It uses a stack to store the vertices in reverse order of their finishing times.

    Algorithm Steps:

    1. Mark all vertices as not visited.
    2. For each vertex:
      • If the vertex is not visited, perform a DFS from it.
      • During DFS, mark the vertex as visited.
      • After exploring all vertices from the current vertex, add it to the stack.
    3. Once all vertices are processed, the stack contains the topologically sorted order.

    Example and C++ Code

    Let's demonstrate the DFS-based algorithm with a concrete example.

    Example:

    Consider a DAG with the following edges:

    0 -> 1
    0 -> 2
    1 -> 3
    2 -> 3
    

    Topological Sort of the given graph could be 0 -> 2 -> 1 -> 3 or 0 -> 1 -> 2 -> 3.

    #include <iostream>
    #include <vector>
    #include <stack>
    
    using namespace std;
    
    // A utility function to add an edge in a directed graph.
    void addEdge(vector<int> adj[], int u, int v) {
        adj[u].push_back(v);
    }
    
    // A utility function to perform DFS from a given vertex.
    void DFS(int v, vector<bool> &visited, stack<int> &Stack, const vector<int> adj[]) {
        // Mark the current node as visited.
        visited[v] = true;
    
        // Recur for all the vertices adjacent to this vertex.
        for (int i : adj[v]) {
            if (!visited[i]) {
                DFS(i, visited, Stack, adj);
            }
        }
    
        // Push the current vertex to the stack which stores the result.
        Stack.push(v);
    }
    
    // Function to perform topological sort.
    void topologicalSort(int V, const vector<int> adj[]) {
        stack<int> Stack;  // Stack to store the topological sort.
        vector<bool> visited(V, false);  // Mark all vertices as not visited.
    
        // Call the recursive helper function to store topological sort.
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFS(i, visited, Stack, adj);
            }
        }
    
        // Print the contents of stack.
        while (!Stack.empty()) {
            cout << Stack.top() << " ";
            Stack.pop();
        }
    }
    
    // Driver program to test the functions.
    int main() {
        // Number of vertices in the graph.
        int V = 4;
    
        // Creating an adjacency list for the directed graph.
        vector<int> adj[V];
    
        // Adding edges to the graph.
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 3);
    
        // Perform topological sort.
        cout << "Topological Sort of the given graph: ";
        topologicalSort(V, adj);
    
        return 0;
    }
    

    Explanation of the C++ Code:

    1. addEdge Function:

      • Adds a directed edge from vertex u to vertex v in the graph.
    2. DFS Function:

      • A recursive function that visits all the vertices reachable from a given vertex v.
      • Marks the vertex as visited.
      • Recursively calls DFS for all its unvisited adjacent vertices.
      • Pushes the vertex to the stack after visiting its adjacent vertices.
    3. topologicalSort Function:

      • Initializes a stack to store the order and a visited array to keep track of visited vertices.
      • Calls DFS for all unvisited vertices to generate the topological order.
      • Prints vertices in stack which represents topologically sorted order.
    4. main Function:

      • Defines the number of vertices.
      • Sets up the graph by adding edges.
      • Calls the topologicalSort function to perform and print the sorting.

    This completes the tutorial and code demonstration of topological sorting of a directed acyclic graph using the DFS-based approach in C++.

  3. User

    Please provide also explanation and a commented example of Kahn's Algorithm.

  4. Assistant

    Kahn's Algorithm for Topological Sorting

    Kahn's Algorithm: Kahn's Algorithm is an iterative algorithm specifically designed to handle topological sorting of a Directed Acyclic Graph (DAG) by using the in-degree (number of incoming edges) of each vertex.

    Steps of Kahn's Algorithm:

    1. Calculate In-degrees: Compute the in-degree for each vertex.
    2. Initialize Queue: Initialize a queue and enqueue all vertices with in-degree 0.
    3. Process Vertices:
      • While the queue is not empty:
        • Dequeue a vertex.
        • Add it to the topological order.
        • Decrement the in-degree of its adjacent vertices.
        • If the in-degree of an adjacent vertex becomes zero, enqueue it.
    4. Check for Cycles:
      • If all vertices are processed, the graph does not have cycles.
      • If there are vertices that haven’t been processed, the graph contains a cycle.

    Example and C++ Code

    Let's use the same DAG example as before: Consider a DAG with the following edges:

    0 -> 1
    0 -> 2
    1 -> 3
    2 -> 3
    

    Topological Sort of the given graph could be 0 -> 2 -> 1 -> 3 or 0 -> 1 -> 2 -> 3.

    C++ Code with Explanation:

    #include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    // Function to add an edge to the graph.
    void addEdge(vector<int> adj[], int u, int v) {
        adj[u].push_back(v);
    }
    
    // Function to perform topological sort using Kahn's Algorithm.
    void topologicalSort(int V, vector<int> adj[]) {
        
        // Vector to store in-degrees of all vertices.
        vector<int> in_degree(V, 0);
        
        // Compute in-degrees of all vertices.
        for (int u = 0; u < V; u++) {
            for (int v : adj[u]) {
                in_degree[v]++;
            }
        }
        
        // Queue to store vertices with in-degree 0.
        queue<int> q;
        
        // Enqueue vertices with in-degree 0.
        for (int i = 0; i < V; i++) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }
        
        // List to store the topological order.
        vector<int> topo_order;
        
        // Initialize count of visited vertices.
        int count = 0;
        
        // One by one dequeue vertices from queue and enqueue their adjacent vertices.
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topo_order.push_back(u);
            
            // Traverse all adjacent vertices of dequeued vertex u and decrease their in-degree by 1.
            for (int v : adj[u]) {
                if (--in_degree[v] == 0) {
                    q.push(v);
                }
            }
            
            count++;
        }
        
        // Check if there was a cycle in the graph.
        if (count != V) {
            cout << "There exists a cycle in the graph\n";
            return;
        }
        
        // Print the topological order.
        for (int i : topo_order) {
            cout << i << " ";
        }
        cout << endl;
    }
    
    // Driver code.
    int main() {
        // Number of vertices in the graph.
        int V = 4;
        
        // Create a graph.
        vector<int> adj[V];
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 3);
        
        // Perform topological sort.
        cout << "Topological Sort of the given graph: ";
        topologicalSort(V, adj);
        
        return 0;
    }
    

    Explanation of the C++ Code:

    1. addEdge Function:

      • Adds a directed edge from vertex u to vertex v in the graph.
    2. topologicalSort Function:

      • Initializes a vector in_degree to store the in-degrees of all vertices.
      • Computes the in-degrees by iterating through the adjacency list.
      • Initializes a queue to store vertices with in-degree 0 and enqueues them.
      • Initializes a vector topo_order to store the topological order and a counter count for keeping track of the number of processed vertices.
      • While the queue is not empty:
        • Dequeues a vertex and adds it to topo_order.
        • Decrements the in-degrees of its adjacent vertices and enqueues any that subsequently have an in-degree of 0.
        • Increments the count of processed vertices.
      • After processing all vertices, checks if count matches the number of vertices (to detect cycles).
      • Prints the topological order if no cycle is detected; otherwise, prints that a cycle exists.
    3. main Function:

      • Defines the number of vertices.
      • Sets up the graph by adding edges.
      • Calls the topologicalSort function to perform and print the sorting.

    This concludes the explanation and commented example of Kahn's Algorithm for topological sorting in C++.