ronith
9/23/2018 - 9:19 AM

All Topological Sorts of a Directed Acyclic Graph

We can go through all possible ordering via backtracking , the algorithm step are as follows :

Initialize all vertices as unvisited. Now choose vertex which is unvisited and has zero indegree and decrease indegree of all those vertices by 1 (corresponding to removing edges) now add this vertex to result and call the recursive function again and backtrack. After returning from function reset values of visited, result and indegree for enumeration of other possibilities.

All Topological Sorts.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
#include <bits/stdc++.h>
using namespace std;

class graph {
    int v;
    list<int> *adj;
    vector<int> indegree;
public:
    graph (int v) {
        this->v= v;
        adj= new list<int> [v];
        for (int i=0;i<v; i++)
            indegree.push_back(0);

    }
    void addEdge (int u, int w) {
        adj[u].push_back(w);
        indegree[w]++;
    }
    void TS();
    void TSUtil (bool [], vector<int> &);
};
void graph::TSUtil(bool visited[], vector <int> &res) {
    bool flag= false;

    for (int i=0;i<v; i++) {
        if (indegree[i]==0 && !visited[i]) {
            list<int>::iterator j;
            for (j= adj[i].begin(); j!= adj[i].end(); ++j)
                indegree[*j]--;

            res.push_back(i);
            visited[i]= 1;
            TSUtil(visited, res);

            visited[i]=0;
            res.erase(res.end()-1);
            for (j= adj[i].begin(); j!= adj[i].end(); ++j)
                indegree[*j]++;
            flag= 1;
        }
    }
    if (!flag) {
        for (int i = 0; i < res.size(); i++)
            cout << res[i] << " ";
        cout << endl;
    }
}
void graph::TS() {
    bool visited[v]= {0};
    vector<int> res;

    TSUtil(visited, res);
}

int main() {
    graph g(6);

    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    g.TS();
}