图论之 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.新增道路查询后的最短距离

在这里插入图片描述

思路分析：

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