图算法

发表于 更新于 分类于

图的介绍

怎么说呢，通过前两篇的编写，我发现学数据结构真的是从一个有序，再到另外一个有序，最后到一个杂乱的东西。那么回想一下，我们在写代码的时候，刚开始，代码是井然有序的，然后慢慢的随着功能的新增，产品经理的无理，我们的项目就会慢慢的变成一碗意大利面（用白话说就是 屎💩）当然，目前知道了图的概念以后，我发现，一碗 屎💩 还有点用处，就是可以研究我们接下来要说的数据结构：图。 大概我们把之前说到的树，连多几条边，就可以感受到 图 了，不过，查找树 也是 图，链表 数组 均为图，只不过因为他们的性质让我们利用起来做一些应用的时候会更加的方便，而且 高效 性价比高：

连上边，我们之前的 节点，变成了另外一个概念 顶点，而连接线则由另外一个名称：边。不过人类该死的视觉总是会产生差错，会误以为下面这幅 图 和上面这幅 图 表示的是不同的 图：

但其实，这两幅图是 一样的。为啥，因为 顶点 一样，顶点之间 的连接情况也一样，所以这两幅图是相等的（WPS 真好用，拖动节点的时候，会自动的把 边 给带上hhhhh）。

图的应用

那是因为无聊才提出这个概念吗，不是，我们研究地图，美团外卖小哥送外卖，滴滴打车的时候都需要用到 图 这个概念来计算最短的线路，或者编译我们写的 屎山 的时候，编译器需要用他来规划我们的模块之间、类之间的联系，甚至是 Java 的 JVM虚拟机，也需要用到 图 来 标记-清除 系统产生的垃圾。 而且前面学的 数组 呀 二叉树 呀都可以使用 图 这个结构来做，但是没必要。毕竟在我们程序这个 “1D” 的东西里面，表示一幅 图，还是需要额外的空间的，不如直接使用 数组 或者 链表 表示来得实在。

树

如果一幅图 G，含有 V 个顶点，而 V-1 条边不含有 环 切相互连通，并且任意一对顶点之间只存在一条连通的路径，我们可以称 图 为 一棵 树。并且 树 中任意新增一条 边 都会产生 环，任意删除一条 边 都会得到两棵独立的 树。 我们先来看看 环 的定义：

如图，黄色部分组成一个 环。 而 树 是没有 环 的：

如上图所示，12 个顶点，含有 11 条边，每个顶点相互连通，增删任意一条边都会使这棵 树 变为 图。

森林

树 多了就是 森林： 如 图，两棵 树 组成一篇 森林。

生成树森林算法

那结合应用，我们要在一个 图 里面 规划 最短路径的 树，实际应用大概就是 地图 寻找最短线路的应用了吧，所以我们就需要在一个 图 里面去查找 线路，而 线路 连接起来，刚好就是一个 树：

如图，在一个 图 里面查找顶点之间，然后连接边使其生成一棵 树，称之为 生成树森林算法。

无向图

图的实现

无向图 比较简单，所以我们先来说说 无向图 吧，首先，我们得考虑一下，怎么样才能把上面这幅图（为了方便我改成 0-11 的数字了）给初始化到内存中去，可是内存中貌似只有 数组 这种结构比较好用了，所以肯定是数组啦，但是怎么表示还是个问题，我们的程序一般都要求要又快又省空间，所以我们有几个方案，矩阵（类似于一个正方形的数组，如果两个边连接，我们就在 array[x][y] 做一个标记，一般用 bool 表示），不过当顶点几百上千万的时候，就跟捉鸡了；Edge 集合，但是我们查找边的时候，每次总是需要遍历整个 Edge 集合，也显得不好；第三个方案就是 动静结合 了，初始化一个 V个顶点 的数组，而数组里边的数组是一个可拓展性的数组，这样我们只需要记录当前这个 顶点 和 另外一个顶点 连接的情况就可以了，大概就会变成下面这个样子：

1
2
3
4
5
6
7
8
9
10
11
12
0 -> [1,2,3,4]
1 -> [0,8]
2 -> [0,3,5]
3 -> [0,2,6,10]
4 -> [0,7,8]
5 -> [2,6]
6 -> [5,9,3,10]
7 -> [4]
8 -> [1,4]
9 -> [6]
10 -> [3,6,11]
11 -> [10]

所以我们就可以来写代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Graph {

  // 顶点的数目
  private final int V;
  // 边的数目
  private int E;
  // 记录连接情况；
  List<Integer>[] lists;

  public Graph(int v) {
    V = v;
    E = 0;
    lists = (List<Integer>[]) new ArrayList[v];
    for (int i = 0; i < v; i++) {
      lists[i] = new ArrayList<>();
    }
  }

  // 常量级
  public int V () {
    return V;
  }
  // 常量级
  public int E() {
    return E;
  }
  // 常量级
  public void addEdge(int v, int w) {
    lists[v].add(w);
    lists[w].add(v);
    E++;
  }
  // 返回一个顶点所有连接的另外一个顶点
  public Iterable<Integer> adj(int e) {
    return lists[e];
  }
}

然后我们就可以把我们的图给输入进去，等我一下，我写个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class GraphApplication {

  public static void main(String[] args) {
    // 所有连接线
    String[] line = {
        "0-1", "0-2", "0-3", "0-4",
        "1-8", "2-3", "2-5", "3-6", "3-10",
        "4-8", "4-7", "5-6", "6-9", "6-10", "10-11"
    };

    // 创建图用例
    Graph g = new Graph(12);
    for (String _l : line) {
      String[] split = _l.split("-");
      g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
    }
    // 输出：[0, 8, 7]
    System.out.println(g.adj(4));
  }

}

图搜索

那么有图了，就应该用他来做点什么事情了，假设上面那个图，每个顶点是一个城市，我们自然就会想找出 城市0 到 城市11 的有哪些走法，哪种走法最快。所以这时候就出现了 图搜索 的问题了。搜索的方式也有两种，我重新放一下这幅图：

图涉及的搜索方式有两种：深度优先遍历（dfs -- Deep First Search） 和 广度优先遍历（bfs -- Breadth First Search），两种搜索遍历的方式不相同：

  1. 深度优先遍历：顾名思义，深度优先，也就是我从起点出发，从邻近第一个点开始，继续查找接下来的这个顶点，直到查找到的顶点都已经被标记走过了，才回退回来，继续第二个邻近的顶点，比如 0 找到 1 这个顶点，而 1 与 [0, 8] 相邻，0 是进来的点已经被标记过了，所以再走到 顶点8，顶点8 再走到 顶点4，而 顶点4 邻接顶点只有 顶点7 还没标记，顶点7 就是极限了，这时候要回退到 顶点4，顶点4 也没有未标记的顶点，再回退到 顶点8，再退 顶点1，然后再按照上面的思路开始遍历 顶点2 以及 顶点2的邻接顶点，也就是我们的指针只有走到底层无路可走才会回退继续遍历上一个顶点未标记的点。
  2. 广度优先遍历：如果说深度是遍历到最深处无路可走的时候才返回的话，而广度则是一步一步推进的去遍历，我们先想象成多线程的情况，顶点0 开始，分裂出了 3个线程：[顶点1、顶点2、顶点3]，然后 3个子线程 再分别分裂其 子线程，类似于细胞分裂的情况，但是我们研究的时候肯定不会用这么高级的特性，所以我们需要一个数据结构：队列。首先，顶点0 开始，将 [顶点1、顶点2、顶点3] 推入队列中，然后 顶点1 出列并做标记，将其邻接未被标记的顶点：[顶点8] 推入队列，所以我们程序的遍历顺序将会变成 顶点0、顶点1、顶点2、顶点3、顶点8（顶点1出列时标记）、顶点5（顶点2出列时标记）...。

