图论总结-拓扑排序以及最短路径问题（无权最短路径、Dijkstra算法、具有负边值的图）
图的定义
一个图（graph）G = (V,E) 由 顶点(vertex) 集 V 和 边(edge) 集 E 组成。
每一条边就是一个点对（v,w），其中 v,w∈ V，有时也被称为弧(arc)。
如果点对是有序的，那么图就叫做是有向的（directed），有向的图有时也叫做有向图（digraph）。
顶点 v 和 w 邻接（adjacent） 当且仅当（v,w）∈ E。
有时边还有第三种成分，称作 权（weight） 或 值（cost）。
对于一个顶点 v，边（u,v）的条数称为入度（indegree）。
图中的一条路径（path） 是一个顶点序列 w1,w2,w3,…wN，使得（wi,wi+1）∈ E，1<= i < N。
这样的一条路径的长（length） 是该条路径上的边数，它等于 N - 1。
一条简单路径是这样的一条路径：其上的所有顶点都是互异的但第一个顶点和最后一个顶点可能相同。
有向图中的圈（cycle） 是满足 w1 = wN 且长度至少为 1 的一条路径，如果该条路径是简单路径，那么这个圈就是简单圈。
如果一个有向图没有圈，则称其为无圈的（acyclic）。一个有向无圈图有时也简称为 DAG。
如果一个无向图中从每一个顶点到每一个其他顶点都存在一条路径，则称该无向图是连通的（connected）。
具有这样性质的有向图称为是强连通（strongly connected） 的。
如果边上去掉方向所形成的图是连通的，那么称为基础图（underlying graph）。
如果一个有向图不是连通的，但是它是基础图，那么该有向图称为弱连通（weakly connected） 的。
完全图（complete graph） 是其每一对顶点间都存在一条边的图。
稠密图（dense） ：图中 E 的条数接近 V*V 也就是，接近任意两点之间相连。
稀疏图（sparse） ：图中 E 的条数远小于 V*V。
图的表示
关于图的具体 Java 实现可以点此查看，或点击下面的链接：
https://github.com/0xZhangKe/Algorithms/tree/master/src/com/zhangke/java/graph/adt
我这里是使用邻接表的方式实现的。
邻接矩阵
表示图的一种简单方法是使用一个二维数组，称为邻接矩阵（adjacency matrix）表示法。
适合稠密的图。
邻接表
如果图是稀疏的，则更好的表示方式是使用邻接表（adjacency list）表示。
拓扑排序
拓扑排序是对有向无圈图的顶点的一种排序，他使得如果存在一条从 vi 到 vj 的路径，那么在排序中 vj 出现在 vi 后面。
一个简单的求拓扑排序的算法是先找出任意一个没有入度的顶点。然后我们显示出该顶点，并将它和它的边一起从图中删除。然后，我们对图的其余部分应用同样的方法处理。
public static <T> void sort(ListDGraph<T> graph) {
Queue<Vertex<T>> queue = new ArrayDeque<>();
Queue<Vertex<T>> resultQueue = new ArrayDeque<>();
int size = graph.size();
int[] indegree = new int[size];//入度数组
for (int i = 0; i < size; i++) {
List<Edge<Vertex<T>>> edges = graph.get(i).getEdgeList();
for (Edge<Vertex<T>> item : edges) {
indegree[graph.get(item.getDest())]++;
}
}
for (int i = 0; i < size; i++) {
if (indegree[i] == 0) {
queue.offer(graph.get(i));
}
}
while (!queue.isEmpty()) {
Vertex<T> vertex = queue.poll();
resultQueue.offer(vertex);
List<Edge<Vertex<T>>> edges = vertex.getEdgeList();
if (edges != null) {
for (Edge<Vertex<T>> edge : edges) {
int index = graph.get(edge.getDest());
indegree[index]--;
if (indegree[index] <= 0) {
queue.offer(edge.getDest());
}
}
}
}
while (!resultQueue.isEmpty()) {
Vertex<T> item = resultQueue.poll();
System.out.print(item.getValue());
if (!resultQueue.isEmpty()) {
System.out.print(" -> ");
}
}
}
最短路径算法
输入一个赋权图：与每条边（vi, vj）相联系的是穿越该弧的代价（或称为值）ci, j。一条路径 v1 v2 … vN 的值是 ∑i=1 N-1 ，i+ 1 叫做赋权路经长（weight path length）。而无权路径长（unweight path length）只是路径上的边数，及 N - 1。
为了解决最短路径问题，这里引入一个配置表的概念：
对于每个顶点，我们跟踪三个信息。
Know：表示该顶点是否是已知的；
dv：从起点 s 到该点的距离；
pv：簿记变量，它使我们能够显示出实际的路径。
那么再来定义一个用于创建配置表的方法：
/**
* 用于寻找最短路径的辅助配置表
*
* Created by ZhangKe on 2019/3/31.
*/
public class TableEntity<T> {
static final int INFINITY = Integer.MAX_VALUE;
boolean know = false;
int dist = INFINITY;
T path = null;
static <T> Map<Vertex<T>, TableEntity<Vertex<T>>> getTable(DGraph<T> graph, Vertex<T> vertex){
Map<Vertex<T>, TableEntity<Vertex<T>>> table = new HashMap<>();
for (int i = 0; i < graph.size(); i++) {
Vertex<T> v = graph.get(i);
TableEntity<Vertex<T>> entity = new TableEntity<>();
if (v.equals(vertex)) {
entity.dist = 0;
}
table.put(v, entity);
}
return table;
}
static <T> void printTable(Map<Vertex<T>, TableEntity<Vertex<T>>> table){
String divider = " ";
System.out.print(String.format("v%sKnown%sDv%sPv", divider, divider, divider));
System.out.println();
for (Vertex<T> key : table.keySet()) {
TableEntity<Vertex<T>> itemTable = table.get(key);
System.out.print(key.getValue() +
divider +
itemTable.know +
divider +
itemTable.dist +
divider +
(itemTable.path == null ? "null" : itemTable.path.getValue()));
System.out.println();
}
}
}
需要注意的是，这里的 DGraph 以及其他图相关的实现类可以点击这里查看，或者点击下面的链接，此处不做详细说明：
https://github.com/0xZhangKe/Algorithms/tree/master/src/com/zhangke/java/graph/adt
无权最短路径
使用某个顶点 s 作为输入参数，我们想找出从 s 到所有其他顶点的最短路径，我们只对包含在路径中的边数感兴趣，因此在边上不存在权。
显然，这是赋权最短路径问题的特殊情形，因为我们可以为所有的边都赋以权 1。
具体的代码实现如下：
public <T> void find(DGraph<T> graph, Vertex<T> s) {
//创建初始配置表
Map<Vertex<T>, TableEntity<Vertex<T>>> table = TableEntity.getTable(graph, s);
Queue<Vertex<T>> queue = new ArrayDeque<>();
queue.offer(s);
while (!queue.isEmpty()) {
Vertex<T> v = queue.poll();
TableEntity<Vertex<T>> itemTable = table.get(v);
itemTable.know = true;
if (v.getEdgeList() != null) {
for (Edge<Vertex<T>> edge : v.getEdgeList()) {
if (edge.getDest() != null) {
TableEntity<Vertex<T>> destTable = table.get(edge.getDest());
if (destTable.dist == TableEntity.INFINITY) {
destTable.dist = itemTable.dist + 1;
destTable.path = v;
queue.offer(edge.getDest());
}
}
}
}
}
TableEntity.printTable(table);
}
上面这种搜索方式成为广度优先搜索（breadth-first search）。该方法按层处理顶点：距开始点最近的那些顶点首先被赋值，而最远的那些顶点最后被赋值。这很像对树的层序遍历（level-order traversal）。
Dijkstra 算法
解决单源最短路径问题的一般方法叫做 Dijkstra 算法（Dijkstra`s algorithm）。这个有 30 年历史的解法是贪婪算法（greedy algorithm） 最好的例子。
Dijkstra 算法像无权最短路径算法一样，按阶段进行，在每个阶段， Dijkstra 算法选择一个顶端 v，它在所有未知顶点中具有最小的 dv，同时算法声明从 s 到 v 的最短路径是已知的。
/**
* 1.获取未标志过的顶点列表中值最小的顶点（因为默认都是 MAX_VALUE ，所以只可能邻接节点，本质上是寻找邻接节点中的最小值）
* 2.遍历该顶点的邻接点，如果邻接点未标记，且值小于当前路径权重值，则用当前路径权重值更新
* 3.重复步骤1/2
*/
private static <T> void find(DGraph<T> graph, Vertex<T> vertex) {
Map<Vertex<T>, TableEntity<Vertex<T>>> table = TableEntity.getTable(graph, vertex);
for (int i = 1; i < graph.size(); i++) {
Vertex<T> minVertex = findUnknownMin(table);
if (minVertex == null) {
break;
}
TableEntity<Vertex<T>> minTable = table.get(minVertex);
int minDist = minTable.dist;
minTable.know = true;
if (minVertex.getEdgeList() != null) {
for (Edge<Vertex<T>> edge : minVertex.getEdgeList()) {
if (edge.getDest() != null) {
TableEntity<Vertex<T>> edgeTable = table.get(edge.getDest());
if (!edgeTable.know &&
(minDist + edge.getWeight() < edgeTable.dist)) {
edgeTable.dist = minDist + edge.getWeight();
edgeTable.path = minVertex;
}
}
}
}
}
TableEntity.printTable(table);
}
/**
* 从未知表中读取一个 dist 最小的顶点
*/
private static <T> Vertex<T> findUnknownMin(Map<Vertex<T>, TableEntity<Vertex<T>>> table) {
int min = TableEntity.INFINITY;
Vertex<T> vertex = null;
for (Vertex<T> key : table.keySet()) {
TableEntity<Vertex<T>> item = table.get(key);
if (!item.know && min >= item.dist) {
min = item.dist;
vertex = key;
}
}
return vertex;
}
具有负边值的图
把赋权和无权的算法结合起来将会解决这个问题。
private static <T> void find(DGraph<T> graph, Vertex<T> vertex) {
Map<Vertex<T>, TableEntity<Vertex<T>>> table = TableEntity.getTable(graph, vertex);
Queue<Vertex<T>> queue = new ArrayDeque<>();
queue.offer(vertex);
while (!queue.isEmpty()) {
Vertex<T> itemVertex = queue.poll();
TableEntity<Vertex<T>> itemTable = table.get(itemVertex);
itemTable.know = true;
if (itemVertex.getEdgeList() != null) {
for (Edge<Vertex<T>> edge : itemVertex.getEdgeList()) {
if (edge.getDest() != null) {
TableEntity<Vertex<T>> destTable = table.get(edge.getDest());
if (itemTable.dist + edge.getWeight() < destTable.dist) {
destTable.dist = itemTable.dist + edge.getWeight();
destTable.path = itemVertex;
if (!queue.contains(edge.getDest())) {
queue.offer(edge.getDest());
}
}
}
}
}
}
TableEntity.printTable(table);
}
注意：上述内容是对【数据结构与算法——C语言描述】.mark Allen Weiss 一书第九章：图论算法的学习总结。
更多其他算法及数据结构相关的知识可去我的 Github 仓库查看：
https://github.com/0xZhangKe/Algorithms
如果觉得还不错的话，欢迎关注我的个人公众号，我会不定期发一些干货文章~