python判断无向图是否有环

可以使用深度优先搜索（DFS）来判断无向图是否有环。具体步骤如下：

1. 从任意一个节点开始进行深度优先搜索。
2. 在搜索过程中，如果遇到了已经访问过的节点，且该节点不是搜索路径上的父节点，则说明存在环。
3. 如果搜索完成后没有发现环，则图是无环图。

下面是使用 Python 实现的代码：

def has_cycle(adj_list):
    visited = set()  # 用集合记录已经访问过的节点
    for node in adj_list:
        if node not in visited:  # 如果该节点没被访问过，就从该节点开始进行 DFS
            if dfs(node, visited, adj_list, parent=None):  # 如果 DFS 返回 True，说明存在环
                return True
    return False  # 如果所有节点都被访问过，且没有发现环，则说明是无环图


def dfs(node, visited, adj_list, parent):
    visited.add(node)  # 将当前节点标记为已访问
    for neighbor in adj_list[node]:
        if neighbor not in visited:  # 如果邻居节点没被访问过，则继续 DFS
            if dfs(neighbor, visited, adj_list, parent=node):  # 如果 DFS 返回 True，说明存在环
                return True
        elif neighbor != parent:  # 如果邻居节点已经被访问过，且不是当前节点的父节点，则说明存在环
            return True
    return False

其中，`adj_list` 是邻接表表示的无向图。每个节点的邻居节点存储在一个列表中。如果节点 i 有邻居 j，则 `adj_list[i]` 中会有一个元素 j。