All Topological Sorts of a Directed Acyclic Graph - GeeksforGeeks

All Topological Sorts of a Directed Acyclic Graph - GeeksforGeeks
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
Given a DAG, print all topological sorts of the graph.

1. Initialize all vertices as unvisited.
2. 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.
3. After returning from function reset values of visited, result and indegree for enumeration of other possibilities.

void Graph::alltopologicalSortUtil(vector<int>& res,

                                   bool visited[])

{

    // To indicate whether all topological are found

    // or not

    bool flag = false;

 

    for (int i = 0; i < V; i++)

    {

        //  If indegree is 0 and not yet visited then

        //  only choose that vertex

        if (indegree[i] == 0 && !visited[i])

        {

            //  reducing indegree of adjacent vertices

            list<int>:: iterator j;

            for (j = adj[i].begin(); j != adj[i].end(); j++)

                indegree[*j]--;

 

            //  including in result

            res.push_back(i);

            visited[i] = true;

            alltopologicalSortUtil(res, visited);

 

            // resetting visited, res and indegree for

            // backtracking

            visited[i] = false;

            res.erase(res.end() - 1);

            for (j = adj[i].begin(); j != adj[i].end(); j++)

                indegree[*j]++;

 

            flag = true;

        }

    }

 

    //  We reach here if all vertices are visited.

    //  So we print the solution here

    if (!flag)

    {

        for (int i = 0; i < res.size(); i++)

            cout << res[i] << " ";

        cout << endl;

    }

}

 

//  The function does all Topological Sort.

//  It uses recursive alltopologicalSortUtil()

void Graph::alltopologicalSort()

{

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

 

    vector<int> res;

    alltopologicalSortUtil(res, visited);

}

Read full article from All Topological Sorts of a Directed Acyclic Graph - GeeksforGeeks