搞两个动态图看看，不过因为大小限制我删除了右边的顶点 orz 深度优先搜索动图：

广度优先搜索动图：

两个算法的应用场景：广度优先搜索 我们可以搜索两个点之间最短的距离（其实不然，但是可以先简单这么理解，经过哪几条线路最快到达，因为线路还带有距离的嘛，所以下面的加权才是真正的场景）而 深度优先搜索 呢，好像针对上面的问题没什么作为，但是如果读过 Spring 源码的话，就可以很简单的明白，依赖搜索我写的 屎山 的时候，用的恰恰好就是 深度优先搜索，找到最后一个没有依赖的开始向上初始化，直达所有的 Bean 都初始化好了，就可以开始工作了。

深度优先搜索实现

那么因为上面那张图，基本所有顶点都是连通的，为了测试，断开部分连接：

然后我们使用工具类的形式来做搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
public class DFS {

  /** 有多少个顶点可达 */
  private int count;
  /** 使用数组的下标表示顶点，记录哪些点被遍历过了 */
  private boolean[] marked;

  public DFS(Graph g, int startPoint) {
    marked = new boolean[g.V()];
    dfs(g, startPoint);
  }

  /**
   * 递归搜索，递归到最底层的时候才会返回来递归前一个顶点.
   * @param g 图实例.
   * @param startPoint 顶点.
   */
  private void dfs(Graph g, int startPoint) {
    marked[startPoint] = true;
    count++;
    for (int v : g.adj(startPoint)) {
      if (marked[v]) {
        continue;
      }
      // 递归遍历底层的所有节点
      dfs(g, v);
    }
  }

  /**
   * 获取有多少个与构造方法的起点关联的个数.
   * @return
   */
  public int getCount() {
    return count;
  }

  /**
   * 获取所有可达的顶点.
   * @return
   */
  public int[] available() {
    return IntStream.range(0, marked.length)
        .filter(i -> marked[i])
        .toArray();
  }

}

public class GraphApplication {

  public static void main(String[] args) {
    // 所有顶点
    int[] E = {
        0, 1, 2, 3, 4,
        5, 6, 7, 8, 9,
        10, 11
    };
    // 所有连接线
    String[] line = {
        "0-2", "0-3",
        "1-8", "2-3", "2-5", "3-6", "3-10",
        "4-8", "4-7", "5-6", "6-9", "6-10", "10-11"
    };

    // 创建图用例
    Graph g = new Graph(E.length);
    for (String _l : line) {
      String[] split = _l.split("-");
      g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
    }
    System.out.println(g.adj(4));

    DFS dfs = new DFS(g, 0);
    System.out.println("从顶点0出发，共有" + dfs.getCount() +
        "个顶点可达，分别有：" + Arrays.toString(dfs.available()));
  }

}
// 输出：
[8, 7]
从顶点0出发，共有8个顶点可达，分别有：[0, 2, 3, 5, 6, 9, 10, 11]

广度优先搜索实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class BFS {

  /** 有多少个顶点可达 */
  private int count;
  /** 使用数组的下标表示顶点，记录哪些点被遍历过了 */
  private boolean[] marked;

  public BFS(Graph g, int startPoint) {
    marked = new boolean[g.V()];
    bfs(g, startPoint);
  }

  /**
   * 递归搜索，递归到最底层的时候才会返回来递归前一个顶点.
   * @param g 图实例.
   * @param startPoint 顶点.
   */
  private void bfs(Graph g, int startPoint) {
    // 队列代替递归循环
    Queue<Integer> q = new ArrayDeque<>();
    marked[startPoint] = true;
    q.add(startPoint);
    count++; // 标记第一个可达
    while (!q.isEmpty()) {
      int first = q.poll();
      for (int point : g.adj(first)) {
        if (marked[point]) {
          continue;
        }
        marked[point] = true;
        q.add(point);
        count++;
      }
    }
  }

  /**
   * 获取有多少个与构造方法的起点关联的个数.
   * @return
   */
  public int getCount() {
    return count;
  }

  public int[] available() {
    return IntStream.range(0, marked.length)
        .filter(i -> marked[i])
        .toArray();
  }

}

public class GraphApplication {

  public static void main(String[] args) {
    // 所有顶点
    int[] E = {
        0, 1, 2, 3, 4,
        5, 6, 7, 8, 9,
        10, 11
    };
    // 所有连接线
    String[] line = {
        "0-2", "0-3",
        "1-8", "2-3", "2-5", "3-6", "3-10",
        "4-8", "4-7", "5-6", "6-9", "6-10", "10-11"
    };

    // 创建图用例
    Graph g = new Graph(E.length);
    for (String _l : line) {
      String[] split = _l.split("-");
      g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
    }
    System.out.println(g.adj(4));

    DFS dfs = new DFS(g, 0);
    System.out.println("从顶点0出发，共有" + dfs.getCount() +
        "个顶点可达，分别有：" + Arrays.toString(dfs.available()));

    BFS bfs = new BFS(g, 0);
    System.out.println("从顶点0出发，共有" + bfs.getCount() +
        "个顶点可达，分别有：" + Arrays.toString(bfs.available()));
  }

}

// 输出：
[8, 7]
从顶点0出发，共有8个顶点可达，分别有：[0, 2, 3, 5, 6, 9, 10, 11]
从顶点0出发，共有8个顶点可达，分别有：[0, 2, 3, 5, 6, 9, 10, 11]

图相关基础问题

那么这些问题，我们都可以使用 委托模式 来做，将一个图交给委托者，让他来做计算。

连通分量

连通分量，我们可以简单的认为就是一个图，有多少个独立的连通，比如上图，很明显有2个，那么这个问题我们可以使用 深度优先搜索 来做：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class ConnGraphUtil {

  /** 连通分量计数器 */
  private int count;
  /** 使用数组的下标表示顶点，记录哪些点被遍历过了 */
  private boolean[] marked;

  public ConnGraphUtil(Graph g, int startPoint) {
    marked = new boolean[g.V()];
    // 修改为遍历所有的顶点，如果每次dfs搜索出来以后
    // 还有没有被记录的顶点，count加1
    for (int i = 0; i < g.V(); i++) {
      if (!marked[i]) {
        dfs(g, i);
        count++;
      }
    }
  }

  private void dfs(Graph g, int startPoint) {
    marked[startPoint] = true;
    count++;
    for (int v : g.adj(startPoint)) {
      if (marked[v]) {
        continue;
      }
      // 递归遍历底层的所有节点
      dfs(g, v);
    }
  }

  public int getCount() {
    return count;
  }

}

