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

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

给定 A < B 形式的变量约束列表，您将编写一个程序，打印与约束一致的变量的所有排序。例如，给定约束 A < B 和 A < C，变量 A、B 和 C 的两个排序与这些约束一致：ABC 和 ACB。

我不相信这个解决方案会为您提供您正在寻找的答案，但我们非常欢迎您尝试并实施它。

另请查看此算法。

笔记：

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

祝你好运。

Answer 2

为未来的观众添加解决方案：

要打印拓扑排序的所有解决方案，我们遵循以下方法：

1. 将所有顶点初始化为未标记。

2. 现在选择未标记且入度为零的顶点，并将所有这些顶点的入度减少 1（对应于删除边）。

3. 现在将此顶点添加到列表中并再次调用递归函数并回溯。

4. 从函数返回后，将标记、列表和入度的值重置为枚举其他可能性。

下面的代码——

class GraphAllTopSorts{
    int V;  // No. of vertices
    LinkedList<Integer>[] adj;  //Adjacency List
    boolean[] marked;   //Boolean array to store the visited nodes
    List<Integer> list;
    int[] indegree; //integer array to store the indegree of nodes

    //Constructor
    public GraphAllTopSorts(int v) {
        this.V=v;
        this.adj = new LinkedList[v];
        for (int i=0;i<v;i++) {
            adj[i] = new LinkedList<Integer>();
        }
        this.indegree = new int[v];
        this.marked = new boolean[v];
        list = new ArrayList<Integer>();
    }

    // function to add an edge to graph
    public void addEdge(int v, int w){
        adj[v].add(w);
        // increasing inner degree of w by 1
        indegree[w]++;
    }

    // Main recursive function to print all possible topological sorts
    public void alltopologicalSorts() {
        // To indicate whether all topological are found or not
        boolean flag = false;

        for (int w=0;w<V;w++) {

            // If indegree is 0 and not yet visited then
            // only choose that vertex
            if (!marked[w] && indegree[w]==0) {
                marked[w] = true;
                Iterator<Integer> iter = adj[w].listIterator();
                while(iter.hasNext()) {
                    int k = iter.next();
                    indegree[k]--;
                }

                // including in list
                list.add(w);
                alltopologicalSorts();

                // resetting marked, list and indegree for backtracking
                marked[w] = false;
                iter = adj[w].listIterator();
                while(iter.hasNext()) {
                    int k = iter.next();
                    indegree[k]++;
                }
                list.remove(list.indexOf(w));

                flag = true;
            }
        }

        // We reach here if all vertices are visited.
        // So we print the solution here
        if (!flag) {
            for (int w=0;w<V;w++) {
                System.out.print(list.get(w) + " ");
            }
            System.out.print("\n");
        }
    }

    // Driver program to test above functions
    public static void main(String[] args) {
        // Create a graph given in the above diagram
        GraphAllTopSorts g = new GraphAllTopSorts(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);

        System.out.println("All Topological sorts");

        g.alltopologicalSorts();
    }
}

资料来源：http ://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/

Answer 3

这是我必须基于其他算法构建的唯一非递归工作代码，因为递归在处理图形算法时确实是一个糟糕的解决方案，即使它是自然的。相反，我们可以只在拓扑排序和回溯的每个级别保留一个未访问的集合，甚至不需要额外的堆栈，只有这个数据结构。时间复杂度基本上与递归版本相同，例如最坏情况 O((m+n)*n!)。当然，置换集合 {1..n} 的所有 $n!$ 置换并调用简单的 O(m+n)is_topological_sort函数在平均情况下会更慢，并且不能用于解决足够大的挑战问题。

def topo_khan_enum(g): #O((m+n)*n!)
  topo, S, k = [], set(), 0
  inc = {u: 0 for u in g}
  for u in g:
    for v in g[u]: inc[v] += 1
  for u in g:
    if inc[u] == 0: S.add(u)
  unprocessed = {0: set(S)}
  while len(unprocessed[k]) != 0:
    while len(S) != 0:
      u = unprocessed[k].pop(); S.remove(u); k += 1
      topo.append(u)
      for v in g[u]:
        inc[v] -= 1
        if inc[v] == 0: S.add(v)
      unprocessed[k] = set(S)
    if k < len(g): raise ValueError
    yield list(topo)
    while True:
      u = topo.pop(); k -= 1
      for v in g[u]:
        if inc[v] == 0: S.remove(v)
        inc[v] += 1
      S.add(u)
      if k == 0 or len(unprocessed[k]) != 0: break
  return ()