图的遍历的实现数据结构代码
时间: 2024-07-04 21:00:31 浏览: 62
在计算机科学中,图的遍历通常涉及到深度优先搜索(Depth-First Search, DFS)和广度优先搜索(Breadth-First Search, BFS)。这些算法通常使用邻接表或邻接矩阵这两种数据结构来存储图。
**1. 邻接表实现**:
邻接表是一种稀疏矩阵的表示方法,对于每个节点,用一个链表或数组存储与其相连的所有邻居。以下是使用Python的邻接表实现DFS的一个简单示例:
```python
class Graph:
def __init__(self):
self.graph = {} # 使用字典存储邻接表
def add_edge(self, node1, node2):
if node1 not in self.graph:
self.graph[node1] = []
self.graph[node1].append(node2)
def dfs(self, start_node):
visited = set()
stack = [start_node]
while stack:
vertex = stack.pop()
if vertex not in visited:
print(vertex, end=" ")
visited.add(vertex)
for neighbor in self.graph[vertex]:
stack.append(neighbor)
# 使用示例
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.dfs('A') # 输出:A B D C
```
**2. 邻接矩阵实现**:
邻接矩阵是一个二维数组,其中行代表源节点,列表代表目标节点。如果两个节点之间有边,则对应的矩阵元素为1或True,否则为0或False。下面是使用Python实现BFS的例子:
```python
from collections import deque
class Graph:
def __init__(self, num_vertices):
self.graph = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)] # 初始化邻接矩阵
def bfs(self, start_node):
visited = [False] * len(self.graph) # 初始化visited数组
queue = deque([start_node])
visited[start_node] = True
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for i in range(len(self.graph[vertex])):
if not visited[i] and self.graph[vertex][i]: # 如果邻居未访问且有边
visited[i] = True
queue.append(i)
# 使用示例
g = Graph(5)
g.graph = [1, 2] # 表示节点0与1, 2相邻
g.graph = [0, 2, 3]
g.graph = [0, 1, 4]
g.graph =
g.graph =
g.bfs(0) # 输出:0 1 2 3 4
```