如代码所示，我们使用深度，将会遍历所有顶点。如果搜索一次以后，还有的点没有被记录到，则我们记录的分量数 加1 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void main(String[] args) {
  // 所有顶点
  int[] E = {
    0, 1, 2, 3, 4,
    5, 6, 7, 8, 9,
    10, 11
  };
  // 所有连接线
  String[] line = {
    "0-2", "0-3",
    "1-8", "2-3", "2-5", "3-6", "3-10",
    "4-8", "4-7", "5-6", "6-9", "6-10", "10-11"
  };

  // 创建图用例
  Graph g = new Graph(E.length);
  for (String _l : line) {
    String[] split = _l.split("-");
    g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
  }

  System.out.println("一共有" + new ConnGraphUtil(g).getCount() + "个连通分量");
}
// 输出：
一共有2个连通分量

我们可以使用这种模型，来查找一个网络中，有多少个局域网。

最短连通路径

而最短连通的路径中，则需要使用 广度优先搜索 来做，然后我们需要一个数组来保存 连接的点-起点 的数值 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class ShortestGraphUtil {

  /** 使用数组的下标表示顶点，记录哪些点被遍历过了 */
  private boolean[] marked;
  private int endPoint;
  private int startPoint;
  private int[] edgeTo;

  public ShortestGraphUtil(Graph g, int startPoint, int endPoint) {
    marked = new boolean[g.V()];
    edgeTo = new int[g.V()];
    this.endPoint = endPoint;
    this.startPoint = startPoint;
    bfs(g, startPoint);
  }

  /**
   * 递归搜索，递归到最底层的时候才会返回来递归前一个顶点.
   * @param g 图实例.
   * @param startPoint 顶点.
   */
  private void bfs(Graph g, int startPoint) {
    // 队列代替递归循环
    Queue<Integer> q = new ArrayDeque<>();
    marked[startPoint] = true;
    q.add(startPoint);
    while (!q.isEmpty()) {
      int point = q.poll();
      for (int _point : g.adj(point)) {
        if (marked[_point]) {
          continue;
        }
        marked[_point] = true;
        q.add(_point);
        // 下标保存被连接的点的值，数组值保存上一个点的值
        edgeTo[_point] = point;
        if (_point == endPoint) {
          return;
        }
      }

    }
  }

  public Iterable<Integer> pathTo() {
    // 使用栈反过来查找edgeTo
    Stack<Integer> path = new Stack<>();
    for (int x = endPoint; x != startPoint; x = edgeTo[x]) {
      path.push(x);
    }
    path.push(startPoint);
    return path;
  }


  public static void main(String[] args) {
    // 所有顶点
    int[] E = {
      0, 1, 2, 3, 4,
      5, 6, 7, 8, 9,
      10, 11
    };
    // 所有连接线
    String[] line = {
      "0-2", "0-3",
      "1-8", "2-3", "2-5", "3-6", "3-10",
      "4-8", "4-7", "5-6", "6-9", "6-10", "10-11"
    };

    // 创建图用例
    Graph g = new Graph(E.length);
    for (String _l : line) {
      String[] split = _l.split("-");
      g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
    }

    ShortestGraphUtil u = new ShortestGraphUtil(g, 0, 11);
    System.out.println(u.pathTo());
  }

}
// 输出：
[11, 10, 3, 0]

有向图

有向图的实现

有向图和无向图的区别就只是在于，顶点到另外一个顶点是有方向的，所以我们只需要改改无向图的实现即可实现有向图了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Digraph {

  // 顶点的数目
  private final int V;
  // 边的数目
  private int E;
  // 记录连接情况；
  List<Integer>[] lists;

  public Digraph(int v) {
    V = v;
    E = 0;
    lists = (List<Integer>[]) new List[v];
    for (int i = 0; i < v; i++) {
      lists[i] = new ArrayList<>();
    }
  }

  public int V () {
    return V;
  }

  public int E() {
    return E;
  }

  public void addEdge(int v, int w) {
    // 只是添加一个方向的，比无向图少了一个返回
    lists[v].add(w);
    E++;
  }

  // 返回一个顶点所有连接的另外一个顶点
  public Iterable<Integer> adj(int e) {
    return lists[e];
  }

  // 反转图的方向
  public Digraph reverse() {
    Digraph g = new Digraph(V);
    for (int i = 0; i < V; i++) {
      for (Integer j : adj(i)) {
        g.addEdge(j, i);
      }
    }
    return g;
  }

}

然后我们 GraphApplication 中的连接就会变成：

可达性

然后上面 无向图 的 深度优先搜索 和 广度优先搜索 的代码只要把接参改为 Diagraph 参数即可完美运行（啊呀真方便，不用重新写了 orz）

环和有向无环

环就是一个顶点出发遍历他周围的顶点，然后发现，他可以回到第一个顶点，所以我们就可以通过深度优先搜索来写这个算法了，所以其实就是计算 图 中所有的路径中加点计算： 为了实验，构建了这样一幅图：

然后，我们用 深度优先 来做：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class CycleDiagraphUtil {

  /** 使用数组的下标表示顶点，记录哪些点被遍历过了 */
  private final boolean[] marked;
  private final int[] edgeTo;
  private final boolean[] onStack;
  private Stack<Integer> cycle;

  public CycleDiagraphUtil(Digraph g, int startPoint) {
    marked = new boolean[g.V()];
    edgeTo = new int[g.V()];
    onStack = new boolean[g.V()];
    dfs(g, startPoint);
  }


  private void dfs(Digraph g, int point) {
    onStack[point] = true;
    marked[point] = true;

    for (Integer v : g.adj(point)) {
      if (hasCycle()) {
        return;
      }
      if (!marked[v]) {
        edgeTo[v] = point;
        dfs(g, v);
      } else if (onStack[v]) {
        cycle = new Stack<>();
        for (int x = point; x != v; x = edgeTo[x]) {
          cycle.push(x);
        }
        cycle.push(v);
        cycle.push(point);
      }
    }

    onStack[point] = false;
  }

  public Iterable<Integer> cycle() {
    return cycle;
  }

  public boolean hasCycle() {
    return cycle != null;
  }

  public static void main(String[] args) {
    // 所有连接线
    String[] line = {
        "2-0", "0-3",
        "1-8", "3-2", "2-5", "3-6", "3-10",
        "4-8", "4-7", "5-6", "6-9", "6-10", "10-11"
    };

    // 创建图用例
    Digraph g = new Digraph(12);
    for (String _l : line) {
      String[] split = _l.split("-");
      g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
    }

    CycleDiagraphUtil cycleDiagraphUtil = new CycleDiagraphUtil(g, 2);
    System.out.println(cycleDiagraphUtil.cycle());
  }

}
// 输出：
[3, 0, 2, 3]

拓扑排序

