图论基础
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指向的节点，就是节点iif 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] = 1res = []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 defaultdictresult = [] # 收集符合条件的路径
path = [] # 1节点到终点的路径def dfs(graph, x, n):if x == n: # 找到符合条件的一条路径result.append(path.copy())returnfor 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()
广度优先搜索理论基础
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
1、广度搜索的过程
BFS是一圈一圈的搜索过程，但具体是怎么一圈一圈来搜；
假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步，如下图所示：
