求有向图全部拓扑序列

All Topological Sorts，在前一章中Topological Sorting，已经讨论了拓扑排序的原理及其实现算法，但只是实现了从单一一个入度为0的节点进行的拓扑排序。本章主要来讨论一下，如何求一个有向无环图的所有拓扑排序序列。

问题描述

因为在一个有向无环图中，并非所有顶点间都有路径可达，而且可能有些点是孤立点，这导致了同一个有向图可能会有多个拓扑排序，因为显然孤立点在拓扑序列中的位置是任意的，各子连通子图间的先后次序也可以互换。

那么如何来求一个有向无环图的所有拓扑排序序列呢？我们可以通过修改前一篇文章中的算法达到这个目标，即在原有拓扑排序过程的基础上，加上回溯法，并对所有入度为0的顶点应用这个带回溯的拓扑排序算法，

算法思路

1. 初始化所有顶点为未访问状态；
2. 依次对所有入度为0的顶点，先把其入度降1，然后把该顶点放到排序序列中，然后递归访问它的所有邻接点，最后回溯；
3. 在函数最终返回后，就得到了一个拓扑序列，然后重置访问状态和入度，继续寻找其它拓扑序列。

代码实现

#include <bits/stdc++.h>
using namespace std;

class Graph
{
    int V;    // No. of vertices

    // Pointer to an array containing adjacency list
    list<int> *adj;

    // Vector to store indegree of vertices
    vector<int> indegree;

    // A function used by alltopologicalSort
    void alltopologicalSortUtil(vector<int>& res,
                                bool visited[]);

public:
    Graph(int V);   // Constructor

    // function to add an edge to graph
    void addEdge(int v, int w);

    // Prints all Topological Sorts
    void alltopologicalSort();
};

//  Constructor of graph
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];

    // Initialising all indegree with 0
    for (int i = 0; i < V; i++)
        indegree.push_back(0);
}

//  Utility function to add edge
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v's list.

    // increasing inner degree of w by 1
    indegree[w]++;
}

//  Main recursive function to print all possible
//  topological sorts
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);
}

int main()
{
    // Create a graph given in the above diagram
    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);

    cout << "All Topological sorts\\n";

    g.alltopologicalSort();

    return 0;
}