无向无权图 无向有权图 有向无权图 有向有权图
没有自环边，没有平行边， 称为简单图
一个图的所有节占不一定全部相连
一个图可能有多个联通分量
树是一种无环图。无环图不一定是树
联通的无环图就是树
不是！
没有
复杂度
可以优化空间复杂度 O(V2)
如果一个图有3000个节点
空间：5999vs3000^2约1000万
求相邻顶点．degree(v)vs3000
稠密图
平均每个度比较最大的度
空间复杂度，O(V+E)
如果是 树的话 O（2E+1）= O(E)
如果是完全图的话 O（v*(V-1)/2 + E）= O(E)
但是 不能写O(E) 如果不联通
建图：O(E*V) 和邻接矩阵 相差了v
看两点是否相邻 ：O(degree(v)) 原来是O(1)
求一个点的相邻节点 : O(degree(v)) 只需要遍历所有相邻节点个数
快速查重
快速查看两点是否相邻
不要使用链表
hash 表 HashSet O(1)
红黑树 TreeSet O(logv)
因为红黑树 考虑到元素之间的顺序性，为了保证TreeSet，为了使得结果相对可视化。
红黑树相对于hash表内存空间相对于少。
时间复杂度虽然会增加 o(1) < o(logn) < o(n) 比如 100w 1< 20 < 1000000
算法优化 使用红黑树而对于java使用TreeSet
我们可以看出来邻接表，在其他方面都是优于其他的表示方法。
所以我们接下来，都是使用邻接表。基于TreeSet。
图是一种数据结构 每种数据结构，都必须有“遍历"的方式
比如树的遍历:
很多算法本质就是遍历，其实看算法中是否有关。
其实80%的面试问题都可以解决了。
图其实就是比树要解决，重复遍历的问题。每次需要记录，那个节点被遍历。
图论不考虑非递归算法。
其实图论算法都是从树的遍历的引申，其实很像，其实底层实现很想。
其实对应n叉树，很像。
代码DFS
回归二叉树的遍历
类似的 我们可以推导后续遍历
复杂度 O（V+E）
关于优先遍历的应用：二分图
非递归的手法，深度优先遍历，其实很难，邻接矩阵的深度优先遍历
邻接表的深度优先遍历，其实一样。无非就是改变接口，但是注意时间复杂度: O(V^2)
因为这个过程，我们依然要遍历所有顶点的所有邻边。但是遍历一个顶点的所有邻边的时候，要遍历所有的顶点，复杂度是O(V)的，而非O(degree(v))的。
因此，整体，遍历所有顶点的所有邻边，需要的时间复杂度是O(V^2)的。
代码实现 : ADJDFS
使用图的接口 : Interface
大家可以看到，我们写的DFS算法类，其实封装的非常好，只需要简单的将类中传入的所有Graph类型（对应第二章中AdjSet的实现），修改为AdjMatrix，就可以完全正确地执行针对链接矩阵AdjMatrix的深度优先遍历了。
关于图的非递归的深度优先遍历
首先先复习一下，使用栈，树的非递归的实现, 如 Leetcode 144
// 深度优先遍历的非递归实现，需要使用一个栈
Stack<TreeNode> stack = new Stack<TreeNode>();
// 栈中首先压入根节点root
stack.push(root);
// 只要栈不为空，说明还有未被遍历的节点
while(!stack.empty()){
// 遍历栈顶元素
TreeNode curNode = stack.pop();
// 在这个例子中，遍历的方式是将该节点的值放入一个线性表res中
res.add(curNode.val);
// 之后，把当前节点的左右孩子压入栈中，等待后续的遍历
if(curNode.right != null)
stack.push(curNode.right);
if(curNode.left != null)
stack.push(curNode.left);
}
那么对于这种来其实一样。
实现代码：code
注意这里的结果和以前的不一样
递归 ： [0, 1, 3, 2, 6, 5, 4 ]
非递归 ： [0, 2, 1, 3, 5, 4, 6]
其实很简单。因为非递归的过程，我们是将一个顶点的相邻顶点压入栈中，取出的时候，是反向的；而递归没有这个问题，我们会按照adj(v)返回的列表的顺序，依次做深度优先遍历。+在这里，对此有疑问的同学，强烈建议实际对这两个程序进行一下单步跟踪，仔细理解一下，为什么会产生不一样的结果？通过但不跟踪，了解算法的每一步在做什么，每一步变量都发生了怎样的变化，怎样一点一点得到了最终的结果，这可是学习算法的重要方式哦。很多时候，顿悟，就发生在这个过程中：）
当然了，其实，这两个结果，都是图的深度优先遍历的结果。
代码：可以通过深度优先遍历，查看哪些是联通分量
两点在同一个联通分量， 意味着两点间有路径
路径怎么求
对应这种问题，我们向对来说，只能求从0到那个节点有路径，从某个点出发，到任意位置的路径，单源路径。
那么我们现在只是解决了单源问题，但是没解决多源问题，所以如何解决所有点路径的问题。
我们其实全部遍历点就好了，创建一个SingleSourcePath 数组
对于递归提前结束，没必要全部都遍历
在这一小节，我们实现了无向图的环检测代码。那么现在能不能实现一个简单的算法逻辑，来判断，给定的一张图，是否是一棵树?
必须保证图是联通的，同时没有环，才能说明这张图是一棵树。
在这一章，我们已经封装了求解图的连通分量的 CC 类，和环检测 CycleDetection 类,其实就可以判断一个图是不是树。
左右两边是一样的，其实无非就是染色。
同构图
NP 难 不能再多项式的问题是解决不了，但是无法证明是指数复杂度解决。
平面图
回顾树的优先遍历，其实就是一个队列，实现每次将这个节点的孩子节点放入队列中，最终当队列空了，就说明 树已经全部遍历过。对于一个节点，将所有的节点都遍历一边。
复杂度 O(V+E)
和深度优先遍历是一样的，如果是联通图的情况就是 O(E)
无非就是顺序不一样。
DFS : 0->6:[0, 1, 3, 2, 6]
BFS : 0->6:[0, 2, 6]
如果大家实际尝试一下，就会发现，这其实是非常简单的，我们要做的事情，近乎就是讲 dfs 函数替换成 bfs 函数而已。
注意，以下代码沿用我们在上一章第三小节的代码风格，visited数组是一个整型数组，-1 代表没有遍历，非负整数代表对应的连通分量的id。
// 使用 BFS 解决无向图的联通分量问题
public class CC {
private Graph G;
private int[] visited;
private int cccount = 0;
public CC(Graph G){
this.G = G;
visited = new int[G.V()];
for(int i = 0; i < visited.length; i ++)
visited[i] = -1;
for(int v = 0; v < G.V(); v ++)
if(visited[v] == -1){
// 只是这里调用 bfs 而已
bfs(v, cccount);
cccount ++;
}
}
代码如下：
可以回忆一下，在上一章，我们使用 DFS 解决了环检测问题。同理的，BFS 也可以解决环检测问题：）
和 DFS 的思路一样，大家可以回忆一下。使用 DFS 做环检测，只需要看到某一个顶点之前曾经遍历过，同时不是当前顶点的前一个顶点，就说明我们找到了一个环。
可以回忆一下，在上一章，我们使用 DFS 解决了二分图检测问题。同理的，BFS 也可以解决环检测问题：）
和 DFS 的思路一样，大家可以回忆一下。使用 DFS 做二分图检测，需要不断对没有遍历过的顶点进行染色，对遍历过的顶点，查看是否矛盾。如果产生矛盾，即某条边的两个端点颜色一样，则说明整张图不可能是二分图，否则，整张图就是二分图。
在这里，我首先强烈建议大家自己尝试基于 BFS，设计一个算法类，解决二分图检测问题。整个类的接口，应该和我们在学习 DFS 时设计的 BipartitionDetection 类是一样的，只不过，内部实现是使用 BFS 而不是 DFS：）
#BFS 性质
无权图最短路径
其实就是 BFS 求出路径就是 最短路径
不可能后遍历的节点 一定是基于后遍历的节点
无权图的最短路径
图的广度优先遍历BFS
无权图的最短路径
其实很相似，无非就是修改stack 和 queue
其实也可以用随机使用其他模型，比如随机队列。
算法笔试中图论问题的书写
四联通 ： 四个方向[[-1,0],[0,1],[1,0],[0,-1]]
x,y
for(d = 0;d <4;d++){
nextx = x + dist[d][0]
nexty = y + dist[d][1];
}
Floodfill 算法
其实就是从一个点就是遍历，到所有的匹配算法。
更多的应用：填色问题
魔棒其实就是：floodfill 算法
leetcode 200 岛屿的数量
leetcode 1020 飞地的数量
leetcode 130
leetcode 733 图像处理
leetcode 1034 边框着色
leetcode 529 扫雷
leetcode 827 最大人工岛
关于leetcode 659 号问题的研究。
我们可以更加优化，我们不需要visited 数组。
leetcode 1091
BFS , 八联通 1091
leetcode 752 Open the Lock
一道智力题
有两个水桶，一个装5升，一个装3升。 怎么利用这两个水桶，得到4升水？
状态压缩 10 *x + y
让我们一定能保证的话，可以能够保证两个联通分量，相互链接。
BFS 遍历树和DFS 遍历树
能不能使用BFS遍历？ 不能
DFS 遍历树
所以必须通过DFS去寻找桥
##哈密尔顿回路和路径
NP难，我们还没有多项式的算法无法解出。
暴力求解
回溯解法
O(n!) HamiltonLoop
##状态压缩
二维坐标用一个数字表示 两个桶的水量用一个两位数表示
因为是有符号的就是31位，一般不会超过31位，还不行就用63位，long类型
反之做减法
位运算
####基于状态压缩的哈密尔顿路径 HamiltonLoop
###记忆化搜说
####O(n!) vs O(n*2^n)
是把所有的排列组合，其实可能记忆化算搜说可能其实比较大。
哈密尔顿回路 从一个点出发，沿着边行走，经过每个顶点恰好一次，之后再回到出发点
一个点出发，沿着边行走，经过每个边恰好一次，之后再回到出发点
尽量使用最小的边，最终选择v-1条边 布线设计
切分定理
横切边中的最短边，属于最小生成树
- 贪心算法
O(ElogE)最大的时间其实就是排序边
O(ElogE) 最大的时间其实就是排序边
- 只有正权边
O(V^2)
O(ElogE)
- 松弛操作
- 负权环
所有点对的最短路径
- 任务调度
- 学习计划
- 互联网链接
- floodfill
- 最小生成树
- 桥和割点
- 二分图检测
- DFS
- BFS
- Dijsktra/Floyd/Bellman-Ford
判断是否在路径上
使用队列
拓扑排序另一种算法：DFS的后序遍历
不能进行环检测
强连通分量，在一个强连通分量中， 任何两点都可达
将所有强连通分量看做一个点 得到的有向图一定是DAG
增广路径：就是所有的残量大于0，到终点
最大匹配：就是找大最多的边
完全匹配：所有的点都在匹配中
完全匹配一定是最大匹配， 最大匹配不一定是完全匹配
有增广路径，意味这匹配数可以增加1
BFS 需要改进：来到右边的点，不需要寻路
DFS实现
O(V*E)
