图论理论基础
无向图:连通图;极大连通子图称之为该图的一个连通分量
有向图:强连通图;极大强连通子图称之为该图的强连通分量
如何用代码来表示一个图呢?
一般使用邻接表、邻接矩阵 或者用类来表示。
深搜理论基础
dfs 关键就两点:
- 搜索方向,是认准一个方向搜,直到碰壁之后再换方向
- 换方向是撤销原路径,改为节点链接的下一个路径,回溯的过程。
深搜三部曲如下:
- 确认递归函数,参数
- 确认终止条件
- 处理目前搜索节点出发的路径
98. 所有可达路径
1.使用邻接矩阵
2.使用邻接表
使用的数据结构:List<LinkedList<Integer>> graph = new ArrayList<>(m+1);
广搜理论基础
1.广搜的搜索方式就适合于解决两个点之间的最短路径问题。
2.广搜不是递归,我们仅仅需要一个容器,能保存我们要遍历过的元素就可以,那么用队列,还是用栈,甚至用数组,都是可以的。通常用队列。