Please provided detailed tutorial about topological sorting of a direct acyclic graph.…
- User
Please provided detailed tutorial about topological sorting of a direct acyclic graph. Additionally, please provide a commented C++ code to clearly demonstrate it.
- 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:
- Kahn's Algorithm (Using In-degree):
- 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:
- Mark all vertices as not visited.
- 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.
- 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 -> 3Topological Sort of the given graph could be
0 -> 2 -> 1 -> 3or0 -> 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:
-
addEdge Function:
- Adds a directed edge from vertex
uto vertexvin the graph.
- Adds a directed edge from vertex
-
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.
- A recursive function that visits all the vertices reachable from a given vertex
-
topologicalSort Function:
- Initializes a stack to store the order and a
visitedarray 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.
- Initializes a stack to store the order and a
-
main Function:
- Defines the number of vertices.
- Sets up the graph by adding edges.
- Calls the
topologicalSortfunction 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++.
- User
Please provide also explanation and a commented example of Kahn's Algorithm.
- 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:
- Calculate In-degrees: Compute the in-degree for each vertex.
- Initialize Queue: Initialize a queue and enqueue all vertices with in-degree 0.
- 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.
- While the queue is not empty:
- 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 -> 3Topological Sort of the given graph could be
0 -> 2 -> 1 -> 3or0 -> 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:
-
addEdge Function:
- Adds a directed edge from vertex
uto vertexvin the graph.
- Adds a directed edge from vertex
-
topologicalSort Function:
- Initializes a vector
in_degreeto 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_orderto store the topological order and a countercountfor 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
countof processed vertices.
- Dequeues a vertex and adds it to
- After processing all vertices, checks if
countmatches the number of vertices (to detect cycles). - Prints the topological order if no cycle is detected; otherwise, prints that a cycle exists.
- Initializes a vector
-
main Function:
- Defines the number of vertices.
- Sets up the graph by adding edges.
- Calls the
topologicalSortfunction to perform and print the sorting.
This concludes the explanation and commented example of Kahn's Algorithm for topological sorting in C++.