拓扑排序 指的是一个 有向无环图，顶点的按照依赖的顺序来排序的 图排序算法，而顺序也分为 前序 后序 逆后序 的不同顺序。举一些比较简单的🌰，比如 任务调度，我们在执行一系列任务的时候，一般都有任务优先级，比如先执行查询产品的库存是否充足，才会去创建订单，只有创建了订单以后，才能进行订单的支付等等。 而前序遍历，可以让我们清楚的识别任务的依赖顺序，后序则可以让我们清楚了解任务完成执行的顺序，而逆后序则更加类似于任务执行中，日志在我们的文件中打印的情况。 那么排序，我们用的还是需要 深度优先搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class DFSIter {

  private boolean[] marked;

  /** 使用队列来存储前序和后续遍历 */
  private Queue<Integer> pre;
  private Queue<Integer> post;
  /** 栈存储逆后序的顺序 */
  private Stack<Integer> reversePost;

  public DFSIter(Digraph g) {
    this.marked = new boolean[g.V()];
    this.pre = new ArrayDeque<>();
    this.post = new ArrayDeque<>();
    this.reversePost = new Stack<>();
    for (int i = 0; i < g.V(); i++) {
      if (!marked[i]) {
        dfs(g, i);
      }
    }
  }

  private void dfs(Digraph g, int v) {
    this.pre.offer(v);
    this.marked[v] = true;
    for (Integer w : g.adj(v)) {
      if (!this.marked[w]) {
        dfs(g, w);
      }
    }
    this.post.offer(v);
    this.reversePost.push(v);
  }

  public Queue<Integer> getPre() {
    return pre;
  }

  public Queue<Integer> getPost() {
    return post;
  }

  public Iterable<Integer> getReversePost() {
    List<Integer> l = new ArrayList<>();
    for (int i = reversePost.size(); i > 0; i--) {
      l.add(reversePost.pop());
    }
    return l;
  }

  public static void main(String[] args) {
    // 所有连接线
    String[] line = {
        "0-2", "0-3",
        "1-8", "3-2", "2-5", "3-6", "3-10",
        "4-8", "4-7", "5-6", "6-9", "6-10", "10-11"
    };

    // 创建图用例
    Digraph g = new Digraph(12);
    for (String _l : line) {
      String[] split = _l.split("-");
      g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
    }

    DFSIter dfsIter = new DFSIter(g);
    System.out.println(dfsIter.getPre());
    System.out.println(dfsIter.getPost());
    System.out.println(dfsIter.getReversePost());
  }

}

强连通性

强连通性表示的是，给定一个图和两个顶点 A B，同时存在一条线路可以从 A 到达 B，也存在另外一条线路从 B 到 A，就说明 A 和 B 是具有 强连通性 的。而 环 就是 强连通性的一种方式 那么，一个叫做 Kosaraju 的人，就发现了，如果我对一个有向图进行 深度遍历，发现 A -> B，而如果存在一个路径是 B->A 的话，那么在这个有向图的反向图中，必定存在 A -> B 的路径： 首先，先构建一个图：

图中，2 和 8 组成了强连通性的分量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class KosarajuCC {

  private boolean[] marked;
  private int[] id;
  private int count;

  public KosarajuCC(Digraph g) {
    marked = new boolean[g.V()];
    id = new int[g.V()];
    DFSIter dfsIter = new DFSIter(g.reverse());
    for (Integer i : dfsIter.getReversePost()) {
      if (!marked[i]) {
        dfs(g, i);
        count++;
      }
    }
  }

  private void dfs(Digraph g, Integer i) {
    marked[i] = true;
    id[i] = count;
    for (Integer v : g.adj(i)) {
      if (!marked[v]) {
        dfs(g, v);
      }
    }
  }

  public boolean strongConnect(int v, int w) {
    return id[v] == id[w];
  }

  public static void main(String[] args) {
    // 所有连接线
    String[] line = {
        "0-2", "1-0",
        "1-7", "2-4",
        "2-6", "6-3",
        "6-5", "5-2",
        "4-8", "8-6"
    };

    // 创建图用例
    Digraph g = new Digraph(9);
    for (String _l : line) {
      String[] split = _l.split("-");
      g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
    }

    KosarajuCC kosarajuCC = new KosarajuCC(g);
    System.out.println("1和7是强连通性的吗？" + kosarajuCC.strongConnect(1, 7));
    System.out.println("2和8是强连通性的吗？" + kosarajuCC.strongConnect(8, 2));
  }

}

那么，这个算法感觉我们需要来分析一下。 首先反转一下这个图：

那么现在有这个理论，如果原图中存在一条 2 -> 8 并且这个连接是强连通性的话，那么就需要证明还存在一条 8 -> 2 的路径，也就是说他的反向图中，存在一个 2 -> 8 的连接。那么 长得帅的同学 就要问了，我直接使用原图来证明 8 -> 2 不就行了吗，为什么还要 反向图 来出场？还不是为了速度和递归的程度。 证明 2 到 8 有两个路径，那么原图从反向图就能优先得到类似“最后处理”的顶点，开始在原图往回深度遍历标记 count变量，因为正向深度如果很深的话，那么反向图来遍历正向图，所需要的递归深度将会更少。这也是 Kosaraju 发现的这个算法的奇妙之点。

加权图和最小生成树

加权图的数据结构表示

图 生成 最小树，意思就是，通过寻找 图 中所有 顶点 和 边，然后找出来能构建 一棵树 的一种算法。

上面所说的 树 的定义：如果一幅图 G，含有 V 个顶点，而 V-1 条边不含有 环 切相互连通，并且任意一对顶点之间只存在一条连通的路径，我们可以称 图 为 一棵 树。并且 树 中任意新增一条 边 都会产生 环，任意删除一条 边 都会得到两棵独立的 树。

