python判断无向图是否有环

判断无向图是否有环可以使用DFS（深度优先搜索）或BFS（广度优先搜索）算法。以下是使用DFS的Python代码示例：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def is_cyclic_util(self, v, visited, parent):

        visited[v] = True

        for i in self.graph[v]:
            if not visited[i]:
                if self.is_cyclic_util(i, visited, v):
                    return True
            elif parent != i:
                return True

        return False

    def is_cyclic(self):

        visited = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                if self.is_cyclic_util(i, visited, -1):
                    return True

        return False

g = Graph(5)
g.add_edge(1, 0)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(0, 3)
g.add_edge(3, 4)

if g.is_cyclic():
    print("Graph contains cycle")
else:
    print("Graph does not contain cycle")

在上面的代码中，我们定义了一个Graph类来表示无向图。`add_edge`方法用于将边添加到图中。`is_cyclic_util`方法用于递归地检查每个节点是否有环，如果存在环则返回True，否则返回False。`is_cyclic`方法遍历图中的每个节点，并调用`is_cyclic_util`方法来检查每个节点是否有环。如果存在环，则返回True，否则返回False。