拓扑排序： Python, C++ 算法示例

由： 陈莎拉 陈莎拉
Hours 更新

什么是拓扑排序算法？

拓扑排序又称为 Kahn 算法，是一种流行的排序算法。拓扑排序使用有向图作为输入，对节点进行排序，使每个节点都出现在其指向的节点之前。

该算法应用于 DAG（有向无环图），使得每个节点在所有其他节点指向它之前出现在有序数组中。该算法重复遵循一些规则，直到排序完成。

为了简化，请看以下示例：

有向图
有向图

这里我们可以看到“A”没有入度，它表示指向节点的边。“B”和“C”以“A”为先决条件，而“E”以“D”和“F”节点为先决条件。其中一些节点依赖于其他节点。

以下是上图的另一种表示形式：

各节点依赖关系

每个节点的依赖关系（线性排序）

因此，当我们将 DAG（有向无环图）传递给拓扑排序时，它将为我们提供一个具有线性排序的数组，其中第一个元素没有依赖性。

拓扑排序算法

此示例显示了一个带有循环的图表：

以下是执行此操作的步骤：

步骤1） 查找具有零个传入边的节点，即具有零度的节点。

步骤2） 将入度为零的节点存储在队列或堆栈中，并从图中删除该节点。

步骤3） 然后从该节点删除传出边。

这将减少下一个节点的入度数。

拓扑排序要求图数据结构不会有任何循环。

如果图满足以下要求，则将被视为 DAG：

  • 一个或多个入度值为零的节点。
  • 图不包含任何循环

只要 Graph 中有节点，并且 Graph 仍然是 DAG，我们就会运行上述三个步骤。否则，算法将陷入循环依赖，并且 Kahn 算法将无法找到入度为零的节点。

拓扑排序的工作原理

这里，我们将使用“Kahn 算法”进行拓扑排序。假设我们有以下图表：

拓扑排序的工作原理

以下是 Kahn 算法的步骤：

步骤1） 计算图中所有节点的入度或入边。

请注意：

  • 入度表示指向该节点的有向边。
  • 出度表示来自某个节点的有向边。

这是上图的入度和出度：

拓扑排序的工作原理

步骤2） 查找入度为零或入边为零的节点。

入度为零的节点表示没有边指向该节点。节点“A”的入度为零，表示没有边指向节点“A”。

因此，我们将采取下列行动：

  • 删除此节点及其出度边（传出边）
  • 将节点放入队列中以便排序。
  • 更新“A”邻居节点的入度数。

拓扑排序的工作原理

步骤3） 我们需要找到一个入度值为零的节点。在此示例中，“B”和“C”的入度为零。

这里，我们可以选择其中任意一个。我们选择“B”并将其从图中删除。

然后更新其他节点的入度值。

执行这些操作后，我们的图表和队列将如下所示：

拓扑排序的工作原理

步骤4） 节点“C”没有传入边。因此，我们将从图中删除节点“C”并将其推送到队列中。

我们还可以删除从“C”传出的边。

现在，我们的图表将如下所示：

拓扑排序的工作原理

步骤5） 我们可以看到节点“D”和“F”的入度为零。我们将取出一个节点并将其放入队列中。

我们先把“D”取出来。那么节点“E”的入度数就是1。现在，从D到E就没有节点了。

我们需要对节点“F”执行相同的操作，结果将如下所示：

拓扑排序的工作原理

步骤6） 节点“E”的入度（入边）和出度（出边）变为零。因此，我们已满足节点“E”的所有先决条件。

这里，我们将“E”放在队列的末尾。因此，我们没有剩余节点，所以算法到此结束。

拓扑排序的工作原理

拓扑排序的伪代码

这是使用 Kahn 算法进行拓扑排序的伪代码。

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  While node with O indegree present:
    topological_list.append(node)
    G.remove(node)
    Update Indegree of present nodes
  Return topological_list