但是，我们说了这么久的 图，边 都是没有数值表示其 大小 的，虽然画在上面的 图 边 的长短让我们产生了错觉以为是有数值的。那么现在我们就需要给 边 进行赋值，术语称为 权重。 权重 在实际应用中可以表示很多东西，比如说 顶点 表示城市，边 表示线路，那么 权重 可以表示堵车程度，或者线路的长短。 SO，我们就需要构建 加权图 的类了，构建图的边情况，我就直接抄书中的案例了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class EdgeWeightedGraph {

  /** 顶点的数量 */
  private final int V;
  /** 边的数量 */
  private int E;
  private List<Edge>[] adj;

  /**
   * 表示加权图的两个顶点以及边的权重.
   */
  public static class Edge implements Comparable<Edge> {
    private final int v;
    private final int w;
    private final double weight;

    public Edge(int v, int w, double weight) {
      this.v = v;
      this.w = w;
      this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
      return Double.compare(this.weight, o.weight);
    }

    public double weight() {
      return weight;
    }

    public int other(int vertex) {
      if (vertex == v) return w;
      else if (vertex == w) return v;
      else throw new IllegalArgumentException("Illegal endpoint");
    }

  }

  public EdgeWeightedGraph(int v) {
    V = v;
    E = 0;
    adj = (List<Edge>[]) new List[v];
    for (int i = 0; i < v; i++) {
      adj[i] = new ArrayList<>();
    }
  }

  /**
   * 增加一条权重边.
   * @param edge Edge.
   */
  public void addEdge(Edge edge) {
    adj[edge.v].add(edge);
    adj[edge.w].add(edge);
    E++;
  }

  public int E() {
    return E;
  }

  public static void main(String[] args) {
    String[] lines = {
        "4-5-0.35",
        "4-7-0.37",
        "5-7-0.28",
        "0-7-0.16",
        "1-5-0.32",
        "0-4-0.38",
        "2-3-0.17",
        "1-7-0.19",
        "0-2-0.26",
        "1-2-0.36",
        "1-3-0.29",
        "2-7-0.34",
        "6-2-0.40",
        "3-6-0.52",
        "6-0-0.58",
        "6-4-0.9"
    };
    EdgeWeightedGraph ewg = new EdgeWeightedGraph(8);
    for (String _line : lines) {
      String[] split = _line.split("-");
      String v = split[0], w = split[1], weight = split[2];
      int vi = Integer.parseInt(v), vw = Integer.parseInt(w);
      ewg.addEdge(new Edge(vi, vw, Double.parseDouble(weight)));
    }
    assert ewg.E() == lines.length;
  }

}

那大概这幅图就是这样的：

这时候边的长短就真的是代表权重了。

最小生成树算法

那么先来宏观观察一下上面这幅图生成一棵最小树是什么样子的：

然后我们尝试把这棵树一分为二：

我们即可发现，0-2 这条边，是两棵树的最小连接边（权重是 0.26）。所以我们可以推出来，两个顶点集合中，连接的边肯定是最小 横切边，并且这条最小 横切边肯定存在于我们要生成的 树 中。 所以我们要生成一棵 树，就可以这么做了，首先遍历当前这个顶点，假设其他所有顶点是另外一棵 树 的顶点的集合，那么我们只要从这个顶点出发，遍历连接的 横切边们，最小的那条取出来就可以了，这也是我们常听说的 贪心算法。

度娘的解释：贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。

那么第一个算法就是 prim算法，他采用了一个优先级队列来保存当前遍历到的顶点的所有路径，然后从一个顶点开始，通过总是弹出来目前队列中最小的路径来标记图中所有的顶点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public class Prim {

  /** 标记属性 */
  private boolean[] marked;

  /** 最小树的队列 */
  private Queue<Edge> result;

  /** 一个优先级队列，在计算中需要用到 */
  private PriorityQueue<Edge> tmp;

  public Prim(EdgeWeightedGraph g) {
    tmp = new PriorityQueue<>();
    result = new ArrayDeque<>();
    marked = new boolean[g.V()];

    marked(g, 0);
    while (!tmp.isEmpty()) {
      Edge poll = tmp.poll();
      int v = poll.either();
      int w = poll.other(v);
      if (marked[v] && marked[w]) {
        continue;
      }
      result.add(poll);
      if (!marked[v]) marked(g, v);
      if (!marked[w]) marked(g, w);
    }
  }

  private void marked(EdgeWeightedGraph g, int v) {
    marked[v] = true;
    for (Edge edge : g.adj(v)) {
      if (!marked[edge.other(v)]) {
        tmp.add(edge);
      }
    }
  }

  public Queue<Edge> getResult() {
    return result;
  }

  public static void main(String[] args) {
    String[] lines = {
        "4-5-0.35",
        "4-7-0.37",
        "5-7-0.28",
        "0-7-0.16",
        "1-5-0.32",
        "0-4-0.38",
        "2-3-0.17",
        "1-7-0.19",
        "0-2-0.26",
        "1-2-0.36",
        "1-3-0.29",
        "2-7-0.34",
        "6-2-0.40",
        "3-6-0.52",
        "6-0-0.58",
        "6-4-0.9"
    };
    EdgeWeightedGraph ewg = new EdgeWeightedGraph(8);
    for (String _line : lines) {
      String[] split = _line.split("-");
      String v = split[0], w = split[1], weight = split[2];
      int vi = Integer.parseInt(v), vw = Integer.parseInt(w);
      ewg.addEdge(new Edge(vi, vw, Double.parseDouble(weight)));
    }
    System.out.println(new Prim(ewg).getResult());
  }

}
// 输出：
[Edge{v=0, w=7, weight=0.16}, Edge{v=1, w=7, weight=0.19}, Edge{v=0, w=2, weight=0.26}, Edge{v=2, w=3, weight=0.17}, Edge{v=5, w=7, weight=0.28}, Edge{v=4, w=5, weight=0.35}, Edge{v=6, w=2, weight=0.4}]

很明显就是通过一个优先级队列将目前我所知道的所有边进行排序，然后我只处理目前最短的那条边认为他就是我要的最小生成树的边了。

那么另外一个算法就是 Kruskal 算法，他的构造方法也是和 Prim 一样一步一步的读取树的连接线，但是不同的是，他不是从顶点出发去遍历，而是读取所有边进行排序，然后遍历这些边去连接，直到连接的新的图的边树等于 顶点数 - 1。不过实现还是蛮简单的，但是需要一个额外的类，也就是 连通器类，用于记录新的图连接的顶点，那我就直接拿《算法》里边的实现来演示就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 首先需要一个连通类来记录，通过数组以及下标一致来寻找连通的分量
public class UF {

  private int[] parent;  
  private byte[] rank;   
  private int count;     

  public UF(int n) {
    if (n < 0) throw new IllegalArgumentException();
    count = n;
    parent = new int[n];
    rank = new byte[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      rank[i] = 0;
    }
  }
  // 判断两个顶点是否已经连接
  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }
  // 连接两个连通分量
  public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) return;

    if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
    else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
    else {
      parent[rootQ] = rootP;
      rank[rootP]++;
    }
    count--;
  }

}

public class KruskalMST {

  private Queue<Edge> mst = new Queue<>();

  public KruskalMST(EdgeWeightedGraph G) {
    // more efficient to build heap by passing array of edges
    MinPQ<Edge> pq = new MinPQ<Edge>();
    for (Edge e : G.edges()) {
      pq.insert(e);
    }

    // run greedy algorithm
    UF uf = new UF(G.V());
    while (!pq.isEmpty() && mst.size() < G.V() - 1) {
      Edge e = pq.delMin();
      int v = e.either();
      int w = e.other(v);
      if (uf.find(v) != uf.find(w)) { // v-w does not create a cycle
        uf.union(v, w);  // merge v and w components
        mst.enqueue(e);  // add edge e to mst
      }
    }
  }

}

可以看到只需要一个队列，然后配合连通分量就可以实现查找最小树。

加权有向图和最短线路问题

加权有向图数据结构表示

