Topological Sorting (Using DFS)

on

Topological Sorting :

  • Now question arises what is Topological Sorting?

It means Linear Ordering of vertices such that if there is an edge from [u --> v] , then u appears before v in that ordering. A graph may have more than one topological sorted order. It works on Directed Acyclic Graphs(DAGs).

  • How can we achieve that order?

So, idea here is that we will use stack to get that ordering . We'll perform DFS call on each node and if the DFS call for that node is over (no more adjacent nodes left to be visited), then we will store that node into our stack recursively.

LOGIC-
Suppose there is an edge from [1 --> 4] , then the first DFS call to be over will be DFS of 4 , after that DFS of 1. So 4 will be inserted first in our stack then 1. We are making it sure that if there is an edge between u and v , then u comes before v.

DAG


Adjacency List

Working(DFS)

As the DFS call is over for a particular node, that node is pushed into the stack.


Complexity Analysis:
  • Time Complexity: O(V+E):
The above algorithm is simply DFS with an extra STACK. So time complexity is the same as DFS.
  • Auxiliary Space:
The extra space is needed for the stack.

-------------------------------------------------------------------------------------------------------------------------

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void findTopo(int node, vector<int> adj[], stack<int> &st, vector <int> &visited){
    visited[node] = 1;
    for(auto it : adj[node]){
        if(!visited[it]){
            findTopo(it, adj, st, visited);
        }
    }
    st.push(node);
}

vector<int> topoSort(int V, vector<int> adj[]){
    stack<int> st;
    vector<int> visited ((V+1), 0);
    for(int i=1;i<=V;i++){
        if(!visited[i]){
            findTopo(i, adj, st, visited);
        }
    }
    vector <int> topo;
    while(!st.empty()){
        topo.push_back(st.top());
        st.pop();
    }
    return topo;
}

int main() {
    int V, E, u, v;
    cin >> V >> E;
    vector<int> adj[V+1];
    while(E--){
        cin >> u >> v;
        adj[u].push_back(v);
    }
    vector <int> res = topoSort(V, adj);
    for(int x : res){
        cout << x << " ";
    }
}



------------------------------------------------------------------------------

Comments

Post a Comment