如何判断有向环图：DFS、拓扑排序与Kahn算法详解

创作时间:

作者:

@小白创作中心

如何判断有向环图：DFS、拓扑排序与Kahn算法详解

引用

来源

https://docs.pingcode.com/baike/1129249

有向环图（Directed Graph with Cycle）是图论中的一个重要概念，在计算机科学和工程领域有着广泛的应用。判断一个有向图是否存在环是图算法中的基本问题之一，常见的解决方法包括深度优先搜索（DFS）、拓扑排序和Kahn算法。本文将详细介绍这三种方法的原理、实现步骤，并提供Python代码示例。

深度优先搜索（DFS）

算法原理

深度优先搜索（DFS）是一种用于遍历或搜索图或树的数据结构的算法。其基本思想是沿着一个分支尽可能深入，然后回溯。DFS算法可以检测有向图中的环，因为在递归过程中，如果某个节点已经在当前路径中出现过，则说明存在一个环。

实现步骤

初始化数据结构：创建一个标记数组来记录节点是否被访问，以及一个辅助栈来记录当前路径。
递归遍历：从每个未访问的节点出发，进行递归遍历。如果在递归过程中，发现某个节点已经在当前路径中，则说明存在一个环。
回溯：如果当前节点的所有邻居节点都已经访问过，则将其从当前路径中移除。

Python代码示例

def has_cycle(graph):
    def dfs(node, visited, stack):
        visited[node] = True
        stack[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if dfs(neighbor, visited, stack):
                    return True
            elif stack[neighbor]:
                return True
        stack[node] = False
        return False

    visited = [False] * len(graph)
    stack = [False] * len(graph)
    for node in range(len(graph)):
        if not visited[node]:
            if dfs(node, visited, stack):
                return True
    return False

# 示例图
graph = [
    [1],
    [2],
    [0, 3],
    [4],
    []
]
print(has_cycle(graph))  # 输出: True

拓扑排序

算法原理

拓扑排序是一种线性排序算法，适用于有向无环图（DAG）。如果一个有向图存在环，则无法进行拓扑排序。因此，通过尝试进行拓扑排序，我们可以判断一个有向图是否包含环。

实现步骤

计算入度：计算每个节点的入度。
初始化队列：将所有入度为0的节点加入队列。
广度优先搜索（BFS）：从队列中取出一个节点，访问其所有邻居节点，并将其从图中移除。如果某个邻居节点的入度变为0，则将其加入队列。
检查结果：如果所有节点都被访问过，则图中不存在环；否则，存在环。

Python代码示例

from collections import deque

def has_cycle(graph):
    in_degree = [0] * len(graph)
    # 计算入度
    for node in range(len(graph)):
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    queue = deque([node for node in range(len(graph)) if in_degree[node] == 0])
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return count != len(graph)

# 示例图
graph = [
    [1],
    [2],
    [0, 3],
    [4],
    []
]
print(has_cycle(graph))  # 输出: True

Kahn算法

算法原理

Kahn算法是一种用于拓扑排序的算法，与上述的拓扑排序方法类似。其基本思想是不断从图中移除入度为0的节点，并更新其邻居节点的入度。如果在移除所有节点之后，仍有节点未被访问，则图中存在环。

实现步骤

计算入度：计算每个节点的入度。
初始化队列：将所有入度为0的节点加入队列。
移除节点：从队列中取出一个节点，访问其所有邻居节点，并将其从图中移除。如果某个邻居节点的入度变为0，则将其加入队列。
检查结果：如果所有节点都被移除，则图中不存在环；否则，存在环。

Python代码示例

from collections import deque

def has_cycle(graph):
    in_degree = [0] * len(graph)
    # 计算入度
    for node in range(len(graph)):
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    queue = deque([node for node in range(len(graph)) if in_degree[node] == 0])
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return count != len(graph)

# 示例图
graph = [
    [1],
    [2],
    [0, 3],
    [4],
    []
]
print(has_cycle(graph))  # 输出: True