建立图的邻接矩阵或邻接表存储结构并以邻接矩阵或邻接表为存储结构实现图的深度优先或广度优先遍历算法。

建立图的邻接矩阵或邻接表存储结构，并实现图的深度优先搜索（DFS）或广度优先搜索（BFS）算法，是图论中的基本操作。以下是详细的介绍和实现步骤： ### 1. 邻接矩阵和邻接表的定义 #### 邻接矩阵 邻接矩阵是一个二维数组，用于表示图中顶点之间的连接关系。对于一个有 `n` 个顶点的图，邻接矩阵是一个 `n x n` 的矩阵。如果顶点 `i` 和顶点 `j` 之间有边，则矩阵中对应位置为 `1`，否则为 `0`。 #### 邻接表 邻接表是一个链表数组，每个顶点对应一个链表，链表中存储与该顶点相连的所有顶点。对于一个有 `n` 个顶点的图，邻接表包含 `n` 个链表。 ### 2. 图的表示 #### 使用邻接矩阵表示图 ```python class Graph: def __init__(self, vertices): self.V = vertices self.adj_matrix = [[0] * vertices for _ in range(vertices)] def add_edge(self, u, v): self.adj_matrix[u][v] = 1 self.adj_matrix[v][u] = 1 def display(self): for row in self.adj_matrix: print(row) ``` #### 使用邻接表表示图 ```python class Graph: def __init__(self, vertices): self.V = vertices self.adj_list = [[] for _ in range(vertices)] def add_edge(self, u, v): self.adj_list[u].append(v) self.adj_list[v].append(u) def display(self): for i in range(self.V): print(f"{i}: {' -> '.join(map(str, self.adj_list[i]))}") ``` ### 3. 深度优先搜索（DFS）算法 #### 使用邻接矩阵实现 DFS ```python def dfs_util(self, u, visited): visited[u] = True print(u, end=' ') for v in range(self.V): if self.adj_matrix[u][v] == 1 and not visited[v]: self.dfs_util(v, visited) def dfs(self, start): visited = [False] * self.V self.dfs_util(start, visited) ``` #### 使用邻接表实现 DFS ```python def dfs_util(self, u, visited): visited[u] = True print(u, end=' ') for v in self.adj_list[u]: if not visited[v]: self.dfs_util(v, visited) def dfs(self, start): visited = [False] * self.V self.dfs_util(start, visited) ``` ### 4. 广度优先搜索（BFS）算法 #### 使用邻接矩阵实现 BFS ```python def bfs(self, start): visited = [False] * self.V queue = [] queue.append(start) visited[start] = True while queue: u = queue.pop(0) print(u, end=' ') for v in range(self.V): if self.adj_matrix[u][v] == 1 and not visited[v]: queue.append(v) visited[v] = True ``` #### 使用邻接表实现 BFS ```python def bfs(self, start): visited = [False] * self.V queue = [] queue.append(start) visited[start] = True while queue: u = queue.pop(0) print(u, end=' ') for v in self.adj_list[u]: if not visited[v]: queue.append(v) visited[v] = True ``` ### 5. 完整示例 以下是一个完整的示例，展示如何使用邻接表和邻接矩阵实现图的深度优先搜索和广度优先搜索： ```python # 邻接矩阵实现 graph_matrix = Graph(5) graph_matrix.add_edge(0, 1) graph_matrix.add_edge(0, 2) graph_matrix.add_edge(1, 2) graph_matrix.add_edge(1, 3) graph_matrix.add_edge(2, 3) graph_matrix.add_edge(3, 4) print("邻接矩阵:") graph_matrix.display() print("DFS (邻接矩阵):") graph_matrix.dfs(0) print("\nBFS (邻接矩阵):") graph_matrix.bfs(0) # 邻接表实现 graph_list = Graph(5) graph_list.add_edge(0, 1) graph_list.add_edge(0, 2) graph_list.add_edge(1, 2) graph_list.add_edge(1, 3) graph_list.add_edge(2, 3) graph_list.add_edge(3, 4) print("\n邻接表:") graph_list.display() print("DFS (邻接表):") graph_list.dfs(0) print("\nBFS (邻接表):") graph_list.bfs(0) ```