题目描述

这是一个关于图论的基本问题，通常考察对图的遍历和搜索算法的理解。以下是题目的英文描述：

Given a directed graph, return true if and only if it contains a cycle.

中文描述：

给定一个有向图，如果它包含一个环，则返回 true，否则返回 false。

解决思路

解决这类问题通常有以下几种方法：

  • 深度优先搜索 (DFS): 使用递归或栈来遍历图的每个节点，如果在遍历过程中遇到了已经访问过的节点，则说明存在环。
  • 广度优先搜索 (BFS): 使用队列来遍历图的每个节点，同时记录每个节点的前驱节点，如果在遍历过程中遇到了已经访问过的节点，并且这个节点不是其前驱节点，则说明存在环。
  • Floyd 算法: 对于加权图，使用动态规划的方法检查图中是否存在环。

示例代码

以下是一个使用 DFS 解决此问题的 Python 示例代码：

def hasCycle(graph):
    visited = set()
    
    def dfs(node):
        if node in visited:
            return True
        visited.add(node)
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        return False
    
    for node in graph:
        if dfs(node):
            return True
    return False

扩展阅读

如果您对图论问题感兴趣，可以阅读更多相关内容。您可以访问本站提供的 [图论基础教程](/coding_practice/leetcode/graph_theory basics)。

图片展示

下面展示一个简单的图论示例：

simple_graph