拓扑排序也可以使用 DFS 来实现（深度优先搜索) 方法。但是，该方法是递归方法。Kahn 算法比 DFS 方法更有效。

相关文章

C++ 拓扑排序的实现

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

输出

0       1       2       3       5       4

Python 拓扑排序的实现

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list) 
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

输出

[0, 1, 2, 3, 5, 4]

拓扑排序算法的循环图

包含循环的图无法按拓扑顺序排列。因为循环图具有循环依赖关系。

例如，检查此图：

拓扑排序算法的循环图

此图不是 DAG（有向无环图），因为 A、B 和 C 形成一个循环。如果您注意的话，没有入度值为零的节点。

根据 Kahn 算法，如果我们分析上面的图表：

  • 查找入度为零（无传入边）的节点。
  • 从图中删除该节点并将其推送到队列。
    但是，在上面的图中，没有度为零的节点。每个节点的入度值都大于 0。
  • 返回一个空队列，因为它找不到任何度数为零的节点。

我们可以使用拓扑排序来检测循环，步骤如下：

步骤1） 执行拓扑排序。

步骤2） 计算拓扑排序列表中元素的总数。

步骤3） 如果元素的数量等于顶点的总数，则不存在循环。

步骤4） 如果它不等于顶点的数量，那么给定的图形数据结构中至少有一个循环。

拓扑排序的复杂性分析

算法的复杂性有两种。它们是

  1. 时间复杂度
  2. 空间复杂度

这些复杂性用提供一般复杂性的函数来表示。

时间复杂度： 对于拓扑排序，所有时间复杂度都是相同的。时间复杂度有最坏、平均和最佳情况。

拓扑排序的时间复杂度为O(E + V)，其中E表示图中的边数，V表示图中的顶点数。

让我们突破这种复杂性：

步骤1） 首先，我们将计算所有入度。为此，我们需要遍历所有边，并且首先将所有 V 顶点的入度设置为零。因此，我们完成的增量步骤将是 欧拉(V+E).

步骤2） 我们将找到入度值为零的节点。我们需要从顶点的 V 号开始搜索。因此，完成的步骤将是 （V）.

步骤3） 对于每个入度为零的节点，我们将删除该节点并减少入度。对所有节点执行此操作将需要 欧氏距离.

步骤4） 最后，我们将检查是否存在循环。我们将检查排序数组中的元素总数是否等于节点总数。这将需要 O（1）.

因此，这些是拓扑排序或拓扑排序的每个步骤的单独时间复杂度。我们可以说，从上述计算得出的时间复杂度将为 O(V + E)；这里，O 表示复杂度函数。

空间复杂度： 我们需要 O(V) 空间来运行拓扑排序算法。

以下是我们需要为程序提供空间的步骤：

  • 我们必须计算图中所有节点的入度。由于图共有 V 个节点，因此我们需要创建一个大小为 V 的数组。因此，所需的空间为 （V）.
  • 使用队列数据结构来存储入度为零的节点。我们从原始图中删除了入度为零的节点，并将其放入队列中。为此，所需空间为 （V）.
  • 该数组名为“order”。它按拓扑顺序存储节点。这也要求 （V） 空格。

这些是单独的空间复杂度。因此，我们需要在运行时最大化这些空间。

空间复杂度为O(V)，其中V表示图中顶点的数量。

拓扑排序的应用

拓扑排序有非常广泛的用途。以下是其中一些：

  • 它用于 Opera听系统 需要进行资源分配。
  • 在图中查找一个循环。我们可以使用拓扑排序来验证图是否是 DAG。
  • 自动完成应用程序中的句子排序。
  • 它用于检测 僵局.
  • 不同类型的调度或课程调度使用拓扑排序。
  • 解析依赖项。例如，如果您尝试安装一个包，该包可能还需要其他包。拓扑排序会找出安装当前包所需的所有包。
  • Linux 使用“apt”中的拓扑排序来检查软件包的依赖关系。

你可能会喜欢：