图论之BFS

文章目录 3243.新增道路查询后的最短距离1311.获取你好友已观看的视频

BFS:广度优先搜索（BFS） 是一种常用的算法，通常用于解决图或树的遍历问题，尤其是寻找最短路径或层级遍历的场景。BFS 的核心思想是使用队列（FIFO 数据结构）来逐层遍历节点。

模版 from collections import deque # graph def bfs(start): # 初始化队列，并将起始节点加入队列 queue = deque([start]) # 初始化 visited 集合，记录已访问的节点 visited = set([start]) while queue: # 从队列中取出当前节点 node = queue.popleft() # 处理当前节点（例如打印、判断条件等） # 遍历当前节点的邻居 for neighbor in graph[node]: if neighbor not in visited: # 将未访问的邻居加入队列，并标记为已访问 queue.append(neighbor) visited.add(neighbor)

BFS求解最短距离：必要的条件是每条边的权值都是1

最短距离的求解：分为求解start到end,以及start到剩余节点的问题 def bfs(start,end): queue = deque([start]) # 可以记录是否访问过，还可以记录距离 visited = {start:0} while queue: node = queue.popleft() if node == end: return visited[node] # friends是邻接表 for neigh in friends[node]: if neigh not in visited: # 距离的更新 visited[neigh] = visited[node] + 1 queue.append(neigh) 最短路径，求解start到其余节点的距离,区别在于删除了那个if node == end的判断 from collections import deque # 这个friend是邻接表 def bfs(start): # 初始化队列，将起始节点加入队列 queue = deque([start]) # 记录每个节点是否被访问过以及从起始节点到该节点的最短距离 # 初始时，起始节点的距离为 0 visited = {start: 0} while queue: # 从队列中取出一个节点 node = queue.popleft() # 遍历该节点的所有邻居节点 for neigh in friends[node]: if neigh not in visited: # 如果邻居节点未被访问过，更新其距离为当前节点距离加 1 visited[neigh] = visited[node] + 1 # 将邻居节点加入队列，以便后续继续遍历其邻居 queue.append(neigh) return visited 3243.新增道路查询后的最短距离

3243.新增道路查询后的最短距离

思路分析：

from collections import deque class Solution: def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]: # 初始化邻接表 edge = [[] for _ in range(n)] for i in range(n - 1): edge[i].append(i + 1) # 添加单向边 # BFS 函数，计算从 start 到 end 的最短距离 def bfs(start, end): queue = deque([start]) visited = {start: 0} # 记录每个节点的距离，也能记录是否被访问过 while queue: node = queue.popleft() if node == end: return visited[node] # 返回最短距离 for neigh in edge[node]: # 遍历当前节点的邻居 if neigh not in visited: # 注意的是这个距离的更新方式 visited[neigh] = visited[node] + 1 # 更新距离 queue.append(neigh) # 处理查询 ans = [] for p, q in queries: edge[p].append(q) # 添加新边 ans.append(bfs(0, n - 1)) # 计算最短距离 return ans 1311.获取你好友已观看的视频

311.获取你好友已观看的视频

思路分析：

我的力扣题解

from collections import deque,defaultdict,Counter class Solution: def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]: # 首先我们只需记录你的朋友的级别！也就是最短距离，在最短距离的模版基础上修改即可 # 后面再遍历即可 # 难处在于什么都没有构建，不过这个friends就是相当于邻接表了 # 我们只需计算start,end def bfs(start,end): queue = deque([start]) visited = {start:0} while queue: node = queue.popleft() if node == end: return visited[node] for neigh in friends[node]: if neigh not in visited: visited[neigh] = visited[node] + 1 queue.append(neigh) n = len(watchedVideos) video = [] ans = [] for i in range(n): if bfs(id,i) == level: video.extend(watchedVideos[i]) # 去重吧 ans = list(set(i for i in video)) count = Counter(video) ans_sorted = sorted(ans, key=lambda x: (count[x], x)) return ans_sorted