代码随想录算法训练营第五十天｜图论理论基础，深搜理论基础，98. 所有可达路径，广搜理论基础

图论理论基础：邻接矩阵、邻接表？？-写不出来 = 没入门

而且图论应用广泛，在大家做项目开发的时候，或多或少都会用到图论相关知识。例如：通信网络（拓扑排序、最短路算法），社交网络（深搜、广搜），路径优化（最短路算法），任务调度（拓扑排序），生物信息学（基因为节点，基因关系为边），游戏开发（A * 算法等）等等

图的种类（有向图、无向图、权重）

度：有多少条边连接这个节点，出度&入度（only make sense when有向图）

连通图（在无向图中，任何两个节点都是可以到达的，我们称之为连通图） & 非连通图

强连通图（在有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图）

连通分量

强连通分量

图的构造

朴素存储（n*2 array）

邻接矩阵（n*n矩阵，内存空间比较大）

邻接表（增量 在于 边 的数量）

图的遍历（之前在“二叉树”学过DFS & BFS-有印象学过，但现在应该不会写了😭）

DFS深搜

BFS广搜

深度优先搜索理论基础Depth First Search

recall: 回溯算法（本质也是dfs）

深搜三部曲：1.确定函数 & 参数，2.确定终止条件，3. for(选择本节点连接的节点) - 处理节点 - dfs（图，选择的节点） - 回溯，撤销处理结果

卡码网：98.可达路径

对AMC真的没招了😮‍💨

Broad First Search广度优先搜索

对于matrix的BFS理解：只能上下左右的方向进行搜索（不能斜着）（队列：先入先出/栈：先进后出/数组）

试着跟着写python pseudo-code:

#使用邻接矩阵存图,遍历过的节点不能再次遍历visited

定义全局变量（四个方向的遍历那个）dir = [[0, 1], [1, 0], [-1,0], [0,-1]]

def bfs(graph, visited, x, y):

#以下是把起点加入队列queue

queue #这是起点坐标

queue.append(x, y)

visited[x][y] = 1 #表示已经访问过

while len(queue) != 0:#队列不为空

#取出队列中的首元素

cur = queue[-1]?还是queue[0]

queue.pop()

for i in range(0, 4):

nextx = cur[0] + dir[i][0]

nexty = cur[1] + dir[i][1]

if nextx, nexty >=#越界了就不能处理：

continue

if visited[nextx][nexty] == 1#之前访问过也不能重复加入到队列里:

continue

queue.append([nextx, nexty])

visited[nextx][nexty] == 1