加权有向图就更加贴近实际生活用处了，比如一个顶点去到另外一个顶点，我们可以使用我们最熟悉的地图导航来说。顶点就是一个一个的建筑物，而我们通常需要查询从当前点去到另外一个点的最短距离。所以这时候边就拥有了两个特性：1. 边的权重表示距离；2. 边的方法代表路的方向。 当然啦，不仅仅是地图有这个用处，像线路、优先级任务等等，都需要有向图这种数据结构来表示。所以首先我们还是需要一个加权有向图的类，用来表示一副加权有向图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class DirectedEdgeWeightedGraph {

  /** 顶点的数量 */
  private final int V;
  /** 边的数量 */
  private int E;
  private List<DirectedEdge>[] adj;

  /**
   * 表示加权图的两个顶点以及边的权重.
   */
  public static class DirectedEdge implements Comparable<DirectedEdge> {
    private final int from;
    private final int to;
    private final double weight;

    public DirectedEdge(int from, int to, double weight) {
      this.from = from;
      this.to = to;
      this.weight = weight;
    }

    @Override
    public int compareTo(DirectedEdge o) {
      return Double.compare(this.weight, o.weight);
    }

    public double weight() {
      return weight;
    }

    public int from() {
      return from;
    }

    public int to() {
      return to;
    }
  }

  public DirectedEdgeWeightedGraph(int v) {
    V = v;
    E = 0;
    adj = (List<DirectedEdge>[]) new List[v];
    for (int i = 0; i < v; i++) {
      adj[i] = new ArrayList<>();
    }
  }

  /**
   * 增加一条权重边.
   * @param edge Edge.
   */
  public void addEdge(DirectedEdge edge) {
    adj[edge.from].add(edge);
    E++;
  }

  public List<DirectedEdge> adj(int v) {
    return adj[v];
  }

  public int V() {
    return V;
  }

  public int E() {
    return E;
  }

  public static void main(String[] args) {
    String[] lines = {
        "4-5-0.35",
        "5-4-0.35",
        "4-7-0.37",
        "5-7-0.28",
        "7-5-0.28",
        "5-1-0.32",
        "0-4-0.38",
        "0-2-0.26",
        "7-3-0.39",
        "1-3-0.29",
        "2-7-0.34",
        "6-2-0.40",
        "3-6-0.52",
        "6-0-0.58",
        "6-4-0.93",
    };
    DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8);
    for (String _line : lines) {
      String[] split = _line.split("-");
      String v = split[0], w = split[1], weight = split[2];
      int vi = Integer.parseInt(v), vw = Integer.parseInt(w);
      ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight)));
    }
    assert ewg.E() == lines.length;
  }

}

那么 main 函数中的这个图大概长的是这样子：

好了，图有了，就可以来研究一些算法了。

最短路径

那么需要特别注意几个性质：

  1. 路径是有向的：首先，路径需要注意数据结构中方向的表示，也就是 from -> to；
  2. 权重不一定是距离：可以是电阻呀、汇率呀等等我们可以想到的可以表示数值的元素；
  3. 并不是所有顶点相互可达：因为有方向了，所以难免会进死胡同；
  4. 最短路径可能存在多个
  5. 可能有平行边或者自环：自环看起来一般没有意义（当然如果权重不为零我们需要另外说事），而平行边我们通常选择的是权重最小的，所以先不考虑这些扰人的元素。

那么首先我们来看一个算法：Dijkstra算法，它的实现有点类似于 Kruskal算法 ，就是总是遍历目前已发现的最小权重的 边，并且遍历已经有路径的可达点中，把这些点已经保存的权重和线路的集合作比较，如果比目前的小的话，就把原先处理的删掉，替换成目前的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class DijkstraShortest {

  double[] distTo;
  DirectedEdge[] edgeTo;
  /** 总是计算当前队列中最小的边 */
  IndexMinPQ<Double> pq;

  public DijkstraShortest(DirectedEdgeWeightedGraph g, int s) {
    edgeTo = new DirectedEdge[g.V()];
    distTo = new double[g.V()];
    pq = new IndexMinPQ<>(g.V());
    for (int i = 0; i < g.V(); i++) {
      distTo[i] = Double.POSITIVE_INFINITY;
    }
    distTo[s] = 0.0;

    pq.insert(s, 0.0);
    while (!pq.isEmpty()) {
      /* 放松当前遍历到的点 */
      relax(g, pq.delMin());
    }
  }

  private void relax(DirectedEdgeWeightedGraph g, int v) {
    for (DirectedEdge directedEdge : g.adj(v)) {
      int w = directedEdge.to();
      /* 遍历当前顶点连接的所有点，然后计算如果现有的距离比目前存储的大的话，就开始替换 */
      if (distTo[w] > distTo[v] + directedEdge.weight()) {
        distTo[w] = distTo[v] + directedEdge.weight();
        edgeTo[w] = directedEdge;
        if (pq.contains(w)) pq.changeKey(w, distTo[w]);
        else pq.insert(w, distTo[w]);
      }
    }
  }

  double distTo(int v) {
    return distTo[v];
  }

  boolean hasPathTo(int v) {
    return distTo[v] < Double.POSITIVE_INFINITY;
  }

  Iterable<DirectedEdge> pathTo(int v) {
    if (!hasPathTo(v)) {
      return null;
    }

    Stack<DirectedEdge> path = new Stack<>();
    for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
      path.push(e);
    }
    return path;
  }

  public static void main(String[] args) {
    String[] lines = {
        "4-5-0.35",
        "5-4-0.35",
        "4-7-0.37",
        "5-7-0.28",
        "7-5-0.28",
        "5-1-0.32",
        "0-4-0.38",
        "0-2-0.26",
        "7-3-0.39",
        "1-3-0.29",
        "2-7-0.34",
        "6-2-0.40",
        "3-6-0.52",
        "6-0-0.58",
        "6-4-0.93",
    };
    DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8);
    for (String _line : lines) {
      String[] split = _line.split("-");
      String v = split[0], w = split[1], weight = split[2];
      int vi = Integer.parseInt(v), vw = Integer.parseInt(w);
      ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight)));
    }

    DijkstraShortest d = new DijkstraShortest(ewg, 0);
    for (int i = 0; i < ewg.V(); i++) {
      System.out.println("0到" + i + "的最短距离是：" + d.distTo(i) + "，路径是：" + d.pathTo(i));
    }
  }

}
// 输出：
0到0的最短距离是：0.0，路径是：[]
0到1的最短距离是：1.05，路径是：[DirectedEdge{from=5, to=1, weight=0.32}, DirectedEdge{from=4, to=5, weight=0.35}, DirectedEdge{from=0, to=4, weight=0.38}]
0到2的最短距离是：0.26，路径是：[DirectedEdge{from=0, to=2, weight=0.26}]
0到3的最短距离是：0.9900000000000001，路径是：[DirectedEdge{from=7, to=3, weight=0.39}, DirectedEdge{from=2, to=7, weight=0.34}, DirectedEdge{from=0, to=2, weight=0.26}]
0到4的最短距离是：0.38，路径是：[DirectedEdge{from=0, to=4, weight=0.38}]
0到5的最短距离是：0.73，路径是：[DirectedEdge{from=4, to=5, weight=0.35}, DirectedEdge{from=0, to=4, weight=0.38}]
0到6的最短距离是：1.5100000000000002，路径是：[DirectedEdge{from=3, to=6, weight=0.52}, DirectedEdge{from=7, to=3, weight=0.39}, DirectedEdge{from=2, to=7, weight=0.34}, DirectedEdge{from=0, to=2, weight=0.26}]
0到7的最短距离是：0.6000000000000001，路径是：[DirectedEdge{from=2, to=7, weight=0.34}, DirectedEdge{from=0, to=2, weight=0.26}]

