实现带权图的邻接表存储+图的遍历算法

1. 深度优先搜索（DFS）：

步骤：

1. 从任意一个节点开始，标记为已访问。
2. 递归访问当前节点的未访问过的邻居节点，直到所有节点都被访问。

伪代码：

visited = [False] * n # 标记是否访问过
graph = [[] for _ in range(n)] # 图的邻接表表示

def dfs(node, weight):
visited[node] = True # 标记为已访问
for neighbor in graph[node]:
if not visited[neighbor[0]]:
dfs(neighbor[0], weight + neighbor[1]) # 递归访问邻居节点

# 遍历所有节点
for i in range(n):
if not visited[i]:
dfs(i, 0)

2. 广度优先搜索（BFS）：

步骤：

1. 创建一个队列，将起始节点放入队列中。
2. 当队列非空时，取出队首节点，标记为已访问，并访问它的所有邻居节点，将未访问过的邻居节点加入队列中。
3. 重复步骤2，直到队列为空。

伪代码：

visited = [False] * n # 标记是否访问过
graph = [[] for _ in range(n)] # 图的邻接表表示

def bfs(start):
queue = [(start, 0)] # 初始队列为起始节点
while queue:
node, weight = queue.pop(0) # 取出队首节点
visited[node] = True # 标记为已访问
for neighbor in graph[node]:
if not visited[neighbor[0]]:
queue.append((neighbor[0], weight + neighbor[1])) # 将未访问过的邻居节点加入队列中

# 遍历所有节点
for i in range(n):
if not visited[i]:
bfs(i)