设计一个python代码,遍历联通无向图G中的每一条边,每条边仅遍历一次
时间: 2024-04-29 09:24:49 浏览: 212
C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
5星 · 资源好评率100%
可以使用DFS或BFS进行遍历,具体代码如下:
```python
visited = set() # 存放已经访问过的节点
def traverse(G):
for node in G:
if node not in visited:
dfs(G, node)
def dfs(G, node):
visited.add(node)
for neighbor in G[node]:
if neighbor not in visited:
print(f"遍历到节点 {node} 和 {neighbor} 之间的边")
dfs(G, neighbor)
```
在这段代码中,我们先定义了一个集合 `visited`,用于存放已经访问过的节点。然后定义了 `traverse`函数来遍历整张图,以及一个 `dfs` 函数来实现DFS遍历。在 `dfs` 函数中,我们首先将当前节点加入已访问集合 `visited` 中,然后遍历其所有邻居节点,如果邻居节点没有被访问过,则遍历这条边并递归访问该邻居节点。通过这种方式,我们可以遍历整张图中的每条边,且每条边仅会被遍历一次。
阅读全文