写一个栈实现的图的深度优先搜索算法
时间: 2024-06-11 13:09:28 浏览: 9
算法步骤:
1. 定义一个栈来保存待访问的顶点。
2. 将起始顶点压入栈中,并标记为已访问。
3. 取出栈顶的顶点,访问它的邻接顶点。如果邻接顶点未被访问,则将其压入栈中,并标记为已访问。
4. 重复步骤 3,直到栈为空。
代码实现:
```python
def dfs(graph, start):
visited = set() # 已访问的顶点集合
stack = [start] # 栈
while stack:
vertex = stack.pop() # 取出栈顶顶点
if vertex not in visited: # 如果该顶点未被访问
visited.add(vertex) # 标记为已访问
print(vertex)
# 将该顶点的邻接顶点压入栈中
for neighbor in graph[vertex]:
if neighbor not in visited:
stack.append(neighbor)
```
其中,`graph` 是以字典形式表示的图,`start` 是起始顶点。字典的键表示顶点,值表示与该顶点相邻的顶点列表。例如:
```python
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)