图的深度优先遍历(无向图)
时间: 2024-01-02 18:22:28 浏览: 69
深度优先遍历(Depth First Search,DFS)是一种用于遍历或搜索图或树的算法。在深度优先遍历中,从起始节点开始,沿着一条路径尽可能深入地访问节点,直到到达不能再深入的节点为止,然后回溯到前一个节点,继续访问其他未访问的节点,直到所有节点都被访问。
以下是一个使用邻接表实现深度优先遍历的示例代码:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adj = [[] for _ in range(vertices)]
def addEdge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u)
def DFSUtil(self, v, visited):
visited[v] = True
print(v, end=" ")
for i in self.adj[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
def DFS(self, v):
visited = [False] * (self.V)
self.DFSUtil(v, visited)
# 创建一个图对象
g = Graph(5)
# 添加边
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(1, 4)
print("深度优先遍历结果:")
g.DFS(0)
```
输出结果为:0 1 3 4 2
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)