大家好，我正在尝试解决此问题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();
}
}
}
一种可能的方法是修改由Khan，（1962）指定的算法，其中使用以下算法来计算拓扑排序：
L←将包含已排序元素的空列表
S←所有没有输入边的节点的集合
当S为非空时
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如果图有边，则
return error (graph has at least one cycle)别的
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。
我认为该解决方案不会为您提供所需的答案，但是非常欢迎您尝试并实施它。
还请检查此算法。
笔记：
在重新阅读您的问题后，我将避免发布此信息，但是我决定反对，因为此信息可能对您有用。
祝你好运。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句