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

建立图的邻接矩阵或邻接表存储结构，并实现图的深度优先搜索（DFS）或广度优先搜索（BFS）算法，是图论中的基本操作。以下是详细的介绍和实现步骤：
1. 邻接矩阵和邻接表的定义
邻接矩阵
邻接矩阵是一个二维数组，用于表示图中顶点之间的连接关系。对于一个有 n 个顶点的图，邻接矩阵是一个 n x n 的矩阵。如果顶点 i 和顶点 j 之间有边，则矩阵中对应位置为 1，否则为 0。
邻接表
邻接表是一个链表数组，每个顶点对应一个链表，链表中存储与该顶点相连的所有顶点。对于一个有 n 个顶点的图，邻接表包含 n 个链表。
2. 图的表示
使用邻接矩阵表示图
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)
登录后复制
使用邻接表表示图
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
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
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
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
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. 完整示例
以下是一个完整的示例，展示如何使用邻接表和邻接矩阵实现图的深度优先搜索和广度优先搜索：
# 邻接矩阵实现
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)
登录后复制