当前位置：首页 > article >正文

代码随想录算法训练营第五十天|图论基础|深度优先搜索理论基础|KM98.所有可达路径|广度优先搜索理论基础

article 2025/1/7 6:45:11

图论基础

1、图的基本概念

二维坐标中，两点可以连成线，多个点连成的线就构成了图。

当然图也可以就一个节点，甚至没有节点（空图）

2、图的种类

整体上一般分为有向图和无向图；

有向图是指图中边是有方向的；

无向图是指图中边没有方向；

加权有向图，就是图中边是有权值的；

3、度

无向图中有几条边连接该节点，该节点就有几度。

在有向图中，每个节点有出度和入度。

出度：从该节点出发的边的个数。

入度：指向该节点边的个数。

4、强连通图

强连通图是在有向图中任何两个节点是可以相互到达；

5、连通分量

无向图中节点构成的子图就是该无向图中的一个连通分量，该子图所有节点都是相互可达到的，且必须是极大联通子图才能是连通分量；

6、图的构造

如何用代表来表示一个图呢？一般使用邻接表、邻接矩阵或者用类来表示，主要是朴素存储、邻接表和邻接矩阵。

①邻接矩阵

邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申

请多大的二维数组。

例如： grid[2][5] = 6，表示节点 2 连接节点5 为有向图，节点2 指向节点5，边的权值为6。

如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与节点5 相互连通，权值为6。

优点：

1、表达方式简单，易于理解

2、检查任意两个顶点间是否存在边的操作非常快

3、适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：遇到稀疏图，会导致申请过大的二维数组造成空间浪费且遍历边的时候需要遍历整个n * n矩阵，造成时间浪费

②邻接表

邻接表使用数组 + 链表的方式来表示。邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。

优点：

1、对于稀疏图的存储，只需要存储边，空间利用率高

2、遍历节点连接情况相对容易

缺点：

1、检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。

2、实现相对复杂，不易理解

7、图的遍历方式

1、深度优先搜索（dfs）:二叉树的递归遍历，是dfs 在二叉树上的遍历方式。

2、广度优先搜索（bfs）:二叉树的层序遍历，是bfs 在二叉树上的遍历方式。

深度优先搜索理论基础

1、dfs和bfs的区别

①dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。

②bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

2、深度搜索三部曲

1、确认递归函数，参数

2、确认终止条件

3、处理目前搜索节点出发的路径

98. 所有可达路径

1、确认递归函数，参数

我们dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x；还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候标明找到了终点。

2、确认终止条件

当目前遍历的节点为最后一个节点 n 的时候就找到了一条从出发点到终止点的路径；

3、处理目前搜索节点出发的路径

接下来是走当前遍历节点x的下一个节点。首先是要找到 x节点指向了哪些节点呢？接下来就是将选中的x所指向的节点，加入到单一路径来。最后进入下一层递归；

# 邻接矩阵写法
def dfs(graph, x, n, path, res):
    # 当前遍历的接地点x，到达节点n;
    if x == n:
        res.append(path.copy())
        return
    # 遍历节点x连接的所有节点
    for i in range(1, n+1):
        # 找到x指向的节点，就是节点i
        if graph[x][i] == 1:
            # 遍历到的节点加入到路径中来
            path.append(i)
            # 进入下一层递归
            dfs(graph, i, n, path, res)
            # 回溯，撤销本节点
            path.pop()

def main():
    n, m = map(int, input().split())
    graph = [[0]*(n+1) for _ in range(n+1)]

    for _ in range(m):
        s, t = map(int, input().split())
        graph[s][t] = 1

    res = []
    dfs(graph, 1, n, [1], res)
    if not res:
        print(-1)
    else:
        for path in res:
            print(' '.join(map(str, path)))

if __name__ == '__main__':
    main()

# 邻接表写法
from collections import defaultdict

result = []  # 收集符合条件的路径
path = []  # 1节点到终点的路径

def dfs(graph, x, n):
    if x == n:  # 找到符合条件的一条路径
        result.append(path.copy())
        return
    for i in graph[x]:  # 找到 x指向的节点
        path.append(i)  # 遍历到的节点加入到路径中来
        dfs(graph, i, n)  # 进入下一层递归
        path.pop()  # 回溯，撤销本节点

def main():
    n, m = map(int, input().split())

    graph = defaultdict(list)  # 邻接表
    for _ in range(m):
        s, t = map(int, input().split())
        graph[s].append(t)

    path.append(1)  # 无论什么路径已经是从1节点出发
    dfs(graph, 1, n)  # 开始遍历

    # 输出结果
    if not result:
        print(-1)
    for pa in result:
        print(' '.join(map(str, pa)))

if __name__ == "__main__":
    main()