python输出无向图中所有环路
时间: 2023-05-25 13:02:53 浏览: 121
以下是输出无向图中所有环路的Python程序:
首先,我们需要定义一个函数,该函数将采用邻接列表表示的无向图作为输入,并返回所有环的列表。我们将使用深度优先搜索(DFS)技术。
def find_all_cycles(graph):
cycles = []
for node in graph:
dfs(graph, [node], cycles)
return cycles
在深度优先搜索函数中,我们将尝试从给定节点开始查找环。我们将维护一个路径,以避免重复访问节点。如果我们到达了一个已经在路径中的节点,那么我们已经找到了一个环。请注意,在无向图中,我们可以从下一个节点(而不是从上一个节点)继续搜索。
def dfs(graph, path, cycles):
node = path[-1]
for neighbour in graph[node]:
if len(path) > 2 and neighbour == path[0]:
cycles.append(path + [neighbour])
return
if neighbour not in path:
dfs(graph, path + [neighbour], cycles)
现在,我们可以使用该函数来找到无向图中所有的环。
例如,让我们考虑一个简单的图:
graph = {
1: [2, 3],
2: [1, 3, 4],
3: [1, 2, 4],
4: [2, 3]
}
我们可以使用以下方式调用函数:
print(find_all_cycles(graph))
输出将是:
[[1, 2, 3], [2, 3, 4]]