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] +  1queue.append(neigh)

• 最短路徑，求解start到其余節點的距離,區別在于刪除了那個if node == end的判斷

from collections import deque
# 這個friend是鄰接表
def bfs(start):# 初始化隊列，將起始節點加入隊列queue = deque([start])# 記錄每個節點是否被訪問過以及從起始節點到該節點的最短距離# 初始時，起始節點的距離為 0visited = {start: 0}while queue:# 從隊列中取出一個節點node = queue.popleft()# 遍歷該節點的所有鄰居節點for neigh in friends[node]:if neigh not in visited:# 如果鄰居節點未被訪問過，更新其距離為當前節點距離加 1visited[neigh] = visited[node] + 1# 將鄰居節點加入隊列，以便后續繼續遍歷其鄰居queue.append(neigh)return visited

3243.新增道路查詢后的最短距離

3243.新增道路查詢后的最短距離

思路分析：

from collections import dequeclass 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,enddef 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] +  1queue.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