## 图
### 1、图的概念
* 由点的集合和边的集合构成
* 虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
* 边上可能带有权值
图的表示方法邻接表法、邻接矩阵法等。题目会以各种方式给出图的表达方式，可以将它转化为一种熟悉的表达方式，方便操作。可以将图表示为节点和边的集合，参考下面代码Graph。
```Java
public class Graph {
public Map nodes;
public Set edges;
public Graph() {
this.nodes = new HashMap<>();
this.edges = new HashSet<>();
}
}
public class Node {
// 节点值
public int value;
// 入度
public int in;
// 出度
public int out;
// 相邻节点
public List nexts;
// 节点的边
public List edges;
public Node(int value) {
this.value = value;
in = 0;
out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
public class Edge {
// 边的权重
public int weight;
// 边的起始节点
public Node from;
// 边的结束节点
public Node to;
public Edge(int weight, Node from, Node to) {
this.weight = weight;
this.from = from;
this.to = to;
}
}
```
### 宽度优先遍历
* 利用队列实现
* 从源节点开始依次按照宽度进队列，然后弹出
* 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
* 直到队列变空
### 深度优先遍历
* 利用栈实现
* 从源节点开始把节点按照深度放入栈，然后弹出
* 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
* 直到栈变空
### 拓扑排序
拓扑排序要求有向无环图，拓扑排序结果不唯一，可以用宽度优先遍历和深度优先遍历实现。应用场景有事件安排、编译顺序等
* 在图中找到所有入度为0的点输出
* 把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
* 图的所有点都被删除后，依次输出的顺序就是拓扑排序
### 最小生成树(无向图)
最小生成树要求无向图，可以使用Kruskal和Prim算法实现，Kruskal和Prim都是贪心算法。
#### Kruskal算法使用并查集
* 总是从权值最小的边开始考虑，依次考察权值依次变大的边
* 当前的边要么进入最小生成树的集合，要么丢弃
* 如果当前的边进入最小生成树的集合中不会形成环，就要当前边
* 如果当前的边进入最小生成树的集合中会形成环，就不要当前边
* 考察完所有边之后，最小生成树的集合也得到了
#### Prim算法
* 1）可以从任意节点出发来寻找最小生成树
* 2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边
* 3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环
* 4）如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）
* 5）如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）
* 6）当所有点都被选取，最小生成树就得到了
### 最短路径算法
可以使用Dijkstra算法实现最短路径。
#### 迪瑞克斯拉算法(有向、无负权重、可以有环)
1）Dijkstra算法必须指定一个源点
2）生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步
4）源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
#### Dijkstral算法优化
利用加强堆
某个节点最短距离改变时做动态调整