编写图的深度优先遍历程序
时间: 2023-12-05 10:39:42 浏览: 50
以下是Python中实现图的深度优先遍历的示例代码:
```python
# 定义图类
class Graph:
def __init__(self, graph_dict=None):
if graph_dict is None:
graph_dict = {}
self.__graph_dict = graph_dict
# 添加顶点
def add_vertex(self, vertex):
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] = []
# 添加边
def add_edge(self, edge):
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
# 深度优先遍历
def dfs(self, start_vertex):
visited = set()
self.__dfs(start_vertex, visited)
def __dfs(self, vertex, visited):
visited.add(vertex)
print(vertex, end=' ')
for neighbor in self.__graph_dict[vertex]:
if neighbor not in visited:
self.__dfs(neighbor, visited)
```
在这个示例中,我们首先定义了一个Graph类,它包含了添加顶点和边的方法,以及深度优先遍历的方法。在深度优先遍历方法中,我们使用了递归的方式来遍历整个图。我们首先将起始顶点标记为已访问,然后输出该顶点,并递归地访问它的所有邻居顶点。如果邻居顶点没有被访问过,我们就将它标记为已访问,并递归地访问它的邻居顶点。
相关推荐
![](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)