无向图找环算法,给出实现代码
时间: 2024-05-13 14:16:38 浏览: 70
spfa.zip_SPFA 无向图
下面给出一个基于深度优先搜索(DFS)的无向图找环算法的实现代码:
```python
def find_cycle(graph):
visited = set()
for node in graph:
if node not in visited:
cycle = dfs(graph, node, visited, None)
if cycle is not None:
return cycle
return None
def dfs(graph, node, visited, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited:
return [neighbor, node]
cycle = dfs(graph, neighbor, visited, node)
if cycle is not None:
if node in cycle:
return cycle
else:
return cycle + [node]
return None
```
其中,`graph` 是一个字典,表示无向图的邻接表。例如,对于以下无向图:
```
A---B
| |
C---D
```
可以表示为:
```python
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
```
`find_cycle` 函数首先遍历图中所有的节点,对于每个未访问过的节点,调用 `dfs` 函数进行深度优先搜索。`dfs` 函数维护了一个 `visited` 集合表示已经访问过的节点,以及一个 `parent` 指针表示当前节点在搜索树中的父节点。对于当前节点的每个邻居,如果邻居已经被访问过且不是当前节点的父节点,那么就找到了一个环,返回环上的两个节点。如果邻居未被访问过,那么继续递归搜索。如果递归返回了一个环,那么如果当前节点在环上,就返回整个环,否则返回环加上当前节点。如果没有找到环,返回 `None`。
阅读全文