BFS
:广度优先搜索(BFS) 是一种常用的算法,通常用于解决图或树的遍历问题,尤其是寻找最短路径或层级遍历的场景。BFS 的核心思想是使用队列(FIFO 数据结构)来逐层遍历节点。
from collections import deque
def bfs(start):
queue = deque([start])
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]
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
def bfs(start):
queue = deque([start])
visited = {start: 0}
while queue:
node = queue.popleft()
for neigh in friends[node]:
if neigh not in visited:
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)
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]:
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