☍ Topological Sorting – Complete In-Depth Explanation

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. It's like determining the order in which tasks must be performed given their dependencies.

📌 Why is Topological Sorting Important?

• 💡 Task Scheduling: Determining the order of tasks based on dependencies.
• ⚙️ Dependency Resolution: Resolving dependencies in software projects.
• 🚀 Course Scheduling: Ordering courses based on prerequisites.

📌 Understanding Topological Sorting with an Example

Consider the following DAG representing course prerequisites:

                      A --> B
                      |    ^
                      v    |
                      C --> D
                      |    ^
                      v    |
                      E --> F
                

A topological sort of this graph would give a valid order in which the courses can be taken, respecting the prerequisites. One possible topological order is: A, C, E, B, D, F. (There can be multiple valid topological orderings.)

🔹 Key Points

• Only applicable to directed acyclic graphs (DAGs).
• Multiple topological orderings may exist.
• Represents a valid sequence of tasks respecting dependencies.

🛠 Solution Approaches

There are two main approaches to topological sorting:

📌 1. Depth-First Search (DFS)

1. Perform DFS on the graph.
2. During the backtracking phase of DFS (after visiting all descendants of a vertex), push the vertex onto a stack.
3. Reverse the stack to get the topological order.

📌 2. Kahn's Algorithm (using indegree)

1. Calculate the indegree (number of incoming edges) of each vertex.
2. Add vertices with indegree 0 to a queue.
3. While the queue is not empty:
• Dequeue a vertex u.
• For each neighbor v of u:
• Decrement indegree of v.
• If indegree of v becomes 0, enqueue v.

                  #include 
                  #include 
                  #include 
                  #include 
              
                  using namespace std;
              
                  // DFS-based topological sort
                  void dfs(int v, vector>& adj, vector& visited, stack& st) {
                      visited[v] = true;
                      for (int u : adj[v]) {
                          if (!visited[u]) {
                              dfs(u, adj, visited, st);
                          }
                      }
                      st.push(v);
                  }
              
                  vector topologicalSortDFS(int n, vector>& adj) {
                      vector visited(n, false);
                      stack st;
                      for (int v = 0; v < n; v++) {
                          if (!visited[v]) {
                              dfs(v, adj, visited, st);
                          }
                      }
                      vector result;
                      while (!st.empty()) {
                          result.push_back(st.top());
                          st.pop();
                      }
                      return result;
                  }
              
                  // Kahn's algorithm
                  vector topologicalSortKahn(int n, vector>& adj) {
                      vector indegree(n, 0);
                      for (int v = 0; v < n; v++) {
                          for (int u : adj[v]) {
                              indegree[u]++;
                          }
                      }
              
                      queue q;
                      for (int v = 0; v < n; v++) {
                          if (indegree[v] == 0) {
                              q.push(v);
                          }
                      }
              
                      vector result;
                      while (!q.empty()) {
                          int u = q.front();
                          q.pop();
                          result.push_back(u);
                          for (int v : adj[u]) {
                              indegree[v]--;
                              if (indegree[v] == 0) {
                                  q.push(v);
                              }
                          }
                      }
                      return result;
                  }
              
              
              
                  int main() {
                      int n = 6; // Number of vertices
                      vector> adj(n);
              
                      // Example graph (replace with your graph)
                      adj[0].push_back(1);
                      adj[0].push_back(2);
                      adj[2].push_back(3);
                      adj[1].push_back(3);
                      adj[2].push_back(4);
                      adj[4].push_back(5);
              
              
                      cout << "Topological Sort (DFS): ";
                      vector sortedDFS = topologicalSortDFS(n, adj);
                      for (int v : sortedDFS) cout << v << " ";
                      cout << endl;
              
                      cout << "Topological Sort (Kahn's): ";
                      vector sortedKahn = topologicalSortKahn(n, adj);
                      for (int v : sortedKahn) cout << v << " ";
                      cout << endl;
              
                      return 0;
                  }
                

⏳ Time Complexity Analysis

Both DFS-based and Kahn's algorithm have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.

🌍 Real-World Applications of Topological Sorting

• 🏗️ Project management (task scheduling).
• 💻 Compilers (dependency resolution).
• 📚 Course scheduling.

🔗 Next Topics

• graph
• Graph Algorithms