图的dfs遍历和bfs遍历python

使用 Python 实现图的 DFS 和 BFS 遍历
深度优先搜索 (DFS)
深度优先搜索是一种用于遍历或搜索树或图的算法。该算法会尽可能深入地探索每一个分支，直到无法继续为止。
from collections import defaultdict

class Graph:
def __init__(self):
self.graph = defaultdict(list)

def add_edge(self, u, v):
"""添加边"""
self.graph[u].append(v)

def dfs_util(self, v, visited):
"""辅助函数执行实际的DFS操作"""
visited.add(v)
print(v, end=' ')

for neighbour in self.graph[v]:
if neighbour not in visited:
g.dfs_util(neighbour, visited)

def dfs(self, start_vertex):
"""启动DFS遍历"""
visited = set()
g.dfs_util(start_vertex, visited)
登录后复制
此代码定义了一个 Graph 类来表示无向图，并实现了深度优先搜索的功能[^1]。
广度优先搜索 (BFS)
广度优先搜索也是一种用于遍历或搜索树或图的算法。它按照层次顺序访问节点，即先访问离起始点最近的所有顶点再逐步向外扩展。
from collections import deque, defaultdict

class Graph:
def __init__(self):
self.graph = defaultdict(list)

def add_edge(self, u, v):
"""添加边"""
self.graph[u].append(v)

def bfs(self, start_vertex):
"""启动BFS遍历"""
visited = [False] * (max(self.graph) + 1)
queue = []

queue.append(start_vertex)
visited[start_vertex] = True

while queue:
vertex = queue.pop(0)
print(vertex, end=" ")

for i in self.graph[vertex]:
if not visited[i]:
queue.append(i)
visited[i] = True
登录后复制
这段程序同样创建了一个名为 Graph 的类并提供了添加新边的方法以及执行广度优先搜索的能力[^2]。
通过上述两个例子可以清楚看到两种不同类型的图遍历方式的具体实现过程，在具体应用时可以根据需求选择合适的方式来进行数据处理和分析工作。