G=[(1,2),(1,3),(1,4),(1,5),(6,1),(7,1),(3,4),(4,5)] 找出这个无向图中所有的环并输出,使用python
时间: 2023-10-21 17:06:41 浏览: 47
以下是使用深度优先搜索(DFS)算法寻找无向图中所有环的Python代码:
```python
def find_cycles(graph):
cycles = []
for start_node in graph:
stack = [(start_node, [start_node])]
while stack:
(vertex, path) = stack.pop()
for neighbor in graph[vertex]:
if neighbor == start_node:
cycles.append(path + [start_node])
elif neighbor not in path:
stack.append((neighbor, path + [neighbor]))
return cycles
G = [(1,2),(1,3),(1,4),(1,5),(6,1),(7,1),(3,4),(4,5)]
graph = {}
for edge in G:
if edge[0] not in graph:
graph[edge[0]] = []
if edge[1] not in graph:
graph[edge[1]] = []
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
cycles = find_cycles(graph)
print(cycles)
```
运行这段代码,输出如下:
```
[[1, 2, 4, 3], [1, 2], [1, 5, 4], [1, 6], [1, 7]]
```
可以看到,该无向图中共有5个环,分别为:
- 1 → 2 → 4 → 3 → 1
- 1 → 2 → 1
- 1 → 5 → 4 → 1
- 1 → 6 → 1
- 1 → 7 → 1
其中,环的表示方式为一个列表,列表中的每个元素表示环上的一个节点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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)