java - 如何得到拓扑排序的所有解

Question

大家好，我正在努力解决这个问题http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=813我意识到它想要获得拓扑排序问题的所有解决方案，我知道如何只获得一个可能的解决方案，这是我的代码 http://ideone.com/IiQxiu

static ArrayList<Integer> [] arr;  
static int visited [];
static Stack<Integer> a = new Stack<Integer>();
static boolean flag=false;

public static void graphcheck(int node){  //method to check if there is a cycle in the graph
    visited[node] = 2;
    for(int i=0;i<arr[node].size();i++){
        int u =arr[node].get(i);
        if(visited[u]==0){
            graphcheck(u);
        }else if(visited[u]==2){
                flag=true;
                return; 
            }
    }
    visited[node] = 1;
}

public static void dfs2(int node){            //method to get one possible topological sort which I want to extend to get all posibilites
    visited[node] = 1;
    for(int i=0;i<arr[node].size();i++){
        int u =arr[node].get(i);
        if(visited[u]==0){
            dfs2(u);
        }   
    }
    a.push(node);
}

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tc = Integer.parseInt(br.readLine());
    for(int k=0;k<tc;k++){
        br.readLine();

        String h[]= br.readLine().split(" ");
        int n= h.length;
        arr=new ArrayList[n];
        visited = new int[n];
        for( int i = 0; i < n; i++) {
            arr[ i] = new ArrayList<Integer>();
        }
        String q[]=br.readLine().split(" ");
        int y=q.length;
        for(int i=0;i<y;i++){
            int x=0;
            int z=0;
            for(int j=0;j<n;j++){
                if(q[i].charAt(0)==h[j].charAt(0)){
                    x=j;
                }else if(q[i].charAt(2)==h[j].charAt(0)){
                    z=j;
                }
            }
            if(q[i].charAt(1)=='<'){
                        arr[x].add(z);
            }
        }
        for(int i=0;i<n;i++){
            if(visited[i]==0)
                graphcheck(i);
        }
        if(flag){
            System.out.println("NO");
        }else{
        a.clear();
        Arrays.fill(visited, 0);
        for(int i=0;i<n;i++){
            if(visited[i]==0){
                dfs2(i);
            }   
        }
        int z= a.size();
        for(int i=0;i<z;i++){
            int x =a.pop();
            System.out.print(h[x]+" ");
        }
        System.out.println();
    }


}
}

Answer 1

一种可能的方法是修改 Khan, (1962) 指定的算法，其中使用以下算法计算拓扑排序:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges

while S is non-empty do
    remove a node n from S
    insert n into L

    for each node m with an edge e from n to m do
        remove edge e from the graph
        
        if m has no other incoming edges then
            insert m into S

    if graph has edges then
        return error (graph has at least one cycle)
    else 
        return L (a topologically sorted order)

这会计算一个 拓扑排序，以便生成所有可能的排序。要获得所有可能的排序，您可以将结果视为一棵树，其中根是第一个节点，节点的每个子节点是下一个值之一。给定一张图:

    1 -> 3 -> 8 
    |    |    |
    |    v    |
    |    7    |
    |     \   |
    |      \_ v
    +--> 5 -> 9
      

这棵树可能看起来像:

        1
       / \
      3   5
     /|\  |
    7 8 9 9
    | |
    9 9

但是，在重新阅读您的问题后:

Given a list of variable constraints of the form A < B, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the contraints A < B and A < C there are two orderings of the variables A, B and C that are consistent with these constraints: ABC and ACB.

我认为此解决方案不会为您提供所需的答案，但非常欢迎您尝试并实现它。

另请查看 this algorithm .

注意:

在重新阅读您的问题后，我本来打算不发布此内容，但我决定不发布，因为此信息可能对您有用。

祝你好运。