图论基础1
图的储存方式
邻接矩阵
用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
- 在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。
- 检查任意两个顶点间是否存在边的操作非常快
- 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。
邻接表
用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。
- 对于稀疏图的存储，只需要存储边，空间利用率高
- 遍历节点连接情况相对容易
- 检查任意两个节点间是否存在边，效率相对低，
图的遍历方式
在图（邻接表或邻接矩阵）上进行搜索的算法
深搜
dfs是朝一个方向去搜，一条路跑到黑，直到搜不下去了，再换方向（换方向的过程就涉及到回溯）。
故dfs常用递归实现
1.确认递归函数，参数
需要 ：二维数组数组结构保存所有路径，维数组保存单一路径，可以定义成全局变量
2.确认终止条件
不仅是结束本层递归，同时也是我们收获结果的
3.处理目前搜索节点出发的路径
一个for循环，去遍历 目前搜索节点 所能到的所有节点。
广搜
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向是一圈一圈的，四面八方的搜索过程。
正是因为BFS一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。
能保存遍历过元素的容器
- 用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
- 用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。
注意：只要加入队列就代表走过，需要标记，而不是从队列拿出来的时候再去标记走过。防止重复加入队列。