有向无环图的拓扑排序

Question

有向无环图G有可能具有不同的拓扑排序吗？例如，在图中：

A --> B --> D 
     B --> E 
A --> C --> E 

我以为拓扑排序取决于每个顶点的整理时间运行深度优先搜索算法之后。不是每个完成时间都是唯一的，因此只有一种G的拓扑排序是可能的？

Answer 1

是的。您可以通过多种方式遍历图形。

在你的榜样，你可以有A，B，...或A，C，......

在拓扑排序的维基百科页面有一个更好的例子： http://en.wikipedia.org/wiki/Topological_sorting

从wiki页面上面引用：

如果拓扑排序具有在有序的连续 顶点的所有对由边缘连接的属性，那么这些边缘 形式的向Hamilton在d路径AG。如果存在Hamiltonian路径 ，则拓扑排序顺序是唯一的;没有其他任何顺序都会影响路径的边缘 。相反地​​，如果拓扑排序不构成哈密尔顿路径，则DAG将具有两个或更多个有效拓扑 排列，在这种情况下总是可以通过交换两个连续的顶点来形成第二个有效排序不是 彼此连接的边缘。因此，尽管对于更一般的有向图（Vernet & Markenzon 1997）哈密尔顿路径问题的NP硬度存在，但是可以以线性时间测试是否存在唯一排序以及是否存在哈密尔顿路径。

Answer 2

public class TopologicalSort 
{ 
    private int V; // No. of vertices 
    private List<int> [] adj; // Adjacency List 

    public ToplogicalSort(int v) 
    { 
     V = v; 
     adj = new List<int>[v]; 
     for (int i=0; i < v; ++i) 
      adj[i] = new List<int>(); 
    } 

    public void AddEdge(int v,int w) { adj[v].Add(w); } 

    public void TopologicalSortUtil(int v, bool[] visited, Stack<int> stack) 
    { 
     Stack<int> stackTracing = new Stack<int>(); 
     bool res = true; 
     List<int> list = new List<int>(adj[v]); 
     stackTracing.Push(v); 
     while (stackTracing.Count != 0 | res) 
     { 
      int n = stackTracing.Peek(); 
      list = new List<int>(adj[n]); 
      bool check = false; 
      foreach (var elem in list) 
      { 
       if (!visited[elem]) 
       { 
        visited[elem] = true; 
        n = elem; 
        stackTracing.Push(elem); 
        check = true; 
        break; 
       } 
      } 

      if(!check) 
      { 
       if(!stack.Contains(n)) 
       { 
        stack.Push(n); 
       } 
       if (stackTracing.Count != 0) 
        stackTracing.Pop(); 
       res = false; 
      }   
     } 
    } 

    public void TopologicalSort() 
    { 
     Stack<int> stack = new Stack<int>(); 
     bool[] visited = new bool[V]; 
     for (int i = 0; i < V; i++) 
      visited[i] = false; 

     for (int i = 0; i < V; i++) 
     { 
      if (visited[i] == false) 
      { 
       topologicalSortUtil(i, visited, stack); 
      } 
     } 
     // Print contents of stack 
     while (stack.Count != 0) 
     { 
      stack.Pop(); 
      Console.WriteLine(stack.Pop() + " "); 
     } 
    } 
    public static void RunSort() 
    { 
     TopologicalSort g = new TopologicalSort(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); 
     g.TopologicalSort(); 
    } 
}