加权有向无环图的最短路径

那如果我们知道一幅图是无环的，并且我们假设顶点是一个一个的任务，而且这些任务相互依赖，而我们需要找到指定的某个任务到达另外一个任务的最短路径。我们就可以改造上面的 Dijkstra算法，使其支持更快的搜索出 无环有向图 中的最短路径。那么既然是 无环有向图，那么就可以从遍历放松边的思路开始思考，我们上面对于 无环 提出了一个顶点排序法叫做 拓扑排序，那么现在我们可以利用这个排序来寻找图中最短的路径。 那么现在改造一下上面那幅图：

然后我们目前需要一个针对无环有向加权图的拓扑排序算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
public class TopologicalIter {

  private boolean[] marked;

  /** 使用队列来存储前序和后续遍历 */
  private Queue<Integer> pre;
  private Queue<Integer> post;
  /** 栈存储逆后序的顺序 */
  private Stack<Integer> reversePost;

  public TopologicalIter(DirectedEdgeWeightedGraph g) {
//    if (new CycleDiagraphUtil(g, 0).hasCycle()) {
//      throw new RuntimeException("出现环，无法计算拓扑结构");
//    }
    this.marked = new boolean[g.V()];
    this.pre = new ArrayDeque<>();
    this.post = new ArrayDeque<>();
    this.reversePost = new Stack<>();
    for (int i = 0; i < g.V(); i++) {
      if (!marked[i]) {
        dfs(g, i);
      }
    }
  }

  private void dfs(DirectedEdgeWeightedGraph g, int v) {
    this.pre.offer(v);
    this.marked[v] = true;
    for (DirectedEdge w : g.adj(v)) {
      int to = w.to();
      if (!this.marked[to]) {
        dfs(g, to);
      }
    }
    this.post.offer(v);
    this.reversePost.push(v);
  }

  public Queue<Integer> getPre() {
    return pre;
  }

  public Queue<Integer> getPost() {
    return post;
  }

  public Iterable<Integer> getReversePost() {
    List<Integer> l = new ArrayList<>();
    for (int i = reversePost.size(); i > 0; i--) {
      l.add(reversePost.pop());
    }
    return l;
  }

  public static void main(String[] args) {
    String[] lines = {
      "5-4-0.35",
      "4-7-0.37",
      "5-7-0.28",
      "5-1-0.32",
      "4-0-0.38",
      "0-2-0.26",
      "3-7-0.39",
      "1-3-0.29",
      "7-2-0.34",
      "6-2-0.40",
      "3-6-0.52",
      "6-0-0.58",
      "6-4-0.93",
    };
    DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8);
    for (String _line : lines) {
      String[] split = _line.split("-");
      String v = split[0], w = split[1], weight = split[2];
      int vi = Integer.parseInt(v), vw = Integer.parseInt(w);
      ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight)));
    }

    TopologicalIter top = new TopologicalIter(ewg);
    System.out.println(top.getReversePost());
  }

}

// 输出：
[5, 1, 3, 6, 4, 7, 0, 2]

那么我们就需要这个顺序来寻找最短的路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
public class DijkstraNoCycleShortest {

  double[] distTo;
  DirectedEdge[] edgeTo;
  /** 总是计算当前队列中最小的边 */

  public DijkstraNoCycleShortest(DirectedEdgeWeightedGraph g, int s) {
    edgeTo = new DirectedEdge[g.V()];
    distTo = new double[g.V()];
    for (int i = 0; i < g.V(); i++) {
      distTo[i] = Double.POSITIVE_INFINITY;
    }
    distTo[s] = 0.0;

    TopologicalIter t = new TopologicalIter(g);
    for (Integer integer : t.getReversePost()) {
      relax(g, integer);
    }
  }

  private void relax(DirectedEdgeWeightedGraph g, int v) {
    for (DirectedEdge directedEdge : g.adj(v)) {
      int w = directedEdge.to();
      /* 遍历当前顶点连接的所有点，然后计算如果现有的距离比目前存储的大的话，就开始替换 */
      if (distTo[w] > distTo[v] + directedEdge.weight()) {
        distTo[w] = distTo[v] + directedEdge.weight();
        edgeTo[w] = directedEdge;
      }
    }
  }

  double distTo(int v) {
    return distTo[v];
  }

  boolean hasPathTo(int v) {
    return distTo[v] < Double.POSITIVE_INFINITY;
  }

  Iterable<DirectedEdge> pathTo(int v) {
    if (!hasPathTo(v)) {
      return null;
    }

    Stack<DirectedEdge> path = new Stack<>();
    for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
      path.push(e);
    }
    return path;
  }

  public static void main(String[] args) {
    String[] lines = {
        "5-4-0.35",
        "4-7-0.37",
        "5-7-0.28",
        "5-1-0.32",
        "4-0-0.38",
        "0-2-0.26",
        "3-7-0.39",
        "1-3-0.29",
        "7-2-0.34",
        "6-2-0.40",
        "3-6-0.52",
        "6-0-0.58",
        "6-4-0.93",
    };
    DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8);
    for (String _line : lines) {
      String[] split = _line.split("-");
      String v = split[0], w = split[1], weight = split[2];
      int vi = Integer.parseInt(v), vw = Integer.parseInt(w);
      ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight)));
    }

    DijkstraNoCycleShortest d = new DijkstraNoCycleShortest(ewg, 5);
    for (int i = 0; i < ewg.V(); i++) {
      System.out.println("5 -> " + i + ": " + d.pathTo(i));
    }
  }

}

那为啥说引入拓扑结构就会使算法变得高效呢，因为我们知道拓扑排序，是基于图相互依赖的关系（前提是一个无环图）来排序的，那么，我们使用这个排序再来放松顶点边的时候，当 v-w 这条边被放松了过后，起点 v 因为拓扑排序的关系一定排在 w 之前，所以他在被放松以后，就不会继续被访问到，也不会继续被放松，所以算法经过放松的次数比原生的 Dijkstra算法 更少，所以说针对 无环 的有向图，使用拓扑排序会比原来的算法高效。 那么如果我们需要计算出图中的最长路径呢，那么我们只需要将 distTo 数组所有值先初始化为无限小，然后改变放松计算中的大小方向就可以了。

有负权重的有向加权图

如果有向加权图中出现了 负权值 的边，那么我们在寻找顶点与顶点之间距离的时候，就需要识别这些 负权值 所在的顶点是否会跟其他顶点组成一个 环，而这个 环 他的 环总权值 是否 小于0，如果 小于0 则我们需要避开这些 负权值环 否则问题的解决方案将会变得没有意义。这种情况归纳为有可能是输入数值的错误，在现实中我们很少出现问题是有 负数 这种说法的，所以需要去纠正这个错误。 所以，BellmanFordSP 提出了下面这个算法，它能够周期性的检测 负权值环 并避开他：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
public class BellmanFordShortest {

