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