【代码随想录|第十一章 图论part01 | 797.所有可能的路径 】
代码随想录|第十一章 图论part01 | 图论理论基础，797.所有可能的路径，广搜理论基础
- 一、图论理论基础
- 1.图的基本概念
- 2.图的构造
- 1）邻接矩阵
- 2）邻接表
- 3.图的遍历方式
- 4.深度优先搜索理论基础
- 二、797.所有可能的路径
- 1.核心代码
- 2.问题
- 三、广搜理论基础
- 总结
python
一、图论理论基础
1.图的基本概念
度：几个连接的边。出度、入度
连通图+有向图=强连通图
连通分量：必须是极大联通子图才行
强连通分量: 有向图+连通分量
2.图的构造
如何用代码表示？邻接表、邻接矩阵、类
朴素存储、邻接表、邻接矩阵
1）邻接矩阵
grid[2][5]=6表示节点2 连接向 节点5 ，权值为6
2）邻接表
数组（节点）+链表（相连节点）
3.图的遍历方式
两类：深度优先搜索dfs/广度优先搜索bfs
4.深度优先搜索理论基础
先一直往一个方向走到死角
有递归就有回溯
dfs三部曲：1、参数 2、终止条件 3、处理目前的搜索节点出发的路径
二、797.所有可能的路径
797.所有可能的路径
1.核心代码
代码如下（示例）：
class Solution:def allPathsSourceTarget(self, graph) :ans =list()stk = list()def dfs(x):if x ==len(graph)-1:ans.append(stk[:])returnfor y in graph[x]:stk.append(y)dfs(y)stk.pop()stk.append(0)dfs(0)return ansif __name__=="__main__":raw_input=input()graph=eval(raw_input)solution=Solution()result=solution.allPathsSourceTarget(graph)# 若输出格式无空格result2=str(result).replace(" ","")print(result2)
2.问题
记住，可以将字符串自动解析成列表+链表形式的代码
graph=eval(input())
** 能够处理输入如：[[1,2],[3],[3],[]] **
输入输出部分主要是增加了一个这个输入的函数的学习
然后核心代码部分：
有二维的数组用list()链表来创建
其他看起来还比较简单，就是我还没有自己打一下
三、广搜理论基础
适合解决两个点之间的最短路径问题
用队列，保证每一圈都是一个方向去转
总结
输入输出