建立一个图的邻接表,再实现图的深度优先遍历序列
时间: 2023-10-30 20:10:15 浏览: 38
建立图的邻接表可以使用一个字典来表示,其中字典的键为节点,值为该节点所连接的其他节点的列表。
例如,对于以下的无向图:
```
A — B — C
| | |
D — E — F
```
可以用以下的邻接表来表示:
```
{
"A": ["B", "D"],
"B": ["A", "C", "E"],
"C": ["B", "F"],
"D": ["A", "E"],
"E": ["B", "D", "F"],
"F": ["C", "E"]
}
```
下面是一个实现图的深度优先遍历序列的 Python 代码:
```python
def dfs(graph, start):
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
stack.extend(reversed(graph[node]))
return result
```
该函数接受两个参数:邻接表 `graph` 和起始节点 `start`。它使用一个集合 `visited` 来跟踪已经访问过的节点,使用一个栈 `stack` 来存储待访问的节点,使用一个列表 `result` 来存储遍历序列。
在每次迭代中,从栈中弹出一个节点 `node`。如果该节点没有被访问过,则将其添加到 `visited` 集合中,并将其添加到遍历序列 `result` 中。然后将该节点所连接的其他节点按相反的顺序压入栈中,以便下一次访问。这个过程一直持续到栈为空。
以下是使用上述代码对上面的图进行深度优先遍历的示例:
```python
graph = {
"A": ["B", "D"],
"B": ["A", "C", "E"],
"C": ["B", "F"],
"D": ["A", "E"],
"E": ["B", "D", "F"],
"F": ["C", "E"]
}
print(dfs(graph, "A")) # 输出: ['A', 'D', 'E', 'F', 'C', 'B']
```