用python 写一个 判断 无向图里有没有环的示例

我可以给你一个用python写的判断无向图里有没有环的示例：# 定义无向图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}# 定义深度优先搜索函数
def dfs(graph, node, visited):
if node not in visited:
visited.append(node)
for n in graph[node]:
dfs(graph,n, visited)
return visited# 检查是否存在环
def has_cycle(graph):
visited = []
# 从每个节点开始搜索
for node in graph:
visited = dfs(graph, node, visited)
# 如果搜索的节点数与图中节点数相同，说明存在环
if len(visited) == len(graph):
return True
visited = []
return False# 调用函数
if has_cycle(graph):
print('Graph has a cycle.')
else:
print('Graph does not have a cycle.')

相关问题

python 存储数据到有向无环图寻找路径_python判断无向图环是否存在的示例

对于存储数据到有向无环图寻找路径，可以使用 Python 中的 networkx 库，具体实现可以参考以下代码：

import networkx as nx

# 创建一个有向无环图
G = nx.DiGraph()

# 添加节点
G.add_node(1)
G.add_node(2)
G.add_node(3)

# 添加边
G.add_edge(1, 2)
G.add_edge(2, 3)

# 查找路径
path = nx.shortest_path(G, source=1, target=3)
print(path)  # 输出 [1, 2, 3]

对于判断无向图环是否存在，可以使用深度优先搜索算法来实现，具体实现可以参考以下代码：

def has_cycle(G, v, visited, parent):
    visited[v] = True  # 标记当前节点为已访问
    for neighbor in G[v]:
        if not visited[neighbor]:
            if has_cycle(G, neighbor, visited, v):
                return True
        elif parent != neighbor:
            return True
    return False

# 创建一个无向图
G = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3, 5],
    5: [4]
}

# 判断是否存在环
visited = {v: False for v in G}
has_cycle = False
for v in G:
    if not visited[v]:
        if has_cycle(G, v, visited, -1):
            has_cycle = True
            break

print(has_cycle)  # 输出 True

需要注意的是，以上代码只适用于无向图，对于有向图需要使用拓扑排序等算法进行判断。

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。