  double[] distTo;
  DirectedEdge[] edgeTo;
  boolean[] onQ;
  Queue<Integer> queue;
  private int cost;
  Iterable<DirectedEdge> cycle;


  /** 总是计算当前队列中最小的边 */

  public BellmanFordShortest(DirectedEdgeWeightedGraph g, int s) {
    edgeTo = new DirectedEdge[g.V()];
    distTo = new double[g.V()];
    onQ = new boolean[g.V()];
    queue = new ArrayDeque<>();
    for (int i = 0; i < g.V(); i++) {
      distTo[i] = Double.POSITIVE_INFINITY;
    }
    distTo[s] = 0.0;
    queue.add(s);
    onQ[s] = true;

    while (!queue.isEmpty() && !hasNegativeCycle()) {
      int v = queue.poll();
      onQ[v] = false;
      relax(g, v);
    }
  }

  private boolean hasNegativeCycle() {
    return cycle != null;
  }

  private void relax(DirectedEdgeWeightedGraph g, int v) {
    for (DirectedEdge directedEdge : g.adj(v)) {
      int w = directedEdge.to();
      /* 遍历当前顶点连接的所有点，然后计算如果现有的距离比目前存储的大的话，就开始替换 */
      if (distTo[w] > distTo[v] + directedEdge.weight()) {
        distTo[w] = distTo[v] + directedEdge.weight();
        edgeTo[w] = directedEdge;
        if (!onQ[w]) {
          queue.add(w);
          onQ[w] = true;
        }
      }
      if (cost++ % g.V() == 0) {
        findNegativeCycle();
        if (hasNegativeCycle()) return;
      }
    }
  }

  private void findNegativeCycle() {
    int v = edgeTo.length;
    DirectedEdgeWeightedGraph t = new DirectedEdgeWeightedGraph(v);
    for (int i = 0; i < v; i++) {
      if (edgeTo[i] != null) {
        t.addEdge(edgeTo[i]);
      }
    }

    DirectedEdgeWeightedGraphFinder f = new DirectedEdgeWeightedGraphFinder(t);
    cycle = f.cycle;
  }

  static class DirectedEdgeWeightedGraphFinder{
    Stack<DirectedEdge> cycle;
    private boolean[] marked;
    private DirectedEdge[] edgeTo;
    private boolean[] onStack;
    DirectedEdgeWeightedGraphFinder(DirectedEdgeWeightedGraph G) {
      // 直接通过dfs找出环
      marked  = new boolean[G.V()];
      onStack = new boolean[G.V()];
      edgeTo  = new DirectedEdge[G.V()];
      for (int v = 0; v < G.V(); v++)
        if (!marked[v]) dfs(G, v);

    }

    private void dfs(DirectedEdgeWeightedGraph G, int v) {
      onStack[v] = true;
      marked[v] = true;
      for (DirectedEdge e : G.adj(v)) {
        int w = e.to();

        if (cycle != null) return;

        else if (!marked[w]) {
          edgeTo[w] = e;
          dfs(G, w);
        }

        else if (onStack[w]) {
          cycle = new Stack<>();

          DirectedEdge f = e;
          while (f.from() != w) {
            cycle.push(f);
            f = edgeTo[f.from()];
          }
          cycle.push(f);

          return;
        }
      }

      onStack[v] = false;
    }


  }

  double distTo(int v) {
    return distTo[v];
  }

  boolean hasPathTo(int v) {
    return distTo[v] < Double.POSITIVE_INFINITY;
  }

  Iterable<DirectedEdge> pathTo(int v) {
    if (hasNegativeCycle())
      throw new UnsupportedOperationException("Negative cost cycle exists");
    if (!hasPathTo(v)) {
      return null;
    }

    Stack<DirectedEdge> path = new Stack<>();
    for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
      path.push(e);
    }
    return path;
  }

  public static void main(String[] args) {
    String[] lines = {
        "4%5%0.35",
        "5%4%0.35",
        "4%7%0.37",
        "5%7%0.28",
        "7%5%0.28",
        "5%1%0.32",
        "0%4%0.38",
        "0%2%0.26",
        "7%3%0.39",
        "1%3%0.29",
        "2%7%0.34",
        "6%2%-1.20",
        "3%6%0.52",
        "6%0%-1.4",
        "6%4%-1.25",
    };
    DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8);
    for (String _line : lines) {
      String[] split = _line.split("%");
      String v = split[0], w = split[1], weight = split[2];
      int vi = Integer.parseInt(v), vw = Integer.parseInt(w);
      ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight)));
    }

    BellmanFordShortest d = new BellmanFordShortest(ewg, 1);
    for (int i = 0; i < ewg.V(); i++) {
      Iterable<DirectedEdge> directedEdges = d.pathTo(i);
      double edgeSumWeight = 0.0;
      for (DirectedEdge directedEdge : directedEdges) {
        edgeSumWeight += directedEdge.weight();
      }
      System.out.println("1 -> " + i + ": " + directedEdges + "，sum=" + edgeSumWeight);
    }
  }

}

// 输出：
1 -> 0: [DirectedEdge{from=6, to=0, weight=-1.4}, DirectedEdge{from=3, to=6, weight=0.52}, DirectedEdge{from=1, to=3, weight=0.29}]，sum=-0.5899999999999999
1 -> 1: []，sum=0.0
1 -> 2: [DirectedEdge{from=6, to=2, weight=-1.2}, DirectedEdge{from=3, to=6, weight=0.52}, DirectedEdge{from=1, to=3, weight=0.29}]，sum=-0.38999999999999996
1 -> 3: [DirectedEdge{from=1, to=3, weight=0.29}]，sum=0.29
1 -> 4: [DirectedEdge{from=6, to=4, weight=-1.25}, DirectedEdge{from=3, to=6, weight=0.52}, DirectedEdge{from=1, to=3, weight=0.29}]，sum=-0.44
1 -> 5: [DirectedEdge{from=4, to=5, weight=0.35}, DirectedEdge{from=6, to=4, weight=-1.25}, DirectedEdge{from=3, to=6, weight=0.52}, DirectedEdge{from=1, to=3, weight=0.29}]，sum=-0.09000000000000002
1 -> 6: [DirectedEdge{from=3, to=6, weight=0.52}, DirectedEdge{from=1, to=3, weight=0.29}]，sum=0.81
1 -> 7: [DirectedEdge{from=4, to=7, weight=0.37}, DirectedEdge{from=6, to=4, weight=-1.25}, DirectedEdge{from=3, to=6, weight=0.52}, DirectedEdge{from=1, to=3, weight=0.29}]，sum=-0.07

这个算法会在放松边的时候，出现负数权重环的情况下停止运行。效率肯定是没有上面那个高，但是支持 负权重有向图 的相关问题计算。