🍉 🖐🏿 📐 拓扑排序 🤦 🏭 🏴

在“开发人员算法”课程开始之前，准备了本文的翻译。

有向无环图（有向无环图，以下简称DAG）的拓扑排序是顶点的线性排序，其具有以下条件：对于每个有向边uv，顶点u在该排序中位于顶点v之前。如果该图不是DAG，则无法对其进行拓扑排序。

例如，下图的拓扑排序是“ 5 4 2 3 1 0”。图形可以有几种拓扑排序。例如，针对同一图形的另一种拓扑排序是“ 4 5 2 3 1 0”。拓扑排序中的第一个顶点始终是没有传入边的顶点。

拓扑排序VS深散步：

当要深（深度优先遍历，以下简称DFS）我们输出顶点，然后递归调用相邻顶点的DFS。在拓扑排序中，我们需要在顶点附近显示顶点。例如，在此图中，顶点“ 5”应显示在顶点“ 0”之前，并且与DFS不同，顶点“ 4”也应显示在顶点“ 0”之前。这将拓扑排序与DFS区别开来。例如，上图的DFS为“ 5 2 3 1 0 4”，但这不是拓扑排序。

建议：在继续执行算法之前，首先尝试在实践中了解问题。

拓扑排序搜索算法。

首先，我们建议您熟悉此 DFS实施。我们可以修改DFS，以便获得图的拓扑排序。在DFS中我们从一个合适的顶点开始，我们首先输出它，然后递归调用其相邻顶点的DFS。在拓扑排序中，我们使用临时堆栈。顶点不会立即显示-首先，对所有相邻顶点进行拓扑排序，然后将顶点推入堆栈。仅在遍历所有顶点之后，才会显示堆栈的内容。请注意，仅当所有相邻顶点（及其相邻顶点等）都已经在堆栈上时，才将顶点推入堆栈。

下图说明了上述方法：

:
(G)
0 →
1→
2 → 3
3 → 1
4 → 0, 1
5 → 2, 0

1:
(0), visited[0] = true
. .
0
2:
(1), visited[1] = true
. .
0 1
3:
(2),, visited[2] = true
(3),, visited[3] = true
1 .
0 1 3 2
4:
(4),, visited[4] = true
顶点0和1已被访问。不再进行递归调用
堆栈0 1 3 2 4
步骤5：已访问的
拓扑排序（5）[5] =正确
顶点2和0已被访问。不再进行递归调用
堆栈0 1 3 2 4 5
步骤6：将
所有堆栈项从上到下拉出

以下是拓扑排序实现。请检查DFT实现中是否存在断开连接的图形，并注意此处给出的第二个代码与以下代码之间的区别。

C ++

//   C++     DAG
 
#include<iostream>
#include <list>
#include <stack>
using namespace std;
  
//    
class Graph
{
    int V;	//  
  
    //    ,   
    list<int> *adj;
  
    // ,  topologicalSort
    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
    Graph(int V);   // 
  
     //      
    void addEdge(int v, int w);
  
    //    
    void topologicalSort();
};
  
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
  
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
  
//  ,  topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[], 
                                stack<int> &Stack)
{
    //     
    visited[v] = true;
  
    //       
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            topologicalSortUtil(*i, visited, Stack);
  
    //       
    Stack.push(v);
}
  
//     . 
//   topologicalSortUtil()
void Graph::topologicalSort()
{
    stack<int> Stack;
  
    //     
    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);
  
    //   
    while (Stack.empty() == false)
    {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}
  
//    
int main()
{
    //  ,    
    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 << "Following is a Topological Sort of the given graph \n";
    g.topologicalSort();
  
    return 0;
}

爪哇

//   Java    
import java.io.*;
import java.util.*;
  
//          
class Graph
{
    private int V;   //  
    private LinkedList<Integer> adj[]; //  
  
    // 
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }
  
    //      
    void addEdge(int v,int w) { adj[v].add(w); }
  
    //  ,  topologicalSort
    void topologicalSortUtil(int v, boolean visited[],
                             Stack stack)
    {
        //      
        visited[v] = true;
        Integer i;
  
        //       
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }
  
        //       
        stack.push(new Integer(v));
    }
  
    //     .
    //   topologicalSortUtil()
    void topologicalSort()
    {
        Stack stack = new Stack();
  
        //     
        boolean visited[] = new boolean[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);
  
        //   
        while (stack.empty()==false)
            System.out.print(stack.pop() + " ");
    }
  
    //   
    public static void main(String args[])
    {
        //  ,    
        Graph g = new Graph(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("Following is a Topological " +
                           "sort of the given graph");
        g.topologicalSort();
    }
}
//      (Aakash Hasija)

蟒蛇

#  Python       DAG   import defaultdict
  
#   
class Graph:
    def __init__(self,vertices):
        self.graph = defaultdict(list) #dictionary containing adjacency List
        self.V = vertices #No. of vertices
  
    #      
    def addEdge(self,u,v):
        self.graph[u].append(v)
  
    #  ,  topologicalSort
    def topologicalSortUtil(self,v,visited,stack):
  
        #     
        visited[v] = True
  
        #       
        for i in self.graph[v]:
            if visited[i] == False:
                self.topologicalSortUtil(i,visited,stack)
  
        #       
        stack.insert(0,v)
  
    #     . 
    #   topologicalSortUtil()
    def topologicalSort(self):
        #     
        visited = [False]*self.V
        stack =[]
  
        #    
        #       
        for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(i,visited,stack)
  
        #   
        print stack
  
g= Graph(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);
  
print "Following is a Topological Sort of the given graph"
g.topologicalSort()
#     (Neelam Yadav)

<b>:</b>
Following is a Topological Sort of the given graph
5 4 2 3 1 0

时间上的困难：上面的算法是带有附加堆栈的DFS。因此，时间复杂度与DFS相同，为O（V + E）。

注意：您也可以使用向量而不是堆栈。如果使用向量进行拓扑排序，则需要以相反的顺序输出元素。

应用：

拓扑排序主要用于根据它们之间的给定依赖性来调度工作。在计算机科学中，它用于计划命令，重新计算电子表格中的公式值时组织用于计算公式的单元格，逻辑综合，确定将在makefile中执行的编译任务的顺序，数据序列化以及解析链接器中的符号依存关系[ 2 ]。

Kahn拓扑排序算法：另一种O（V + E）算法。
有向无环图的所有拓扑排序

参考文献

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm
http://en.wikipedia.org/wiki/Topological_sorting

如果发现错误或要共享，请发表评论有关正在讨论的主题的其他信息。

了解有关该课程的更多信息。

拓扑排序

C ++

爪哇

蟒蛇

相关文章

参考文献

More articles: