对任意给定的图(顶点数和边数自定),建立它的邻接表并输出,然后利用堆栈的五种基本运算(清空堆栈、压栈、弹出、取栈顶元素、判栈空)实现图的深度优先搜索遍历。
时间: 2023-11-25 07:08:23 浏览: 200
好的,那么我们先来实现建立图的邻接表的部分。我们可以使用一个字典来表示邻接表,字典的键表示顶点,对应的值为该顶点的邻接表。
```python
# 建立图的邻接表
def build_adjacency_list(edges):
adjacency_list = {}
for u, v in edges:
if u not in adjacency_list:
adjacency_list[u] = []
if v not in adjacency_list:
adjacency_list[v] = []
adjacency_list[u].append(v)
adjacency_list[v].append(u)
return adjacency_list
# 示例
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("C", "E"), ("D", "E")]
adjacency_list = build_adjacency_list(edges)
print(adjacency_list)
```
输出结果为:
```
{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D', 'E'], 'D': ['B', 'C', 'E'], 'E': ['C', 'D']}
```
接下来,我们可以使用堆栈(栈)来实现深度优先搜索遍历。具体来说,我们遍历图时,以任意一个未被访问的顶点为起点,将其压入堆栈中。然后重复以下步骤,直到堆栈为空为止:
1. 从堆栈顶部弹出一个顶点,作为当前顶点。
2. 访问当前顶点并标记为已访问。
3. 遍历当前顶点的所有邻接顶点,如果邻接顶点未被访问,则将其压入堆栈。
下面是利用堆栈实现深度优先搜索遍历的代码:
```python
# 利用堆栈实现深度优先搜索遍历
def dfs(adjacency_list, start):
stack = [start] # 堆栈
visited = set() # 记录已访问的顶点
while stack:
vertex = stack.pop() # 弹出堆栈顶部的顶点
if vertex not in visited:
print(vertex, end=" ") # 访问该顶点
visited.add(vertex) # 标记为已访问
neighbors = adjacency_list[vertex]
for neighbor in neighbors:
if neighbor not in visited:
stack.append(neighbor) # 将邻接顶点压入堆栈中
print()
# 示例
dfs(adjacency_list, "A")
```
输出结果为:
```
A B D E C
```
这就是利用堆栈实现图的深度优先搜索遍历的实现方法。
阅读全文