首页以邻接表为存储结构进行深度优先遍历和广度优先遍历的代码

以邻接表为存储结构进行深度优先遍历和广度优先遍历的代码

时间: 2025-06-09 19:02:39 浏览: 6

在图论中，邻接表是一种常用的数据结构，用于表示稀疏图，其中每个顶点对应一个链表，链表中包含与其相连的所有顶点。以下是使用邻接表分别实现深度优先搜索(DFS)和广度优先搜索(BFS)的基本算法： ```python # 定义图的邻接列表表示 class Graph: def __init__(self): self.graph = {} # 添加边到图 def add_edge(self, u, v): if u not in self.graph: self.graph[u] = [] self.graph[u].append(v) # 深度优先搜索 (DFS) def dfs(graph, start_node): visited = set() stack = [start_node] while stack: vertex = stack.pop() if vertex not in visited: print(vertex, end=" ") visited.add(vertex) stack.extend(set(graph[vertex]) - visited) # 广度优先搜索 (BFS) from collections import deque def bfs(graph, start_node): visited = set() queue = deque([start_node]) while queue: vertex = queue.popleft() if vertex not in visited: print(vertex, end=" ") visited.add(vertex) queue.extend(graph[vertex] - visited) # 使用示例 graph = Graph() graph.add_edge('A', 'B') graph.add_edge('A', 'D') graph.add_edge('B', 'C') graph.add_edge('C', 'D') graph.add_edge('D', 'E') dfs(graph, 'A') # 输出: A B D E C bfs(graph, 'A') # 输出: A B C D E ``` 在这个例子中，我们首先创建了一个`Graph`类，它有一个邻接表`graph`作为内部数据结构。然后定义了`dfs`和`bfs`函数，分别采用栈和队列来进行深度优先和广度优先遍历。这两个函数会按照相应的策略访问并打印出图中的节点。

阅读全文