用DFS遍历无向邻接表
时间: 2023-07-04 09:13:58 浏览: 52
使用DFS来遍历无向邻接表,可以按照以下步骤进行:
1. 从图中任意一个未被访问过的节点开始遍历;
2. 对于当前遍历到的节点,将其标记为已访问;
3. 遍历该节点的所有邻接节点,如果邻接节点未被访问过,则递归遍历该邻接节点;
4. 重复步骤2和3,直到该节点的所有邻接节点都被访问过。
具体实现可以使用递归或栈来实现。以下是一个使用递归的示例代码:
```python
# 定义一个无向邻接表
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
# 定义一个全局变量visited来记录是否访问过
visited = set()
# 定义DFS函数
def dfs(node):
# 标记节点已经访问
visited.add(node)
print(node, end=" ")
# 遍历邻接节点
for neighbor in graph[node]:
if neighbor not in visited:
# 递归遍历邻接节点
dfs(neighbor)
# 从任意一个节点开始遍历
dfs("A")
```
上述代码中,我们首先定义了一个无向邻接表graph,然后定义了一个全局变量visited,用于记录节点是否被访问过。接着定义了一个DFS函数,用于递归遍历节点的邻接节点。最后从任意一个节点开始遍历。