在一个无向图中找环
时间: 2024-01-22 17:17:31 浏览: 27
可以使用深度优先搜索(DFS)来查找是否存在环。具体地,我们对于每个节点,都进行一次 DFS,如果在 DFS 过程中发现了一个已经被访问过的节点,那么说明存在环。
具体实现时,可以用一个 visited 数组来记录每个节点是否被访问过,用一个 stack 来保存当前的 DFS 路径,如果在 DFS 过程中发现了已经被访问过的节点,那么就说明找到了环,可以输出 stack 中从该节点到栈顶的路径。
下面是 Python 代码的示例:
```python
def dfs(graph, visited, stack, node):
visited[node] = True
stack.append(node)
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(graph, visited, stack, neighbor):
return True
elif neighbor in stack:
# Found a cycle
cycle = []
while stack[-1] != neighbor:
cycle.append(stack.pop())
cycle.append(neighbor)
cycle.reverse()
cycle.append(cycle[0])
print('Cycle found:', '->'.join(cycle))
return True
stack.pop()
return False
def find_cycle(graph):
visited = [False] * len(graph)
stack = []
for node in range(len(graph)):
if not visited[node]:
dfs(graph, visited, stack, node)
```
其中,graph 是邻接表表示的无向图。如果存在环,会输出环的路径。如果不存在环,则程序不会有任何输出。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)