第十一章图论 Part1

haohaoscnblogs / 2024-09-04 / 原文

任务

797. 所有可能的路径

给你一个有 n 个节点的有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

思路

题目所给的图的表示是邻接表，题意就是找到从i到n的所有路径，这里使用dfs。参考之前的回溯章节，区别是当时的各种情况的出发根节点可以认为是虚拟节点，在循环和递归中处理各种情况，而现在的出发节点是实际的图的点，需要提前加入到path中来保证正确。

class Solution:
    def __init__(self):
        self.result = []
        self.path = []

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.path.append(0)
        self.dfs(graph,0,len(graph)-1)
        return self.result

    def dfs(self,graph,x,n): # 从x出发到n
        if x == n:
            self.result.append(self.path[:])
            return

        for i in graph[x]:
            self.path.append(i)
            self.dfs(graph,i,n)
            self.path.pop()

下面给出输入为邻接矩阵的算法

class Solution:
    def __init__(self):
        self.result = []
        self.path = []

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.path.append(0)
        self.dfs(graph,0,len(graph)-1)
        return self.result

    def dfs(self,graph,x,n): # 从x出发到n
        if x == n:
            self.result.append(self.path[:])
            return

        for i in graph[x][i]:
            if graph[x][i] == 1:
              self.path.append(i)
              self.dfs(graph,i,n)
              self.path.pop()

深度有限搜索（dfs)和广度优先搜索(bfs）简析

可以认为树中的先中后序遍历为dfs的特例，层序遍历为bfs的特例。

dfs适合的问题：

路径查找：在一些问题中，我们需要找到从起点到终点的一条路径（或所有路径）。DFS 很适合这种问题，因为它可以递归地探索每一条可能的路径，直到找到目标为止。
连通性问题：DFS 可以用于判断图是否连通，即图中是否存在一条从一个节点到另一个节点的路径。
拓扑排序：在处理有向无环图（DAG）时，DFS 可以用于生成拓扑排序
回溯算法：之前的回溯算法章节的问题都可以认为是dfs解决的问题

bfs适合的问题

最短路径问题：BFS 是在无权图中寻找两点之间最短路径的最优算法。因为 BFS 按层次遍历，所以首次到达目标节点时，一定是通过最短路径到达的。
层次遍历：BFS 按层次逐层遍历图或树结构，非常适合需要按照距离或层次关系处理的场景。
最小生成树（MST）：在一些图算法中，BFS 可以用来生成最小生成树（虽然更常用的是 Prim 或 Kruskal 算法）。

bfs的参考代码

from collections import deque

# 表示四个方向
dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def bfs(grid, visited, x, y):
    # 定义队列
    que = deque()
    # 起始节点加入队列
    que.append((x, y))
    # 只要加入队列，立刻标记为访问过的节点
    visited[x][y] = True

    while que:
        # 从队列取元素
        curx, cury = que.popleft() # 当前节点坐标

        # 开始向当前节点的四个方向左右上下去遍历
        for i in range(4):
            nextx = curx + dir[i][0]
            nexty = cury + dir[i][1]  # 获取周边四个方向的坐标

            # 坐标越界了，直接跳过
            if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                continue

            # 如果节点没被访问过
            if not visited[nextx][nexty]:
                # 队列添加该节点为下一轮要遍历的节点
                que.append((nextx, nexty))
                # 只要加入队列立刻标记，避免重复访问
                visited[nextx][nexty] = True