第六部分 图算法

第二十二章 基本的图算法

​ 图的搜索指的是系统化地跟随图中的边来访问图中的每个结点。图搜索算法可以用来发现图的结构。许多的图算法在一开始都会先通过搜索来获得图的结构，其他的一些图算法则是对基本的搜索加以优化。

22.1 图的表示

对于图G = (V,E) ，可以用两种标准表示方法表示。

• 一种表示法将图作为邻接链表的组合
• 一种表示法则将图作为邻接矩阵来看待

​ 邻接链表因为在表示稀疏图（边的条数 1 趴远远小于IV 尸的图）时非常紧凑而成为通常的选择。如果G 是一个有向图，则对千边(u, V) 来说，结点v 将出现在链表Adj[u]里，因此，所有邻接链表的长度之和等于IEI 。如果G 是一个无向图，则对于边(u, V) 来说，结点v 将出现在链表Adj[u]里，结点u 将出现在链表Adj[v]里，因此，所有邻接链表的长度之和等千2IE| 。但不管是有向图还是无向图，邻接链表表示法的存储空间需求均为S(V+E)。

22.2 广度优先搜索

​ 广度优先搜索是最简单的图搜索算法之一，也是许多重要的图算法的原型。Prim 的最小生成树算法和Dijkstra 的单源最短路径算法都使用了类似广度优先搜索的思想。

​ 给定图G= (V,E) 和一个可以识别的源结点s, 广度优先搜索对图G 中的边进行系统性的探索来发现可以从源结点s 到达的所有结点。该算法能够计算从源结点s 到每个可到达的结点的距离（最少的边数），同时生成一棵＂广度优先搜索树”。该树以源结点s 为根结点，包含所有可以从s 到达的结点。对于每个从源结点s 可以到达的结点v, 在广度优先搜索树里从结点s 到结点v 的简单路径所对应的就是图G 中从结点s 到结点v 的“最短路径＂，即包含最少边数的路径。该算法既可以用千有向图，也可以用千无向图。

​ 广度优先搜索过程BFS 中，假定输入图 G=(V, E) 是以邻接链表所表示的。该算法为图中每个结点赋予了一些额外的属性：我们将每个结点u 的颜色存放在属性 u.color 里，将u 的前驱结点存放在属性u. 穴里。如果u 没有前驱结点，则u.pai = NIL。属性 u.d 记录的是广度优先搜索算法所计算出的从源结点s 到结点u 之间的距离。该算法使用一个先进先出的队列Q来管理灰色结点集。

BFS(G, s)
  for each vertex u E G. V —{s}
    u.color = WHITE
    u.d = oo
    u.pre = NIL
  s.color = GRAY
  s.d = 0
  s.pre = NIL
  Q = {}
  ENQUEUE(Q, s)
  while Q != {}
  u = DEQUEUE(Q)
  for each v in G.Adj[u]
    if v.color == WHITE
      v.color = GRAY
      v.d = u.d + 1
      v.pre = u
      ENQUEUE(Q, v)
  u.color = BLACK

Java实现

class GeneralGraph {
    static class Node {
        public int index;
        public int weight;
        public String data;
    
        // 搜索图设置属性
        public Node pre;
        public int start;
        public int finish;
        public int distance;
    
        public Node(int index, String data) {
            this.index = index;
            this.data = data;
        }
    
        @Override
        public String toString() {
            return data;
        }
    }

    private Node[] nodes;
    private List<List<int[]>> table;
    // 全局访问标志
    private int time;
    private byte[] visit;

    public GeneralGraph() {
        // 初始化一个图
        String[] data = new String[] { "r", "s", "t", "u", "v", "w", "x", "y", "z" };
        // 0 1 2 3 4 5 6 7
        // r s t u v w x y
        int[][] edge = new int[][] {
                { 0, 1, 1 },
                { 0, 4, 1 },
                { 1, 0, 1 },
                { 1, 5, 1 },
                { 2, 3, 1 },
                { 2, 5, 1 },
                { 2, 6, 1 },
                { 3, 2, 1 },
                { 3, 6, 1 },
                { 3, 7, 1 },
                { 4, 0, 1 },
                { 5, 1, 1 },
                { 5, 2, 1 },
                { 5, 6, 1 },
                { 6, 2, 1 },
                { 6, 3, 1 },
                { 6, 7, 1 },
                { 7, 3, 1 },
                { 7, 6, 1 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    public void bfs(int index) {
        // 初始化访问标志
        this.time = 0;
        Arrays.fill(this.visit, (byte) 0);

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(index);
        visit[index] = 1;
        while (!queue.isEmpty()) {
            Integer curIndex = queue.poll();
            Node node = nodes[curIndex];
            for (int[] item : table.get(curIndex)) {
                if (visit[item[0]] == 0) {
                    nodes[item[0]].pre = node;
                    nodes[item[0]].distance = node.distance + 1;
                    queue.offer(item[0]);
                    visit[item[0]] = 1;
                }
            }
            System.out.print(node.data + " " + node.distance + ", ");
        }
    }

    public static void main(String[] args) {
        GeneralGraph graph = new GeneralGraph();
        graph.bfs(1);
    }
}

分析

​ 在初始化操作结束后，广度优先搜索不会再给任何结点涂上白色，因此，第13 行的测试 if v.color == WHITE可以确保每个结点的入队次数最多为一次，因而出队最多一次。入队和出队的时间均为O(1)因此，对队列进行操作的总时间为O(V) 。因为算法只在一个结点出队的时候才对该结点的邻接链表进行扫描，所以每个邻接链表最多只扫描一次。由千所有邻接链表的长度之和是O(E), 用于扫描邻接链表的总时间为O(E) 。初始化操作的成本是O(V), 因此广度优先搜索的总运行时间为O(V+E) 。因此，广度优先搜索的运行时间是图G 的邻接链表大小的一个线性函数。

最短路径

​ 在本节开始的时候，我们曾说过，广度优先搜索能够找出从给定源结点 $s \in V$ 到所有可以到达的结点之间的距离。我们定义从源结点s 到结点v 的最短路径距离 $\delta(s,v)$ 为从结点s 到结点v之间所有路径里面最少的边数。如果从结点s 到结点v 之间没有路径，则 $\delta(s,v) = \infty$ 。我们称从结点s 到结点v 的长度为 $\delta(s,v)$ 的路径为s 到v 的最短路径。广度优先搜索可以正确计算出最短路径距离。

广度优先树

​ 过程BFS 在对图进行搜索的过程中将创建一棵广度优先树该棵树对应的是pre属性，如下所示。

​ 如果忆由从源结点s 可以到达的结点组成，并且对于所有的 $s \in V$ ，子图 $G_{\pi}$ 包含一条从源结点s 到结点v 的唯一简单路径，且该路径也是图G 里面从源结点s 到结点v 之间的一条最短路径，则前驱子图 $G_{\pi}$ 是一棵广度优先树。BFS 过程所生成的前驱子图是一棵广度优先树。

22.3 深度优先搜索

​ 在对已被发现的结点u 的邻接链表进行扫描时，每当发现一个结点v时，深度优先搜索算法将对这个事件进行记录，将v 的前驱属性v.pre设置为u 。不过，与广度优先搜索不同的是，广度优先搜索的前驱子图形成一棵树，而深度优先搜索的前驱子图可能由多棵树组成，因为搜索可能从多个源结点重复进行。

DFS(G)
  for each vertex u in G.V
    u.color = WHITE
    u.pre = NIL
  time = 0
  for each vertex u in G.V
    if u. color == WHITE
      DFS-VISIT(G, u)

DFS-VISIT(G, u)
  time = time + 1   // white vertex u has just been discovered
  u.d = time
  u.color = GRAY
  for each v in G:Adj[u]  // explore edge (u, v)
    if v.color == WHITE
      v.pre = u
      DFS-VISIT(G, v)
  u.color = BLACK     // blacken u; it is finished
  time = time + 1
  u.f = time

Java实现

class GeneralGraph {
    static class Node {
        public int index;
        public int weight;
        public String data;
    
        // 搜索图设置属性
        public Node pre;
        public int start;
        public int finish;
        public int distance;
    
        public Node(int index, String data) {
            this.index = index;
            this.data = data;
        }
    
        @Override
        public String toString() {
            return data;
        }
    }

    private Node[] nodes;
    private List<List<int[]>> table;
    // 全局访问标志
    private int time;
    private byte[] visit;

    public GeneralGraph() {
        // 初始化一个图
        String[] data = new String[] { "r", "s", "t", "u", "v", "w", "x", "y", "z" };
        // 0 1 2 3 4 5 6 7
        // r s t u v w x y
        int[][] edge = new int[][] {
                { 0, 1, 1 },
                { 0, 4, 1 },
                { 1, 0, 1 },
                { 1, 5, 1 },
                { 2, 3, 1 },
                { 2, 5, 1 },
                { 2, 6, 1 },
                { 3, 2, 1 },
                { 3, 6, 1 },
                { 3, 7, 1 },
                { 4, 0, 1 },
                { 5, 1, 1 },
                { 5, 2, 1 },
                { 5, 6, 1 },
                { 6, 2, 1 },
                { 6, 3, 1 },
                { 6, 7, 1 },
                { 7, 3, 1 },
                { 7, 6, 1 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    private void dfs(int index) {
        Node node = nodes[index];
        node.start = ++time;
        visit[index] = 2;
        System.out.printf("(%s:%02d->%02d ", node.data, node.start, node.finish);
        for (int[] item : table.get(index)) {
            if (visit[item[0]] == 0) {
                nodes[item[0]].pre = node;
                dfs(item[0]);
            }
        }
        visit[index] = 1;
        node.finish = ++time;
        System.out.printf(" %02d->%02d:%s)", node.start, node.finish, node.data);
    }

    public void dfs() {
        // 初始化访问标志
        this.time = 0;
        Arrays.fill(this.visit, (byte) 0);
        for (int i = 0; i < table.size(); i++) {
            if (visit[i] == 0) {
                dfs(i);
            }
        }
    }

    public static void main(String[] args) {
        GeneralGraph graph = new GeneralGraph();
        graph.dfs();
    }
}

分析

深度优先搜索 $v \in E$算法的运行时间为 $\Theta(V+E)$。深

深度优先搜索的性质

​ 深度优先搜索生成的前驱子图 $G_{\pi}$形成一个由多棵树所构成的森林。

​ 深度优先搜索的另一个重要性质是，结点的发现时间和完成时间具有所谓的括号化结构。如果以左括号"(u"来表示结点u 的发现，以右括号"u)"来表示结点u 的完成，则发现和完成的历史记载形成一个规整的表达式，这里”规整＂的意思是所有的括号都适当地嵌套在一起。

边的分类

对千在图G 上运行深度优先搜索算法所生成的深度优先森林 $G_\pi$，我们可以定义4 种边的类型：

1. 树边：为深度优先森林G亢中的边。如果结点v 是因算法对边(u, v) 的探索而首先被发现，则(u, v) 是一条树边。
2. 后向边：后向边(u, v) 是将结点u 连接到其在深度优先树中（一个）祖先结点v 的边。由于有向图中可以有自循环，自循环也被认为是后向边。
3. 前向边：是将结点u 连接到其在深度优先树中一个后代结点v 的边(u, v) 。
4. 横向边：指其他所有的边。这些边可以连接同一棵深度优先树中的结点，只要其中一个结点不是另外一个结点的祖先，也可以连接不同深度优先树中的两个结点。

​ 在遇到某些边时， DFS 有足够的信息来对这些边进行分类。这里的关键是，当第一次探索边(u, v) 时，结点v 的颜色能够告诉我们关千该条边的一些信息。

1. 结点v 为白色表明该条边(u, v) 是一条树边。
2. 结点v 为灰色表明该条边(u, v) 是一条后向边。
3. 结点v 为黑色表明该条边(u, v) 是一条前向边或横向边。

22.4 拓扑排序

​ 对于一个有向无环图G=(V,E) 来说，其拓扑排序是G 中所有结点的一种线性次序，该次序满足如下条件：如果图G 包含边(u, v), 则结点u 在拓扑排序中处于结点v 的前面（如果图G 包含环路，则不可能排出一个线性次序）。可以将图的拓扑排序看做是将图的所有结点在一条水平线上排开，图的所有有向边都从左指向右。

TOPOLOGICAL-SORT CG)
  call DFS(G) to compute finishing times v.f for each vertex v
  as each vertex is finished, insert it onto the front of a linked list
  return the linked list of vertices

Java实现

public class AcycliDigraph {
    static class Node {
        public int index;
        public int weight;
        public String data;
    
        // 搜索图设置属性
        public Node pre;
        public int start;
        public int finish;
        public int distance;
    
        public Node(int index, String data) {
            this.index = index;
            this.data = data;
        }
    
        @Override
        public String toString() {
            return data;
        }
    }

    private Node[] nodes;
    private List<List<int[]>> table;
    // 全局访问标志
    private int time;
    private byte[] visit;

    public AcycliDigraph() {
        // 初始化一个图
        String[] data = new String[] { "内裤", "袜子", "裤子", "鞋", "手表", "腰带", "衬衣", "领带", "夹克" };
        // 0 1 2 3 4 5 6 7 8
        int[][] edge = new int[][] {
                { 0, 2, 1 },
                { 0, 3, 1 },
                { 1, 3, 1 },
                { 2, 3, 1 },
                { 2, 5, 1 },
                { 5, 8, 1 },
                { 6, 5, 1 },
                { 6, 7, 1 },
                { 7, 8, 1 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    private void topologicalSort(int index, List<String> ans) {
        Node node = nodes[index];
        node.start = ++time;
        visit[index] = 2;
        for (int[] item : table.get(index)) {
            if (visit[item[0]] == 0) {
                nodes[item[0]].pre = node;
                topologicalSort(item[0], ans);
            }
        }
        visit[index] = 1;
        node.finish = ++time;
        ans.add(0, node.data + ":" + node.finish);
    }

    public void topologicalSort() {
        // 初始化访问标志
        this.time = 0;
        Arrays.fill(this.visit, (byte) 0);
        List<String> ans = new LinkedList<>();

        for (int i = 0; i < table.size(); i++) {
            if (visit[i] == 0) {
                topologicalSort(i, ans);
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        AcycliDigraph digraph = new AcycliDigraph();
        // 有向无环图
        digraph.topologicalSort();
    }
}

分析

​ 我们可以在 $\Theta(V+E)$ 的时间内完成拓扑排序，因为深度优先搜索算法的运行时间为 $\Theta(V+E)$, 将结点插入到链表最前端所需的时间为 $O(1)$ 而一共只有 $|V|$ 个结点需要插入。

示例

22.5 强连通分量

​ 有向图G= (V,E) 的强连通分量是一个最大结点集合 $C \subseteq V$. 对于该集合中的任意一对结点u 和v 来说，路径 $ u \leadsto v$和路径 $ v \leadsto u$ 同时存在，即结点u和结点v 可以互相到达。

​ 寻找强连通分量的算法需要用到图G=(V, E) 的转置，在练习22. 1-3 中将其定义为 $G^T=(V,E^T)$这里 $E^T={(u, v): (v, u) \in E}$ 。也就是说，$E^T$由对图G 中的边进行反向而获得。给定图G 的邻接链表，创建 $G^T$ 的时间为O(V+E) 。有趣的是，图G 和图 $G^T$ 的强连通分量完全相同： u 和v 在图G 中可以相互到达当且仅当它们在图 $G^T$ 中可以相互到达。

​ 下面的线性时间（即 $\Theta(V+E)$ 时间）算法使用两次深度优先搜索来计算有向图 G= (V,E) 的强连通分量。这两次深度优先搜索一次运行在图G 上，一次运行在转置图 $G^T$ 上。

STRONGLY-CONNECTED-COMPONENTS(G)
  call DFS (G) to compute finishing times u.f for each vertex u
  compute G^T
  call DFS(G^T)， but in the main loop of DFS, consider the verticesin order of decreasing u. f (as computed in line 1)
  output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component

Java实现

public class ConnectedGraph {
    static class Node {
        public int index;
        public int weight;
        public String data;
    
        // 搜索图设置属性
        public Node pre;
        public int start;
        public int finish;
        public int distance;
    
        public Node(int index, String data) {
            this.index = index;
            this.data = data;
        }
    
        @Override
        public String toString() {
            return data;
        }
    }

    private Node[] nodes;
    private List<List<int[]>> table;
    // 全局访问标志
    private int time;
    private byte[] visit;

    public ConnectedGraph() {
        // 初始化一个图
        String[] data = new String[] { "a", "b", "c", "d", "e", "f", "g", "h" };
        // 0 1 2 3 4 5 6 7
        // a b c d e f g h
        int[][] edge = new int[][] {
                { 0, 1, 1 },
                { 1, 2, 1 },
                { 1, 4, 1 },
                { 1, 5, 1 },
                { 2, 3, 1 },
                { 2, 6, 1 },
                { 3, 2, 1 },
                { 3, 7, 1 },
                { 4, 0, 1 },
                { 4, 5, 1 },
                { 5, 6, 1 },
                { 6, 5, 1 },
                { 6, 7, 1 },
                { 7, 7, 1 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    public ConnectedGraph transposeGraph() {
        ConnectedGraph graph = new ConnectedGraph();
        // 节点
        for (int i = 0; i < nodes.length; i++) {
            graph.nodes[i].pre = nodes[i].pre;
            graph.nodes[i].start = nodes[i].start;
            graph.nodes[i].finish = nodes[i].finish;
        }
        // 边
        for (int i = 0; i < table.size(); i++) {
            graph.table.get(i).clear();
        }
        for (int i = 0; i < table.size(); i++) {
            for (int[] item : table.get(i)) {
                graph.table.get(item[0]).add(new int[] { i, item[1] });
            }
        }
        return graph;
    }

    private void dfs(int index, List<Node> ans) {
        Node node = nodes[index];
        node.start = ++time;
        visit[index] = 2;
        ans.add(node);
        for (int[] item : table.get(index)) {
            if (visit[item[0]] == 0) {
                nodes[item[0]].pre = node;
                dfs(item[0], ans);
            }
        }
        visit[index] = 1;
        node.finish = ++time;
    }

    private void dfs() {
        // 初始化访问标志
        this.time = 0;
        Arrays.fill(this.visit, (byte) 0);

        for (int i = 0; i < table.size(); i++) {
            if (visit[i] == 0) {
                List<Node> ans = new ArrayList<>();
                dfs(i, ans);
            }
        }
    }

    private void dfsFinish() {
        // 初始化访问标志
        this.time = 0;
        Arrays.fill(this.visit, (byte) 0);

        Queue<Node> queue = new PriorityQueue<>((o1, o2) -> o2.finish - o1.finish);
        for (Node node : nodes) {
            queue.add(node);
        }
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (visit[node.index] == 0) {
                List<Node> ans = new ArrayList<>();
                dfs(node.index, ans);
                System.out.println(ans);
            }
        }
    }

    public void stronglyConnected() {
        dfs();
        ConnectedGraph graph = transposeGraph();
        graph.dfsFinish();
    }

    public static void main(String[] args) {
        ConnectedGraph graph = new ConnectedGraph();
        // 有向无环图
        graph.stronglyConnected();
    }
}

示例

第二十三章 最小生成树

​ 连通无向图 G=(V, E) ，这里的V 是结点集合， E 是边，并且对于每条边 $(u, v) \in E$, 我们为其赋予权重 w(u, v) 作为连接结点u,v 的代价。我们希望找到一个无环子集 $T \subseteq E$, 既能够将所有的结点连接起来，又具有最小的权重，即$w(T) = \mathop{\sum}_{(u,v) \in T} w(u, v)$ 的值最小。由于T(u,v)ET是无环的，并且连通所有的结点，因此， T 必然是一棵树。我们称这样的树为（图G 的）生成树，因为它是由图G 所生成的。我们称求取该生成树的问题为最小生成树问题。

23.1 最小生成树的形成

​ 本章所讨论的两种算法都使用贪心策略来解决这个问题，但它们使用贪心策略的方式却有所不同。

​ 这个贪心策略可以由下面的通用方法来表述。该通用方法在每个时刻生长最小生成树的一条边，并在整个策略的实施过程中，管理一个遵守下述循环不变式的边集合A：在每遍循环之前， A 是某棵最小生成树的一个子集。

​ 在每一步，我们要做的事情是选择一条边(u, v), 将其加入到集合A 中，使得A 不违反循环不变式，即$A \cup \{(u, v)\}$ 也是某棵最小生成树的子集。由千我们可以安全地将这种边加入到集合A 而不会破坏A 的循环不变式，因此称这样的边为集合A 的安全边。

GENERIC-MST(G,w)
 A = {}
 while A does not form a spanning tree
   find an edge(u, v) that is safe for A
   A = A 并 {(u,v)}
 return A

23.2 Kruskal 算法和Prim 算法

Kruskal 算法

​ Kruskal 算法找到安全边的办法是，在所有连接森林中两棵不同树的边里面，找到权重最小的边 (u, v) 。设 $C_1$ 和 $C_2$ 为边(u, v) 所连接的两棵树。由于边(u, v) 一定是连接 $C_1$ 和其他某棵树的一条轻量级边，边(u, v) 是 $C_1$ 的一条安全边。很显然， Kruskal算法属于贪心算法，因为它每次都选择一条权重最小的边加入到森林。

​ 我们使用一个不相交集合数据结构来维护几个互不相交的元素集合。每个集合代表当前森林中的一棵树。操作 FIND-SET(u) 用来返回包含元素u 的集合的代表元素。我们可以通过测试 FIND-SET (u) 是否等于 FIND-SET(v) 来判断结点u 和结点v 是否属于同一棵树。Kruskal 算法使用UNION 过程来对两棵树进行合并。

MST-KRUSKALCG,w)
  A = {}
  for each vertex v 属于 G.V
    MakE-SET(v)
  sort the edges of G.E into nondecreasing order by weight w
  for each edge(u,v) 包含于 G.E, taken in nondecreasing order by weight
    if FIND-SET(v) != FIND-SET(v)
      A = A 并 {(u,v)}
      UNION(u,v)
  return A

Java实现

public class TreeGraph {
    static class Node {
        public int index;
        public int weight;
        public String data;
    
        // 搜索图设置属性
        public Node pre;
        public int start;
        public int finish;
        public int distance;
    
        public Node(int index, String data) {
            this.index = index;
            this.data = data;
        }
    
        @Override
        public String toString() {
            return data;
        }
    }
    
    private Node[] nodes;
    private List<List<int[]>> table;

    public TreeGraph() {
        // 初始化一个图
        String[] data = new String[] { "a", "b", "c", "d", "e", "f", "g", "h", "i" };
        // 0 1 2 3 4 5 6 7 8
        // a b c d e f g h i
        int[][] edge = new int[][] {
                { 0, 1, 4 },
                { 0, 7, 8 },
                { 1, 0, 4 },
                { 1, 2, 8 },
                { 1, 7, 11 },
                { 2, 1, 8 },
                { 2, 3, 7 },
                { 2, 5, 4 },
                { 2, 8, 2 },
                { 3, 2, 7 },
                { 3, 4, 9 },
                { 3, 5, 14 },
                { 4, 3, 9 },
                { 4, 5, 10 },
                { 5, 2, 4 },
                { 5, 3, 14 },
                { 5, 4, 10 },
                { 5, 6, 2 },
                { 6, 5, 2 },
                { 6, 7, 1 },
                { 6, 8, 6 },
                { 7, 0, 8 },
                { 7, 1, 11 },
                { 7, 6, 1 },
                { 7, 8, 7 },
                { 8, 2, 2 },
                { 8, 6, 6 },
                { 8, 7, 7 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    private int findRoot(Map<Integer, Integer> map, int index) {
        int root = index;
        while (map.get(root) != root) {
            root = map.get(root);
        }
        return root;
    }

    public void kruskal(int index) {
        // 1.初始化并查集
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nodes.length; i++) {
            map.put(i, i);
        }
        // 2.初始化最小生成树
        List<int[]> tree = new ArrayList<>();
        // 3.初始化边集
        Queue<int[]> edges = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        for (int i = 0; i < table.size(); i++) {
            for (int[] item : table.get(i)) {
                edges.add(new int[] { i, item[0], item[1] });
            }
        }
        // 4.遍历边集
        while (!edges.isEmpty()) {
            int[] edge = edges.poll();
            int root1 = findRoot(map, edge[0]);
            int root2 = findRoot(map, edge[1]);
            if (root1 != root2) {
                tree.add(edge);
                map.put(root1, root2);
            }
        }
        // 5.输出最小生成树
        for (int[] item : tree) {
            System.out.println(nodes[item[0]].data + " -> " + nodes[item[1]].data + " : " + item[2]);
        }
    }

    public static void main(String[] args) {
        TreeGraph graph = new TreeGraph();
        graph.kruskal(2);
    }
}

分析

​ 对千图G= (V, E) , Kruskal 算法的运行时间依赖于不相交集合数据结构的实现方式。假定使用不相交集合森林实现，并增加按秩合并和路径压缩的功能，因为这是目前已知的渐近时间最快的实现方式。在这种实现模式下，Kruskal 算法的时间可表示为 $O(E\:lgV)$ 。

示例

Prim 算法

​ Prim 算法所具有的一个性质是集合A 中的边总是构成一棵树。这棵树从一个任意的根结点r 开始，一直长大到覆盖V 中的所有结点时为止。算法每一步在连接集合A 和A 之外的结点的所有边中，选择一条轻量级边加入到A 中。根据推论23.2, 这条规则所加入的边都是对A 安全的边。因此，当算法终止时， A 中的边形成一棵最小生成树。本策略也属于贪心策略，因为每一步所加入的边都必须是使树的总权重增加量最小的边。

​ 为了有效地实现 Prim 算法，需要一种快速的方法来选择一条新的边，以便加入到由集合A中的边所构成的树里。在下面的伪代码中，连通图G 和最小生成树的根结点r 将作为算法的输入。在算法的执行过程中，所有不在树A 中的结点都存放在一个基千key 属性的最小优先队列Q中。对千每个结点v, 属性 v.key 保存的是连接v 和树中结点的所有边中最小边的权重。我们约定，如果不存在这样的边，则 $v.key= \infty$。属性v. 穴给出的是结点v 在树中的父结点。Prim 算法将 GENERIC-MST 中的集合A 维持在 $A={(v,v.pre):v \in V-\{r\} -Q}$ 的状态下。

​ 当Prim 算法终止时，最小优先队列Q 将为空，而G 的最小生成树A 则是： $A={(v,v.pre):v \in V-\{r\}}$

MST-PRIM(G,w,r)
  for each u 属于 G.V
    u:key = oo
    u:pre =NIL
  r:key = 0
  Q = G.V
  while Q != {}
    u = EXTRACT-MIN(Q)
    for each v 属于 G.Adj[u]
    if v 属于 Q and w(u,v) < v.key
      v.pre = u
      v.key = w(u,v)

Java实现

public class TreeGraph {
    static class Node {
        public int index;
        public int weight;
        public String data;
    
        // 搜索图设置属性
        public Node pre;
        public int start;
        public int finish;
        public int distance;
    
        public Node(int index, String data) {
            this.index = index;
            this.data = data;
        }
    
        @Override
        public String toString() {
            return data;
        }
    }
    
    private Node[] nodes;
    private List<List<int[]>> table;

    public TreeGraph() {
        // 初始化一个图
        String[] data = new String[] { "a", "b", "c", "d", "e", "f", "g", "h", "i" };
        // 0 1 2 3 4 5 6 7 8
        // a b c d e f g h i
        int[][] edge = new int[][] {
                { 0, 1, 4 },
                { 0, 7, 8 },
                { 1, 0, 4 },
                { 1, 2, 8 },
                { 1, 7, 11 },
                { 2, 1, 8 },
                { 2, 3, 7 },
                { 2, 5, 4 },
                { 2, 8, 2 },
                { 3, 2, 7 },
                { 3, 4, 9 },
                { 3, 5, 14 },
                { 4, 3, 9 },
                { 4, 5, 10 },
                { 5, 2, 4 },
                { 5, 3, 14 },
                { 5, 4, 10 },
                { 5, 6, 2 },
                { 6, 5, 2 },
                { 6, 7, 1 },
                { 6, 8, 6 },
                { 7, 0, 8 },
                { 7, 1, 11 },
                { 7, 6, 1 },
                { 7, 8, 7 },
                { 8, 2, 2 },
                { 8, 6, 6 },
                { 8, 7, 7 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    public void prim(int index) {
        List<int[]> tree = new ArrayList<>();

        Set<Integer> set = new HashSet<>();
        set.add(index);
        Queue<int[]> edges = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        for (int[] item : table.get(index)) {
            edges.add(new int[] { index, item[0], item[1] });
        }
        while (set.size() < nodes.length) {
            int[] edge = edges.poll();
            if (!set.contains(edge[1])) {
                tree.add(edge);
                set.add(edge[1]);
                for (int[] item : table.get(edge[1])) {
                    edges.add(new int[] { edge[1], item[0], item[1] });
                }
            }
        }
        // 输出最小生成树
        for (int[] item : tree) {
            System.out.println(nodes[item[0]].data + " -> " + nodes[item[1]].data + " : " + item[2]);
        }
    }

    public static void main(String[] args) {
        TreeGraph graph = new TreeGraph();
        graph.prim(2);
    }
}

分析

​ Prim 算法的运行时间取决于最小优先队列Q 的实现方式。Prim 算法的总时间代价为 $O(V\:lgV + E\:lgV) =O(E\:lg V)$ 。从渐近意义上来说，它与Kruskal算法的运行时间相同。

示例

第二十四章 单源最短路径

​ 在最短路径问题中, 我们给定 一个带权重的有向图 G=(V, E) 和权重函数 $w: E \rightarrow \mathbf{R}$ , 该权重函数将每条边映射到实数值的权 重上。图中一条路径 $p=\left\langle v_{0}, v_{1}, \cdots, v_{k}\right\rangle$ 的权重 w§ 是构成该路径的所有边的权重之和:

$$w(p)=\sum_{i=1}^{k} w\left(v_{i-1}, v_{i}\right)$$

定义从结点 u 到结点 v 的最短路径权重 $\delta(u, v)$ 如下:

$$\delta(u, v)=\left\{\begin{array}{ll} \min \left\{w(p): u^{p} \rightarrow v\right\} & \text { 如果存在一条从结点 } u \text { 到结点 } v \text { 的路径 } \\ \infty & \text { 其他 } \end{array}\right.$$

从结点 u 到结点 v 的最短路径则定义为任何一条权重为 $w(p)=\delta(u, v)$ 的从 u 到 v 的路径 p 。

最短路径的几个变体

​ 单源最短路径问题：给定一个图G=(V, E), 我们希望找到从给定源结点 $s \in V$ 到每个结点 $v \in V$ 的最短路径。单源最短路径问题可以用来解决许多其他问题，其中就包括下面的儿个最短路径的变体问题。

• 单目的地最短路径问题：找到从每个结点v 到给定目的地结点t 的最短路径。如果将图的诲条边的方向翻转过来，我们就可以将这个问题转换为单源最短路径问题。

• 单结点对最短路径问题：找到从给定结点u 到给定结点v 的最短路径。如果解决了针对单个结点u 的单源最短路径问题，那么也就解决了这个问题。而且，在该问题的所有已知算法中，最坏情况下的渐近运行时间都和最好的单源最短路径算法的运行时间一样。

• 所有结点对最短路径问题：对于每对结点u 和v, 找到从结点u 到结点v 的最短路径。虽然可以针对每个结点运行一遍单源最短路径算法，但通常可以更快地解决这个问题。

负权重的边

​ 某些单源最短路径问题可能包括权重为负值的边。但如果图 G=(V, E) 不包含从源结点s 可以到达的权重为负值的环路，则对于所有的结点$v \in V$, 最短路径权重$\delta(s, v)$ 都有精确定义，即使其取值是负数。如果图G 包含从s 可以达到的权重为负值的环路，则最短路径权重无定义。从s 到该环路上的任意结点的路径都不可能是最短路径，因为我们只要沿着任何“最短“路径再遍历一次权重为负值的环路，则总是可以找到一条权重更小的路径。如果从结点s 到结点v 的某条路径上存在权重为负值的环路，我们定义 $\delta(s, v) = - \infty$ 。

​ 某些最短路径算法（如Dijkstra 算法）假设输入图的所有的边权重为非负值。另外一些算法（如Bellman-Ford 算法），允许输入图中包含负权重的边。但只要没有可以从源结点到达的权重为负值的环路，就可以生成正确的答案。在通常情况下，如果存在一条权重为负值的环路， Bellman-Ford 算法可以侦测并报告其存在。

环路

​ 最短路径也不能包含权重为正值的环路，因为只要将环路从路径上删除就可以得到一条源结点和终结点与原来路径相同的一条权重更小的路径。

最短路径的表示

​ 我们不但希望计算出最短路径权重，还希望计算出最短路径上的结点。给定图 G=(V, E), 对千每个结点v, 我们维持一个前驱结点v.pre。该前驱结点可能是另一个结点或者NIL。本章的最短路径算法将对每个结点的兀属性进行设置，这样，将从结点v 开始的前驱结点链反转过来，就是从s 到v 的一条最短路径。

松弛操作

​ 对于每个结点v 来说，我们维持一个属性 v.d ,用来记录从源结点s 到结点v 的最短路径权重的上界。我们称v.d 为s 到v 的最短路径估计。我们使用下面运行时间为 $\Theta(V)$ 的算法来对最短路径估计和前驱结点进行初始化：

INITIALIZE-SINGLE-SOURCE(G, s)
  for each vertex v 属于 G. V
    v.d = oo
    v.pre = NIL
  s.d = 0

​ 对一条边的(u, v) 的松弛过程为：首先测试一下是否可以对从s 到v 的最短路径进行改善。测试的方法是，将从结点s 到结点u 之间的最短路径距离加上结点u 与v 之间的边权重，并与当前的s 到v 的最短路径估计进行比较，如果前者更小，则对 v.d 和v.pre进行更新。松弛步骤可能降低最短路径的估计值v.d 并更新 v 的前驱属性v.pre 。下面的伪代码执行的就是对边(u, v) 在O(1) 时间内进行的松弛操作：

RELAX(u,v,w)
 if v.d > u.d + w(u,v)
   v.d = u.d + w(u,v)
   v.pre = u

24.1 Bellman-Ford 算法

​ Bellman-Ford 算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。给定带权重的有向图 G=(V, E) 和权重函数 w: E-R, Bellman-Ford 算法返回一个布尔值，以表明是否存在一个从源结点可以到达的权重为负值的环路。如果存在这样一个环路，算法将告诉我们不存在解决方案。如果没有这种环路存在，算法将给出最短路径和它们的权重。

​ Bellman-Ford 算法通过对边进行松弛操作来渐近地降低从源结点s 到每个结点v 的最短路径的估计值 v.d, 直到该估计值与实际的最短路径权重 $\delta(s, v)$ 相同时为止。该算法返回TRUE 值当且仅当输入图不包含可以从源结点到达的权重为负值的环路。

​ 经过数学证明，在没有负权回路存在的情况下，所有边最多进行n-1次松弛操作。如果进行n次迭代，则最短路要经过n条边，则必有两个点是重复的，则一定存在环路，并且是负环。当负权存在时，连最短路都不一定存在了。如果最短路存在，一定存在一个不含环的最短路。因为在边权可正可负的图中，环有零环、正环和负环3种。如果包含零环或正环，去掉以后路径不会变长；如果包含负环，则意味着最短路不存在

BELLMAN-FORD(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G,s)
  for i=1 to |G.V| - 1
    for each edge(u,v) 属于 G.E
      RELAX(u,v,w)
  for each edge(u,v) 属于 G.E
    if v.d > u.d + w(u.v)
      return FALSE
  return TRUE

Java实现

public class ShortestPath {
    static class Node {
        public char data;
        public int weight;

        // 搜索图设置属性
        public Node pre;
        public int distance;

        public Node(char data) {
            this.data = data;
        }
    }

    private Node[] nodes;
    private List<List<int[]>> table;

    public ShortestPath() {
        // 初始化一个图
        char[] data = new char[] { 's', 't', 'x', 'y', 'z' };
        // 0 1 2 3 4
        // s t x y z
        int[][] edge = new int[][] {
                { 0, 1, 6 },
                { 0, 3, 7 },
                { 1, 2, 5 },
                { 1, 3, 8 },
                { 1, 4, -4 },
                { 2, 1, -2 },
                { 3, 2, -3 },
                { 3, 4, 9 },
                { 4, 0, 2 },
                { 4, 2, 7 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    public void bellmanFord(int index) {
        // 初始化
        for (Node node : nodes) {
            node.distance = Integer.MAX_VALUE;
            node.pre = null;
        }
        nodes[index].distance = 0;
        // 迭代
        for (int i = 0; i < nodes.length; i++) {
            // 遍历节点
            for (int j = 0; j < nodes.length; j++) {
                for (int[] item : table.get(j)) {
                    if (nodes[j].distance + item[1] < nodes[item[0]].distance) {
                        nodes[item[0]].distance = nodes[j].distance + item[1];
                        nodes[item[0]].pre = nodes[j];
                    }
                }
            }
        }

        for (int j = 0; j < nodes.length; j++) {
            for (int[] item : table.get(j)) {
                if (nodes[j].distance + item[1] < nodes[item[0]].distance) {
                    System.out.println("存在负环");
                    return;
                }
            }
        }

        // 输出
        for (Node node : nodes) {
            System.out.print(node.data + " " + node.distance + ": ");
            Node p = node;
            while (p.pre != null) {
                System.out.print(p.data + " <- ");
                p = p.pre;
            }
            System.out.println(p.data);
        }
    }

    public static void main(String[] args) {
        ShortestPath shortestPath = new ShortestPath();
        shortestPath.bellmanFord(0);
    }
}

分析

​ Bellman-Ford 算法的总运行时间为O(VE) 。

示例

24.2 有向无环图中的单源最短路径问题

​ 根据结点的拓扑排序次序来对带权重的有向无环图 $G=(V, E)$ 进行边的松弛操作，我们便可以在 $\Theta(V+E)$ 时间内计算出从单个源结点到所有结点之间的最短路径。在有向无环图中，即使存在权重为负值的边，但因为没有权重为负值的环路，最短路径都是存在的。

​ 我们的算法先对有向无环图进行拓扑排序，以便确定结点之间的一个线性次序。如果有向无环图包含从结点u 到结点v 的一条路径，则u 在拓扑排序的次序中位千结点v的前面。我们只需要按照拓扑排序的次序对结点进行一遍处理即可。每次对一个结点进行处理时，我们对从该结点发出的所有的边进行松弛操作。

DAG-SHORTEST-PATHS(G,w,s)
  topologically sort the vertices of G
  INITIALIZE-SINGLE-SOURCE(G, s)
  for each vertex u, taken in topologically sorted order
    for each vertex v 属于 G.Adj[u]
      RELAX(u,v,w)

Java实现

public class AcycliShortestGraph {
    private Node[] nodes;
    private List<List<int[]>> table;
    // 全局访问标志
    private int time;
    private byte[] visit;

    public AcycliShortestGraph() {
        // 初始化一个图
        String[] data = new String[] { "r", "s", "t", "x", "y", "z" };
        // 0 1 2 3 4 5
        // r s t x y z
        int[][] edge = new int[][] {
                { 0, 1, 5 },
                { 0, 2, 3 },
                { 1, 3, 6 },
                { 1, 2, 2 },
                { 2, 4, 4 },
                { 2, 5, 2 },
                { 2, 3, 7 },
                { 3, 5, 1 },
                { 3, 4, -1 },
                { 4, 5, -2 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    private void topologicalSort(int index, List<Node> ans) {
        Node node = nodes[index];
        node.start = ++time;
        visit[index] = 2;
        for (int[] item : table.get(index)) {
            if (visit[item[0]] == 0) {
                nodes[item[0]].pre = node;
                topologicalSort(item[0], ans);
            }
        }
        visit[index] = 1;
        node.finish = ++time;
        ans.add(0, node);
    }

    private List<Node> topologicalSort() {
        // 初始化访问标志
        this.time = 0;
        Arrays.fill(this.visit, (byte) 0);
        List<Node> ans = new LinkedList<>();

        for (int i = 0; i < table.size(); i++) {
            if (visit[i] == 0) {
                topologicalSort(i, ans);
            }
        }
        return ans;
    }

    public void dagShortestPath(int index) {
        List<Node> topSort = topologicalSort();
        // 初始化
        for (Node node : nodes) {
            node.distance = Integer.MAX_VALUE;
            node.pre = null;
        }
        nodes[index].distance = 0;
        for (Node node : topSort) {
            if(node.distance == Integer.MAX_VALUE){
                continue;
            }
            for (int[] item : table.get(node.index)) {
                if (node.distance + item[1] < nodes[item[0]].distance) {
                    nodes[item[0]].distance = node.distance + item[1];
                    nodes[item[0]].pre = node;
                }
            }
        }

        // 输出
        for (Node node : nodes) {
            System.out.print(node.data + " " + node.distance + ": ");
            Node p = node;
            while (p.pre != null) {
                System.out.print(p.data + " <- ");
                p = p.pre;
            }
            System.out.println(p.data);
        }
    }

    public static void main(String[] args) {
        AcycliShortestGraph graph = new AcycliShortestGraph();
        graph.dagShortestPath(1);
    }
}

分析

​ 算法的总运行时间为 $\Theta(V+E)$ ， 即对于以邻接链表法表示的图来说，这个时间为线性级。

示例

24.3 Dijkstra 算法

​ Dijkstra 算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。因此，在本节的讨论中，我们假定对于所有的边 $(u, v) \in E$, 都有 $w(u, v) \ge 0$ 。我们稍后将看到，如果所采用的实现方式合适， Dijkstra 算法的运行时间要低千Bellman-Ford 算法的运行时间。

​ Dijkstra 算法在运行过程中维持的关键信息是一组结点集合S。从源结点s 到该集合中每个结点之间的最短路径已经被找到。算法重复从结点集 $V-S$ 中选择最短路径估计最小的结点u,将u 加入到集合S, 然后对所有从u 发出的边进行松弛。在下面给出的实现方式中，我们使用一个最小优先队列 Q 来保存结点集合，每个结点的关键值为其d 值。

DUKSTRA (G,w,s)
  INITIALIZE-SINGLE-SOURCE(G, s)
  S = {}
  Q = G.V
  while Q != {}
    u = EXTRACT-MIN(Q)
    S = S 并 {u}
    for each vertex v 属于 G.Adj[u]
      RELAX(u,v,w)

JAVA实现

public class DijkstraShortestGraph {
    private Node[] nodes;
    private List<List<int[]>> table;

    public DijkstraShortestGraph() {
        // 初始化一个图
        String[] data = new String[] { "s", "t", "x", "y", "z" };
        // 0 1 2 3 4
        // s t x y z
        int[][] edge = new int[][] {
                { 0, 1, 10 },
                { 0, 3, 5 },
                { 1, 2, 1 },
                { 1, 3, 2 },
                { 2, 4, 4 },
                { 3, 1, 3 },
                { 3, 2, 9 },
                { 3, 4, 2 },
                { 4, 0, 7 },
                { 4, 2, 6 }
        };
        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
        // 其他
        time = 0;
        visit = new byte[data.length];
    }

    public void dijkstra(int index) {
        // 初始化
        for (Node node : nodes) {
            node.distance = Integer.MAX_VALUE / 2 - 1;
            node.pre = null;
        }
        nodes[index].distance = 0;
        Queue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.distance - o2.distance);
        queue.add(nodes[index]);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (int[] item : table.get(node.index)) {
                if (node.distance + item[1] < nodes[item[0]].distance) {
                    nodes[item[0]].distance = node.distance + item[1];
                    nodes[item[0]].pre = node;
                    // 放入下一层
                    queue.add(nodes[item[0]]);
                }
            }
        }

        // 输出
        for (Node node : nodes) {
            System.out.print(node.data + " " + node.distance + ": ");
            Node p = node;
            while (p.pre != null) {
                System.out.print(p.data + " <- ");
                p = p.pre;
            }
            System.out.println(p.data);
        }
    }

    public static void main(String[] args) {
        DijkstraShortestGraph graph = new DijkstraShortestGraph();
        graph.dijkstra(0);
    }
}

分析

​ Dijkstra 算法的总运行时间依赖于最小优先队列的实现。

​ 若通过利用结点的编号为 $1~|V|$ 来维持最小优先队列。算法的总运行时间为 $O(V^2+E)=O(V^2)$ 。

​ 可以使用二叉堆来实现最小优先队列，从而改善算法的运行时间。算法的总运行时间为 $O((V+E) : lgV) $。若所有结点都可以从源结点到达，则该时间为 $O(E : lgV) $。若 $E=o(V^2 /lgV)$,则该时间成本相对于直接实现的 $O(V^2)$ 成本有所改善。

示例

24.4 差分约束和最短路径

​ 可以使用 Bellman-Ford 算法来求解差分约束系统。因为约束图包含从源结点力。到所有其他结点的边，任何权重为负值的环路都可以从结点v。到达。如果 BellmanFord 算法返回TRUE 值，则最短路径权重给出的是该系统的一个可行解。如果Bellman-Ford 算法返回FALSE 值，则差分约束系统没有可行解。

​ 一个有n 个未知变量和m 个约束条件的差分约束系统所生成的约束图有 n+1 个结点和 n+m 条边。因此，使用Bellman-Ford 算法，我们可以在 $O((n+1)(n十m))=O(n^2+nm)$ 时间内求解该系统 。

第二十五章 所有结点对的最短路径问题

​ 我们给定的是一个带权重的有向图G=(V, E), 其权重函数为W: E-R, 该函数将边映射到实数值的权重上。我们希望找到，对于所
有的结点对u, vEV, 一条从结点u 到结点v 的最短路径，其中一条路径的权重为组成该路径的所有边的权重之和。我们通常希望以表格的形式来表示输出：第u 行第v 列给出的是结点u 到结点v 的最短路径权重。

​ 本章的多数算法使用邻接矩阵来表示图（25. 3 节稀疏图的 Johnson 算法使用的是邻接链表）。假定 结点的编号为 $1,2, \cdots,|V|$ , 因此, 算法的输人将是一个 $n \times n$ 的矩阵 W , 该矩阵代表的是一 个有 n 个结点的有向图 $G=(V, E)$ 的边的权重。即 $W=\left(w_{i j}\right) $ 其中

$$w_{i j}=\left\{\begin{array}{ll} 0 & \text { 若 } i=j \\ \text { 有向边 }(i, j) \text { 的权重 } & \text { 若 } i \neq j \text { 且 }(i, j) \in E \\ \infty & \text { 若 } i \neq j \text { 且 }(i, j) \notin E \end{array}\right.$$

我们允许存在负权重的边, 但目前仍然先假定图中不包括权重为负值的环路。

​ 为了解决所有结点对最短路径问题, 我们不仅需要计算出最短路径权重, 还需要计算出前 驱结点矩阵 $\Pi=\left(\pi_{i j}\right)$ , 其中 $\pi_{i j}$ 在 i=j 或从 i 到 j 不存在路径时为 NIL，在其他情况下给出的是从 结点 i 到结点 j 的某条最短路径上结点 j 的前驱结点。

​ 在开始前, 我们需要给出邻接矩阵表示的一些约定。首先, 假定输人图 G=(V, E) 有 n 个 结点, 因此, $n=|V|$ 。其次, 使用大写字母来表示矩阵, 如 W 、 L 或 D , 而用带下标的小写字 母来表示矩阵中的个体元素, 如 $w_{i j}$ 、$ l_{i j}$ 或 $d_{i j}$ 。一些矩阵将有带括号的上标, 如 $ L^ {(m)}=\left(l_{i j}^ {(m)}\right)$ 或 $D^ {(m)}=\left(d_{i j}^ {(m)}\right)$ , 用来表示迭代。最后, 对于一个给定的 $n \times n$ 矩阵 A , 假定矩阵的维度 n 存储在属 性 A.rows 中。

25.1 最短路径和矩阵乘法

最短路径的结构

​ 对于图 G=(V, E) 的所有结点对最短路径问题, 一条最短路径的所有子路径都是最短路径。假定用邻接矩阵来表示输人图。即 $W=\left(w_{i j}\right)$ 。考虑从结点 i 到结点 j 的一条最短路径 p , 假定 p 至多包含 m 条边, 还假定没有权 重为负值的环路, 且 m 为有限值。如果 $i=j$ , 则 p 的权重为 0 且不包含任何边。如果结点 i 和结 点 j 不同, 则将路径 p 分解为 $i \overset{p'}{\leadsto} k \rightarrow j$ , 其中路径 $p^{\prime}$ 至多包含 m-1 条边。则$p^{\prime}$ 是 从结点 i 到结点 k 的一条最短路径, 因此, $\delta(i, j)=\delta(i, k)+w_{k j}$ 。

所有结点对最短路径问题的递归解

​ 现在设 $l_{i j}^{(m)}$ 为从结点 i 到结点 j 的至多包含 m 条边的任意路径中的最小权重。当 m=0 时，从结点 i 到结点 j 之间存在一条没有边的最短路径当且仅当 i=j 。因此,

$$l_{i j}^{(m)}=\left\{\begin{array}{ll} 0 & \text { 如果 } i=j \\ \infty & \text { 如果 } i \neq j \end{array}\right.$$

对于 $m \geqslant 1$ , 我们需要计算的 $l_{i j}^{(m)} $ 是 $l_{i j}^{(m-1)}$ (从 i 到 j 最多由 m-1 条边组成的最短路径的权重) 的最 小值和从 i 到 j 最多由 m 条边组成的任意路径的最小权重, 我们通过对 j 的所有可能前驱 k 进行 检查来获得该值。因此递归定义

$$l_{i j}^{(m)}=\min \left(l_{i j}^{(m-1)}, \min _{1 \leqslant k \leqslant n}\left\{l_{i k}^{(m-1)}+w_{k j}\right\}\right)=\min _{1 \leqslant k \leqslant n}\left\{l_{i k}^{(m-1)}+w_{k j}\right\}$$

因为对于所有的 j 有 $w_{j j}=0$ , 所以上述式子中后面的等式成立。

​ 如果图 G 不包含权重为负值的环路, 则对于 每一对结点 i 和 j , 如果 $\delta(i, j)<\infty$ , 从 i 到 j 之间存在一条最短路径。由于该路径是简单路径, 其包含的边最多为 n-1 条。从结点 i 到结点 j 的由多于 n-1 条边构成的路径不可能有比从 i 到 j 的最短路径权重更小的权重。因此, 真正的最短路径权重可以由下面的公式给出:

$$\delta(i, j)=l_{i j}^{(n-1)}=l_{i j}^{(n)}=l_{i j}^{(n+1)}=\cdots$$

自底向上计算最短路径权重

​ 根据输人矩阵 $W=\left(w_{i j}\right)$ , 现在可以计算出矩阵序列 $L^{(1)}, L^{(2)}, \cdots, L^{(n-1)}$ , 其中对于 $m= 1,2, \cdots, n-1$ , 有 $L^{(m)}=\left(l_{i j}^{(m)}\right)$ 。最后的矩阵 $L^{(n-1)}$ 包含的是最短路径的实际权重。注意, 对于 所有的结点 i 和 j, $L^{(1)}=\left(w_{i j}\right)$ , 因此, $L^{(1)}=W$ 。该算法的核心如下面的伪代码程序所示。该伪代码程序可以在给定 W 和 $L^{(m-1)}$ 的情况下, 计算出 $L^{(m)}$ 。也就是说, 该伪代码将最近计算出的最短路径扩展了一条边。

EXTEND-SHORTEST-PATHS(L, W)
  n = L.rows
  let L' = (l'(ij)) be a new nXn matrix
  for i = 1 to n
    for j = 1 to n
    l'(ij) = oo
    for k = 1 to n
      l'(ij) = min(l'(ij), l'(ik) + W(kj))
  return L'

​ 该过程计算在算法结束时返回的矩阵 $L'^{(m)}=({l'}_{i j}^{(m)})$。使用L 作为$L^{(m-1)}$, $L'$ 作为 $L_{(m)}$ 。（在写法上没有注明上标的目的是让输入和输出矩阵独立于变量m )由于有3 层嵌套的for 循环，该算法的运行时间为 $O(n^3)$ 。

​ 我们通过对最短路径一条边一条边地扩展来计算最短路径权重。设A•B 表示由算法EXTEND-SHORTEST-PATHS(A, B) 所返回的矩阵“乘积“，我们可以计算出下面由 n-1 个矩阵所构成的矩阵序列：

$$\begin{array}{l} L^{(1)}=L^{(0)} \cdot W=W \\ L^{(2)}=L^{(1)} \cdot W=W^{2} \\ L^{(3)}=L^{(2)} \cdot W=W^{3} \\ \vdots \\ L^{(n-1)}=L^{(n-2)} \cdot W=W^{n-1} \end{array}$$

​ 矩阵 $L^{(n-1)} = W^{n-1}$ 包含的是最短路径权重。下面的伪代码程序在 $\Theta(n^4)$ 时间内计算出该矩阵序列：

SLOW-ALL-PAIRS-SHORTEST-PATHSCW)
  n = W.rows
  L(1) = W
  for m = 2 to n - 1
    let L(m) be a new nXn matrix
    L(m) = EXTEND-SHORTEST-PATHS(L(m-1), W)
  return L(m-1)

示例

改进算法的运行时间

​ 在没有权重为负值的环路的情况下, 对于所有的 $m \geqslant n-1$ , 我们有 $L^{(m)}=L^{(n-1)}$ 。正如传统的矩阵乘法是相关的，由 EXTEND-SHORTEST-PATHS 过程所定义的 矩阵乘法也是相关的。因此，可以仅用 $\lceil \lg (n-1) \rceil$ 个矩阵乘积来计算矩阵 $L^{(n-1)}$ 。计算的方法如下:

$$\begin{array}{l} L^{(1)}=W \\ L^{(2)}=W^{2}=W \cdot W \\ L^{(4)}=W^{4}=W^{2} \cdot W^{2} \\ L^{(8)}=W^{8}=W^{4} \cdot W^{4} \\ \quad \vdots \\ L^{\left(2^{\lceil\lg (n-1)}\right)}=W^{2\lceil\lg (n-1)\rceil}=W^{2\lceil\lg (n-1)\rceil} \cdot W^{2\lceil\lg (n-1)\rceil-1} \end{array}$$

​ 由于 $2^{\lceil\lg (n-1)\rceil} \geqslant n-1$ , 最后的乘积 $L^{\left(2^{\lceil \lg (n-1) \rceil}\right)}$ 等于 $L^{(n-1)}$ 。 下面的过程使用重复平方技术来计算上述矩阵序列。

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
  n = W.rows
  L(1) = W
  m = 1
  while m < n-1
    let L(2m) be a new nXn matrix
    L(2m) = EXTEND-SHORTEST-PATHS(L(m), L(m))
    m=2m
  return L(m)

Java实现

public class AllShortestGraoh {
    private Node[] nodes;
    private int[][] table;
    private static final int INFITY = Integer.MAX_VALUE / 2 - 1;

    public AllShortestGraoh() {
        // 初始化一个图
        String[] data = new String[] { "1", "2", "3", "4", "5" };
        // 0 1 2 3 4 5 6 7
        // a b c d e f g h
        int[][] edge = new int[][] {
                { 0, 1, 3 },
                { 0, 2, 8 },
                { 0, 4, -4 },
                { 1, 3, 1 },
                { 1, 4, 7 },
                { 2, 1, 4 },
                { 3, 0, 2 },
                { 3, 2, -5 },
                { 4, 3, 6 }
        };

        // 节点
        nodes = new Node[data.length];
        table = new int[data.length][data.length];
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            Arrays.fill(table[i], INFITY);
            table[i][i] = 0;
        }
        // 边
        for (int[] item : edge) {
            table[item[0]][item[1]] = item[2];
        }
    }

    private int[][] extendShortestPaths(int[][] weigth1, int[][] weigth2) {
        int n = weigth1.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans[i][j] = INFITY;
                for (int k = 0; k < n; k++) {
                    ans[i][j] = Math.min(ans[i][j], weigth1[i][k] + weigth2[k][j]);
                }
            }
        }

        return ans;
    }

    public int[][] slowAllPairsShorestPaths() {
        int n = table.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans[i][j] = table[i][j];
            }
        }

        for (int i = 2; i < n; i++) {
            ans = extendShortestPaths(ans, table);
        }

        return ans;
    }

    public int[][] fasterAllPairsShorestPaths() {
        int n = table.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans[i][j] = table[i][j];
            }
        }
        // lg n 次即可计算出结果
        for (int i = 1; i < n - 1; i *= 2) {
            ans = extendShortestPaths(ans, ans);
        }

        return ans;
    }

    public static void main(String[] args) {
        AllShortestGraoh graph = new AllShortestGraoh();
        int[][] cur = graph.slowAllPairsShorestPaths();
        for (int[] is : cur) {
            System.out.println(Arrays.toString(is));
        }
    }
}

分析

​ 因为 $\lceil \lg (n-1) \rceil$ 个矩阵中的每个矩阵的计算时间为 $\Theta(n^3)$, FASTER-ALL-PAIRS-SHORTEST-PATHS 的运行时间为 $\Theta(n^3lg\:n)$ 。由于该代码非常紧凑，没有包含任何精巧的数据结构，隐藏在 $\Theta$ 记号中的常数应该较小。

25.2 Floyd-Warshall 算法

​ 我们使用一种不同的动态规划公式来解决所有结点对最短路径问题。所产生的算法称为 Floyd-Warshall 算法，其运行时间为 $\Theta(V^3)$, 。

最短路径的结构

​ Floyd- Warshall 算法考虑的是一条最短路径上的中间结点，这里，简单路径 $ p = \left<v_1,v_2, \cdots, v_l\right>$上的中间结点指的是路径 p 上除 $v_1$ 和 $v_l$ 之外的任意结点，也就是处于集合 $\{ v_2,v_3, \cdots, v_{l-1} \}$ 中的结点。

假定图G 的所有结点为 $V=\{1, 2, \cdots, n\}$, 考虑其中的一个子集 $\{1, 2, \cdots, k\}$ 这里k 是某个小于n 的整数。对于任意结点对 $i,j \in V$, 考虑从结点 i 到结点 j 的所有中间结点均取自集合 $\{1, 2, \cdots, k\}$ 的路径，并且设p 为其中权重最小的路径（路径p 是简单路径）。Floyd-Warshall 算法利用了路径p 和从 i 到 j 之间中间结点均取自集合 $\{1, 2, \cdots, k-1\}$ 的最短路径之间的关系。

• 如果结点k 不是路径p 上的中间结点，则路径p 上的所有中间结点都属千集合 $\{1, 2, \cdots, k-1\}$ 。因此，从结点i 到结点j 的中间结点取自集合 $\{1, 2, \cdots, k-1\}$ 的一条最短路径也是从结点i 到结点j 的中间结点取自集合 $\{1, 2, \cdots, k\}$ 的一条最短路径。
• 如果结点k 是路径 p 上的中间结点，则将路径p 分解为 $i \overset{p_1}{\leadsto} k \overset{p_2}{\leadsto} j $，即 $p_1$ 是从结点i 到结点k 的中间结点全部取自集合 $\{1, 2, \cdots, k-1\}$ 的一条最短路径。$p_2$ 是从结点k 到结点J 的中间结点全部取自集合 $\{1, 2, \cdots, k-1\}$ 的一条最短路径。

所有结点对最短路径问题的一个递归解

​ 设 $d_{i j}^{(k)}$ 为从结点 i 到结点 j 的所有中间结点全部取自集合 $\{1,2, \cdots, k\}$ 的一条最短路径的权重。当 k=0 时, 从结点 i 到结点 j 的一条不包括编号大于 0 的中间结点的路径将没有任何中间结点。这 样的路径最多只有一条边, 因此, $d_{i j}^{(0)}=w_{i j}$ 。根据上面的讨论, 递归定义 $d_{i j}^{(k)}$ 如下:

$$d_{i j}^{(k)}=\left\{\begin{array}{ll} w_{i j} & \text { 若 } k=0 \\ \min \left(d_{i j}^{(k-1)}, d_{i k}^{(k-1)}+d_{k j}^{(k-1)}\right) & \text { 若 } k \geqslant 1 \end{array}\right.$$

因为对于任何路径来说, 所有的中间结点都属于集合 $\{1,2, \cdots, n\}$ , 矩阵 $D^{(n)}=\left(d_{i j}^{(n)}\right) $ 给出的就 是我们的最后答案: 对于所有的 $i, j \in V, d_{i j}^{(n)}=\delta(i, j) $ 。

自底向上计算最短路径权重

​ 我们可以使用下面的自底向上的算法以递增次序来计算 $d_{i j}^{(k)}$ 的值。该算法的输入为一个nXn 的矩阵W。下面的算法返回的是最短路径权重矩阵 $D_{(n)}$ ：

FLOYD-WARSHALL(W)
  n = W.rows
  D(0) = W
  for k = 1 to n
    let D(k) = (d(k)[i][j]) be a new nXn matrix
    for i = 1 to n
      for j = 1 to n
        d(k)[i][j] = min(d(k-1)[i][j] ,d(k-1)[i][k] + d(k-1)[k][j])
  return D(n)

​ Floyd-Warshall 算法的该算法的运行时间为 $\Theta(n^3)$ 。该代码也非常紧凑，没有使用精巧的数据结构，隐藏在 $\Theta$ 表述后面的常数比较小。因此，即使对于输入规模为中等的图， Floyd-Warshall 算法的效率也相当好。

构建一条最短路径

​ 在 Floyd-Warshall 算法中, 可以有多种不同的方法来构建最短路径。一种办法是先计算最短 路径权重矩阵 D , 然后从 D 矩阵来构造前驱矩阵 pre 。一旦给定了前驱矩阵 pre , PRINT-ALL-PAIRS-SHORTESTPATH 过程将打印出给定最短路径上的所有结点。
​ 另外, 我们可以在计算矩阵 $D^{(k)}$ 的同时计算前驱矩阵 pre 。具体来说, 我们将计算一个矩阵序 列 $pre^{(0)}, pre^{(1)}, \cdots, pre^{(n)}$ , 这里 $pre=pre^{(n)}$ 并且定义 $pre_{i j}^{(k)}$ 为从结点 i 到结点 j 的一条所有中间结点都取 自集合 ${1,2, \cdots, k} $ 的最短路径上 j 的前驱结点。
我们可以给出 $pre_{i j}^{(k)}$ 的一个递归公式。当 k=0 时, 从 i 到 j 的一条最短路径没有中间结点, 因此.

$$pre_{i j}^{(0)}=\left\{\begin{array}{ll} \text { NIL } & \text { 若 } i=j \text { 或 } w_{i j}=\infty \\ i & \text { 若 } i \neq j \text { 且 } w_{i j}<\infty \end{array}\right.$$

对于 $k \geqslant 1$ , 如果考虑路径 $i \leadsto k \leadsto j$ , 这里 $k \neq j$ , 则所选择的结点 j 的前驱与我们选择的从结点 k 到结点 j 的一条中间结点全部取自集合 $\{1,2, \cdots, k-1\}$ 的最短路径上的前驱是一样的。否则, 所选择的结点 j 的前驱与选择的从结点 i 到结点 j 的一条中间结点全部取自集合 $\{1,2, \cdots , k-1\}$ 的最短路径上的前驱是一样的。也就是说, 对于 $k \geqslant 1$ ,

$$pre_{i j}^{(k)}=\left\{\begin{array}{ll} pre_{i j}^{(k-1)} & \text { 若 } d_{i j}^{(k-1)} \leqslant d_{i k}^{(k-1)}+d_{k j}^{(k-1)} \\ pre_{k j}^{(k-1)} & \text { 若 } d_{i j}^{(k-1)}>d_{i k}^{(k-1)}+d_{k j}^{(k-1)} \end{array}\right.$$

改进后的Floyd-Warshall算法

FLOYD-WARSHALL(W)
  n = W.rows
  D(0) = W
  let pre(0) be a new nXn matrix
   for i = 1 to n
      for j = 1 to n
        if i == j or W[i][j] == oo
          pre(0)[i][j] = oo
        else
          pre(0)[i][j] = i
          
  for k = 1 to n
    let D(k) = (d(k)[i][j]) be a new nXn matrix
    let pre(k) = (p(k)[i][j]) be a new nXn matrix
    for i = 1 to n
      for j = 1 to n
        if d(k-1)[i][j] <= d(k-1)[i][k] + d(k-1)[k][j]
          d(k)[i][j] = d(k-1)[i][j]
          p(k)[i][j] = pre(k-1)[i][j]
        else
          d(k)[i][j] = d(k-1)[i][k] + d(k-1)[k][j]
          p(k)[i][j] = p(k-1)[k][j]
  // 输出
  for i = 1 to n
    for j = 1 to n
      PRINT-ALL-PAIRS-SHORTESTPATH(pre(n),i,j)
  
  return D(n)

输出路径函数

PRINT-ALL-PAIRS-SHORTEST-PATH(pre,i,j)
  if i == j
    print i
  else if pre[i][j] == NIL
    print "nodd path from"i"to"j"exists"
  else
    PRINT-ALL-PAIRS-SHORTEST-PATH(pre,i, pre[i][j])
  	print j

Java实现

public class WarshallShortestGraoh {
    private Node[] nodes;
    private int[][] table;
    private static final int INFITY = Integer.MAX_VALUE / 2 - 1;

    public WarshallShortestGraoh() {
        // 初始化一个图
        String[] data = new String[] { "1", "2", "3", "4", "5" };
        // 0 1 2 3 4 5 6 7
        // a b c d e f g h
        int[][] edge = new int[][] {
                { 0, 1, 3 },
                { 0, 2, 8 },
                { 0, 4, -4 },
                { 1, 3, 1 },
                { 1, 4, 7 },
                { 2, 1, 4 },
                { 3, 0, 2 },
                { 3, 2, -5 },
                { 4, 3, 6 }
        };

        // 节点
        nodes = new Node[data.length];
        table = new int[data.length][data.length];
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            Arrays.fill(table[i], INFITY);
            table[i][i] = 0;
        }
        // 边
        for (int[] item : edge) {
            table[item[0]][item[1]] = item[2];
        }
    }

    public int[][] floydWarshall() {
        int n = nodes.length;
        int[][] ans = new int[n][n];
        // 初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans[i][j] = table[i][j];
            }
        }
        // 前驱矩阵
        int[][] pre = new int[n][n];
        // 初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || table[i][j] == INFITY) {
                    pre[i][j] = INFITY;
                } else {
                    pre[i][j] = i;
                }
            }
        }

        // 计算
        for (int k = 0; k < n; k++) {
            int[][] newAns = new int[n][n];
            int[][] newPre = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (ans[i][j] <= ans[i][k] + ans[k][j]) {
                        newAns[i][j] = ans[i][j];
                        newPre[i][j] = pre[i][j];
                    } else {
                        newAns[i][j] = ans[i][k] + ans[k][j];
                        newPre[i][j] = pre[k][j];
                    }
                }
            }
            ans = newAns;
            pre = newPre;
        }

        for (int i = 0; i < pre.length; i++) {
            for (int j = 0; j < pre.length; j++) {
                System.out.print(i + "->" + j + ": ");
                printAllPairsShortestPath(pre, i, j);
                System.out.println();
            }
        }

        return ans;
    }

    public void printAllPairsShortestPath(int[][] pre, int i, int j) {
        if (i == j) {
            System.out.print(i + "->");
        } else if (pre[i][j] == INFITY) {
            System.out.printf("noPath from %d to %d\n", i, j);
        } else {
            printAllPairsShortestPath(pre, i, pre[i][j]);
            System.out.print(j + "->");
        }
    }

    public static void main(String[] args) {
        WarshallShortestGraoh graph = new WarshallShortestGraoh();
        int[][] cur = graph.floydWarshall();
        for (int[] is : cur) {
            System.out.println(Arrays.toString(is));
        }
    }
}

示例

25.3 用千稀疏图的 Johnson 算法

​ Johnson 算法可以在 $O(V^2 lgV+VE)$ 的时间内找到所有结点对之间的最短路径。Johnson 算法要么返回一个包含所有结点对的最短路径权重的矩阵，要么报告输入图包含一个权重为负值的环路。Johnson 算法在运行中需要使用Dijkstra 算法和Bellman-Ford 算法作为自己的子程序。

​ Johnson 算法使用的技术称为重新赋予权重。该技术的工作原理如下：如果图 $G=(V, E)$ 中所有的边权重w 皆为非负值，我们可以通过对每个结点运行一次Dijkstra 算法来找到所有结点对之间的最短路径；如果使用斐波那契堆最小优先队列，该算法的运行时间为$O(V^2 lgV+VE)$ 。如果图G 包含权重为负值的边，但没有权重为负值的环路，那么只要计算出一组新的非负权重值， 卫回然后使用同样的方法即可。新赋予的权重 $\hat{w}$ 必须满足下面两个重要性质：

1. 对于所有结点对 $u, v \in V$, 一条路径p 是在使用权重函数w 时从结点u 到结点v 的一条最短路径，当且仅当p 是在使用权重函数也时从u 到v 的一条最短路径。
2. 对于所有的边(u, v), 新权重 $\hat{w} (u, v)$ 为非负值。正如我们将要看到的，我们可以对图G 进行预处理，并在 $O(VE)$ 的时间内计算出 $\hat{w}$

计算所有结点对之间的最短路径

​ 我们在图G中增加一个新结点S，并让其与其他结点相连，形成一幅新图G’，对G’进行Bellman-Ford算法计算从S到各结点的最短路径h，删除结点S，然后根据新权重确定公式 $w'(u,v)=w(u,v)+h(u)-h(v)$：对原图的权重进行修改，使得权重都为正，然后对每个结点进行一次Dijkstra算法找到结点对的最短路径。

​ Johnson 算法在执行过程中需要使用Bellman-Ford 算法和Dijkstra 算法作为子程序来计算所有结点对之间的最短路径。该算法假定所有的边都保存在邻接链表里，其返回的则是一个 $|V| \times |V|$ 的矩阵 $D=d_{ij}$ 其中 $d_{ij}=\delta(i,j)$, 或者报告输入图包含一个权重} 为负值的环路。对千所有结点对最短路径算法来说，我们通常假定结点的编号为从 $1 \sim |V|$ 。

JOHNSON(G,w)
  compute G', where G'.V = G.V并{s}, G'.E = G.E并{(s,v):v属于G.V},and w(s,v)=0 for all v属于G.V
  if BELLMAN-FORD(G',w,s) == FALSE
    print "the input graph contains a negative-weight cycle"
  else 
    for each vertex v属于G'.V
      set h(v) to the value of A(s,v)
        computed by the Bellman-Ford algorithm
    for each edge(u,v)属于G'.E
      w'(u,v) = w(u,v) + h(u) - h(v)
      let D = (d(uv)) be a new nXn matrix
    for each vertex u属于G.V
      run DUKSTRA(G,w',u) to compute A'(u,v) for all v属于G.V
      for each vertex v属于G.V
        d(uv) = A'(u,v) + h(v) - h(u)
  return D

注意代码表示：$A:\delta,\:A' : \hat{\delta}, \: w':\hat{w}$

Java实现

public class JohnsonShortestGraoh {
    private Node[] nodes;
    private List<List<int[]>> table;
    private static final int INFITY = Integer.MAX_VALUE / 2 - 1;

    public JohnsonShortestGraoh() {
        // 初始化一个图
        String[] data = new String[] { "1", "2", "3", "4", "5" };
        // 0 1 2 3 4 5 6 7
        // a b c d e f g h
        int[][] edge = new int[][] {
                { 0, 1, 3 },
                { 0, 2, 8 },
                { 0, 4, -4 },
                { 1, 3, 1 },
                { 1, 4, 7 },
                { 2, 1, 4 },
                { 3, 0, 2 },
                { 3, 2, -5 },
                { 4, 3, 6 }
        };

        // 节点
        nodes = new Node[data.length];
        table = new ArrayList<>(data.length);
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
            table.add(new LinkedList<int[]>());
        }
        // 边
        for (int[] item : edge) {
            table.get(item[0]).add(new int[] { item[1], item[2] });
        }
    }

    public int[] dijkstra(int index, Node[] nodes, List<List<int[]>> table) {
        // 初始化
        for (Node node : nodes) {
            node.distance = INFITY;
            node.pre = null;
        }
        nodes[index].distance = 0;
        Queue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.distance - o2.distance);
        for (Node node : nodes) {
            queue.add(node);
        }

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (int[] item : table.get(node.index)) {
                if (node.distance + item[1] < nodes[item[0]].distance) {
                    nodes[item[0]].distance = node.distance + item[1];
                    nodes[item[0]].pre = node;
                }
            }
        }

        return Arrays.stream(nodes).mapToInt((obj) -> obj.distance).toArray();
    }

    public boolean bellmanFord(int index, Node[] nodes, List<List<int[]>> table) {
        // 初始化
        for (Node node : nodes) {
            node.distance = INFITY;
            node.pre = null;
        }
        nodes[index].distance = 0;
        // 迭代
        for (int i = 0; i < nodes.length; i++) {
            // 遍历节点
            for (int j = 0; j < nodes.length; j++) {
                for (int[] item : table.get(j)) {
                    if (nodes[j].distance + item[1] < nodes[item[0]].distance) {
                        nodes[item[0]].distance = nodes[j].distance + item[1];
                        nodes[item[0]].pre = nodes[j];
                    }
                }
            }
        }

        for (int j = 0; j < nodes.length; j++) {
            for (int[] item : table.get(j)) {
                if (nodes[j].distance + item[1] < nodes[item[0]].distance) {
                    return false;
                }
            }
        }

        return true;
    }

    public int[][] johnson() {
        int n = nodes.length;
        // compute G'
        // 此处不能用 Arrays.copyOf
        // 不然 newNodes 中的元素改变 node 中的元素也会跟着变
        Node[] newNodes = new Node[n + 1];
        for (int i = 0; i < n; i++) {
            newNodes[i] = new Node(nodes[i].index, nodes[i].data);
        }
        newNodes[n] = new Node(n, "-1");

        List<List<int[]>> newTable = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<int[]> item = new LinkedList<>();
            for (int[] js : table.get(i)) {
                item.add(Arrays.copyOf(js, js.length));
            }
            newTable.add(item);
        }
        List<int[]> temp = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            temp.add(new int[] { i, 0 });
        }
        newTable.add(temp);
        // end init G'

        int[][] ans = new int[n][n];

        // 使用 BellmanFord 计算各节点的最短路径
        if (!bellmanFord(n, newNodes, newTable)) {
            System.out.println("the input graph contains a negative-weight cycle");
        } else {
            // compute result
            for (int i = 0; i < newNodes.length; i++) {
                for (int[] item : newTable.get(i)) {
                    item[1] += (newNodes[i].distance - newNodes[item[0]].distance);
                }
            }

            // com
            for (Node node : nodes) {
                int i = node.index;
                int[] delta = dijkstra(i, nodes, newTable);
                for (int j = 0; j < n; j++) {
                    ans[i][j] = delta[j] + (newNodes[j].distance - newNodes[i].distance);
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        JohnsonShortestGraoh graph = new JohnsonShortestGraoh();
        int[][] cur = graph.johnson();
        for (int[] is : cur) {
            System.out.println(Arrays.toString(is));
        }
    }
}

Johnson 算法的执行过程

第二十六章 最大流

​ 我们可以把流网络中每条有向边看做是物料的一个流通通道。每条通道有限定的容量，是物料流经该通道时的最大速率，流网络中的结点则是通道的连接点。除了源结点和终结点外，物料在其他结点上只是流过，并不积累或聚集。换句话说，物料进入一个结点的速率必须与其离开该结点的速率相等。

​ 在最大流问题中，我们希望在不违反任何容量限制的情况下，计算出从源结点运送物料到汇点的最大速率。这是与流网络有关的所有问题中最简单的问题之一。

26.1 流网络

流网络和流

​ 流网络 G=(V, E) 是一个有向图，图中每条边 $(u, v) \in E$ 有一个非负的容量值 $c(u, v) \ge 0$ 。而且，如果边集合E 包含一条边 (u, v), 则图中不存在反方向的边 (v, u) 。如果 $(u, v) \in E$, 则为方便起见，定义 $c(u, v) = 0$, 并且在图中不允许自循环。

​ 在流网络的所有结点中，我们特别分辨出两个特殊结点：源结点s 和汇点t 。为方便起见，假定每个结点都在从源结点到汇点的某条路径上。也就是说，对于每个结点 $v \in V$, 流网络都包含一条路径 $s \leadsto v \leadsto t$ 。因此，流网络图是连通的，并且由于除源结点外的每个结点都至少有一条进入的边，我们有 $|E| \ge |V| - 1$ 。

​ 设G=(V, E) 为一个流网络，其容量函数为c 。设s 为网络的源结点， t 为汇点。G 中的流是一个实值函数 $V \times V \to R$, 满足下面的两条性质：

• 容量限制: 对于所有的结点 $u, v \in V$ , 要求 $0 \leqslant f(u, v) \leqslant c(u, v) $ 。
• 流量守恒: 对于所有的结点 $u \in V-\{s, t\}$ , 要求

$$\sum_{v \in V} f(v, u)=\sum_{v \in V} f(u, v)$$

当 $(u, v) \notin E$ 时, 从结点 u 到结点 v 之间没有流, 因此 f(u, v)=0 。

​ 我们称非负数值 f(u, v) 为从结点 u 到结点 v 的流。一个流 f 的值 |f| 定义如下:

$$|f|=\sum_{v \in V} f(s, v)-\sum_{v \in V} f(v, s)$$

也就是说, 流 f 的值是从源结点流出的总流量减去流人源结点的总流量。（这里, 符号 $| \bullet |$ 表示 流的值, 而不是绝对值或者基数值。通常来说, 一个流网络不会有任何进人源结点的边, 因此, 求和项 $\sum_{v \in V} f(v, s)$ 将是 0 。

使用反平行边来模拟问题

具有多个源结点和多个汇点的网络

26. 2 Ford-Fulkerson 方法

​ Ford-Fulkerson 方法循环增加流的值。在开始的时候, 对于所有的结点 $u, v \in V , f(u, v)=0 $, 给出的初始流值为 0 。在每一次迭代中, 我们将图 G 的流值进行增加, 方法就是在 一个关联的“残存网络” $G_{f}$ 中寻找一条“增广路径”。一旦知道图 $G_{f}$ 中一条增广路径的边，就可以 很容易辨别出 G 中的一些具体的边, 我们可以对这些边上的流量进行修改, 从而增加流的值, 虽然 Ford-Fulkerson 方法的每次迭代都增加流的值，但是对于图 G 的一条特定边来说, 其流量可 能增加, 也可能减少; 对某些边的流进行缩减可能是必要的, 以便让算法可以将更多的流从源结 点发送到汇点。重复对流进行这一过程, 直到残存网络中不再存在增广路径为止。最大流最小切 割定理将说明在算法终结时, 该算法将获得一个最大流。

FORD-FULKERSON-METHOD(G,s,t)
  initialize flow f to 0
  while there exists an augmenting path p in the residual network G1
    augment flow f along p
  return f

残存网络

​ 从直观上看，给定流网络G 和流量f, 残存网络G1 由那些仍有空间对流量进行调整的边构成。流网络的一条边可以允许的额外流量等千该边的容扯减去该边上的流量。如果该差值为正，则将该条边置于图G1 中，并将其残存容量设置为 $c_f(u, v) =c(u, v)-f(u, v)$ 。对于图G 中的边来说，只有能够允许额外流量的边才能加入到图$G_f$中。如果边(u, v) 的流量等千其容量，则其 $c_f(u, v)=0$, 该条边将不属千图 $G_f$。

​ 残存网络 $G_f$ 还可能包含图G 中不存在的边。算法对流量进行操作的目标是增加总流量，为此，算法可能对某些特定边上的流量进行缩减。为了表示对一个正流量 f(u, v) 的缩减，我们将边 (v, u) 加入到图 $G_f$ 中，并将其残存容量设置为 $c_f(v, u)= f(u, v)$ 。也就是说，一条边所能允许的反向流量最多将其正向流量抵消。残存网络中的这些反向边允许算法将已经发送出来的流量发送回去。而将流量从同一条边发送回去等同于缩减该条边的流量，这种操作在许多算法中都是必需的。

​ 假定有一个流网络G=(V, E), 其源结点为s, 汇点为t 。设f 为图G 中的一·个流，考虑结点对 $u, v \in V$, 定义残存容量 $c_f(u, v)$ 如下：

$$c_{f}(u, v)=\left\{\begin{array}{ll} c(u, v)-f(u, v) & \text { 若 }(u, v) \in E \\ f(v, u) & \text { 若 }(v, u) \in E \\ 0 & \text { 其他 } \end{array}\right.$$

因为假定边 $ (u, v) \in E$ 意味着 $(v, u) \notin E$ , 对于每一对边来说, 上述公式只有一种情况成立。

增广路径

​ 给定流网络 G=(V, E) 和流 f , 增广路径 p 是残存网络 $G_{f}$ 中一条从源结点 s 到汇点 t 的简 单路径。根据残存网络的定义, 对于一条增广路径上的边 (u, v) , 我们可以增加其流量的幅度最 大为 $c_{f}(u, v)$ , 而不会违反原始流网络 G 中对边 (u, v) 或 (v, u) 的容量限制。

​ 图 26-4 (b) 中阴影覆盖的路径是一条增广路径。如果将图中的残存网络 $G_{f}$ 看做一个流网络, 那么可以对这条路径上每条边的流量增加 4 个单位, 而不会违反容量限制, 因为该条路径上最小 的残存容量是 $ c_{f}\left(v_{2}, v_{3}\right)=4$ 。我们称在一条增广路径 p 上能够为每条边增加的流量的最大值为 路径 p 的残存容量，该容量由下面的表达式给出:

$$c_{f}(p)=\min \left\{c_{f}(u, v):(u, v) \text { 属于路径 } p\right\}$$

流网络的切割

​ Ford-Fulkerson 方法的核心就是沿着增广路径重复增加路径上的流量，直到找一个最大流为止。一个流是最大流当且仅当其残存网络不包含任何增广路径。

基本的Ford-Fulkerson 算法

​ 在Ford-Fulkerson 方法的每次迭代中，寻找某条增广路径p, 然后使用p 来对流f 进行修改（增加）。在下面的算法实现中, 通过为每条边 $ (u, v) \in E $ 更新流属性 $(u, v).f$ 来计算 流网络 G=(V, E) 中的最大流。如果边 $(u, v) \notin E$ , 则假设 $(u, v).f=0$ 。另外, 假设流网络的 容量 c(u, v) 都已经给出, 如果边 $(u, v) \notin E$ , 则 $c(u, v)=0$ 。根据式残存网络中的公式来计算残存容量 $c_{f}(u, v)$ 。代码中的表达式 $ c_{f}§$ 只是一个临时变量, 用来存放路径 p 的残存容量。

FORD-FULKERSON(G, s, t)
  for each edge(u,v) 属于 G.E
    (u,v).f = 0
  while there exists a path p from s to t in the residual network Gf
    cf(p) = min{cf(u,v): (u,v) is in p}
    for each edge(u,v) in p
      if (u,v) 属于 E
        (u,v).f = (u,v).f + cf(P)
      else
        (v,u).f = (v,u).f - cf(P)

Java实现

public class FlowGraph {
    private Node[] nodes;
    private int[][] table;
    private static final int INFITY = Integer.MAX_VALUE / 2 - 1;

    LinkedList<Node> resultPath = new LinkedList<>();
    int source, target;
    private byte[] visit;

    public FlowGraph() {

        // 初始化一个图
        String[] data = new String[] { "s", "v1", "v2", "v3", "v4", "t" };
        // s v1 v2 v3 v4 t
        // 0 1 2 3 4 5
        int[][] edge = new int[][] {
                { 0, 1, 16 },
                { 0, 2, 13 },
                { 1, 3, 12 },
                { 2, 1, 4 },
                { 2, 4, 14 },
                { 3, 2, 9 },
                { 3, 5, 20 },
                { 4, 3, 7 },
                { 4, 5, 4 }
        };

        // 节点
        nodes = new Node[data.length];
        table = new int[data.length][data.length];
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
        }
        // 边
        for (int[] item : edge) {
            table[item[0]][item[1]] = item[2];
        }

        // 其他
        source = 0;
        target = data.length - 1;
        visit = new byte[data.length];
    }

    private void dnsFindPath(int index, int[][] survive, LinkedList<Node> path) {
        if (!resultPath.isEmpty())
            return;
        if (index == target) {
            resultPath.addAll(path);
            return;
        }
        for (int i = 0; i < nodes.length; i++) {
            if (survive[index][i] > 0 && visit[i] == 0) {
                visit[i] = 1;
                path.add(nodes[i]);
                dnsFindPath(i, survive, path);
                path.removeLast();
                visit[i] = 0;
            }
        }
    }

    public LinkedList<int[]> dnsFindPath(int[][] survive) {
        // 初始化
        Arrays.fill(this.visit, (byte) 0);
        visit[source] = 1;
        resultPath.clear();

        LinkedList<Node> path = new LinkedList<>();
        path.add(nodes[source]);
        dnsFindPath(source, survive, path);

        LinkedList<int[]> ret = new LinkedList<>();
        if (resultPath.size() < 2)
            return ret;
        Iterator<Node> it = resultPath.iterator();

        int minVal = INFITY;
        Node last = it.next();
        while (it.hasNext()) {
            Node next = it.next();
            ret.add(new int[] { last.index, next.index });
            minVal = Math.min(minVal, survive[last.index][next.index]);
            last = next;
        }
        ret.add(new int[] { minVal });

        for (Node node : resultPath) {
            System.out.print(node.data + "->");
        }
        System.out.println();

        return ret;
    }

    public void fordFulkerson() {
        int n = nodes.length;
        int[][] flow = new int[n][n];
        int[][] survive = new int[n][n];
        for (int i = 0; i < n; i++) {
            survive[i] = Arrays.copyOf(table[i], n);
        }

        int ansNum = 0;
        while (true) {
            // 寻找路径
            LinkedList<int[]> ans = dnsFindPath(survive);
            if (ans.isEmpty())
                break;
            // 寻找参数
            int minVal = ans.pollLast()[0];
            for (int[] item : ans) {
                int x = item[0];
                int y = item[1];

                survive[x][y] -= minVal;
                survive[y][x] += minVal;

                if (x < y) {
                    flow[x][y] += minVal;
                } else {
                    flow[y][x] -= minVal;
                }
            }
            ansNum += minVal;
        }

        for (int[] is : flow) {
            System.out.println(Arrays.toString(is));
        }
        System.out.println();
        System.out.println(ansNum);
    }

    public static void main(String[] args) {
        FlowGraph graph = new FlowGraph();
        graph.fordFulkerson();
    }
}

分析

​ 如果用来实现流网络 G=(V, E) 的数据结构是合理的，并且寻找一条增广路径的算法时间是线性的，则整个while 循环的执行将非常有效。如果 $|f^*|$ 表示转换后网络中的一个最大流，则在FORD-FULKERSON 算法的一个直接实现中，执行while 循环的次数最多为 $|f^*|$ 次，因为流量值在每次迭代中最少增加一个单位。整个FORD-FULKERSON 算法的运行时间为 $O(E|f^*|)$ 。

示例

Edrnonds-Karp算法

​ 我们可以通过在算法第3 行寻找增广路径的操作中使用广度优先搜索来改善FORDFULKERSON算法的效率。也就是说，我们在残存网络中选择的增广路径是一条从源结点s 到汇点t 的最短路径，其中每条边的权重为单位距离。我们称如此实现的Ford-Fulkerson 方法为Edrnonds-K叩算法。现在来证明Edmonds-Karp 算法的运行时间为$O(VE^2)$ 。

​ 由于在用广度优先搜索寻找增广路径时， FORD-FULKERSON 中的每次迭代可以在 $O(E)$ 时间内实现，所以Edmonds-Karp 算法的总运行时间为 $O(VE^2)$ 。

26.3 最大二分匹配

最大二分匹配问题

​ 给定一个无向图 G=(V, E) , 一个匹配是边的一个子集 $M \subseteq E$ , 使得对于所有结点 $v \in V$ , 子集 M 中最多有一条边与结点 v 相连。如果子集 M 中的某条边与结点 v 相连, 则称结点 v 由 M 所匹配; 否则, 结点 v 就是没有匹配的。最大匹配是最大基数的匹配, 也就是说, 对于任意匹配 $M^{\prime}$ , 有 $|M| \geqslant\left|M^{\prime}\right|$ 的匹配 $M$。在一个二分图中, 结点集合可以划分为 $V=L \cup R$ , 其中 L 和 R 是不相交的, 并且边集合 E 中所有的边都横跨 L 和 R 。进一步假定结点集合 V 中的每个结点至少有一条边。

寻找最大二分匹配

​ 使用Ford-Fulkerson 方法可以在关于$|V|$和$|E|$ 阳的多项式时间内，找出无向二分图 $G=(V, E)$ 的最大匹配。我们将二分图G 所对应的流网络 $G'=(V', E')$ 定义如下：设源结点 s 和汇点t 为不属千结点集V 的新结点，并设 $V'=V \cup \{s, t\}$ 。如果图G 的结点集划分为 $V=L \cup R$, 则E中从L 指向R 的边都是流网络G’ 的边。此外， $G'$ 中的边还包括如下的1 们条新有向边：

$$E'= \{(s,u):u \in L\} \cup \{(u,v):(u,v) \in E\} \cup \{(v,t):v \in R\}$$

​ 要完成流网络的构建，需要给 $E'$ 中的每条边赋予单位容量。由于结点集 $V$ 中的每个结点至少有一
条相连的边， $|E| \ge |V| /2 $ 。因此， $|E| \le |E’| = |E| + |v| \le 3|E| $, 所以 $|E'|=\Theta(E)$ 。

​ 给定一个二分无向图G, 可以通过创建流网络 $G'$, 在其上运行Ford-Fulkerson 方法来找到一个最大匹配。这个最大匹配 $M$ 可以直接从找到的整数最大流 $f$ 获得。由于二分图中的任何匹配的基数的最大值为$min(L, R)=O(V)$, $G'$ 中的最大流的值为$O(V)$ 。因此，可以在 $O(VE') =O(VE)$ 时间内找到一个二分图的最大匹配，因为 $|E'|=\Theta(E)$ 。

Java实现

public class MaxBisectFlowGraph {
    private Node[] nodes;
    private int[][] table;
    private static final int INFITY = Integer.MAX_VALUE / 2 - 1;

    LinkedList<Node> resultPath = new LinkedList<>();
    int source, target;
    private byte[] visit;

    public MaxBisectFlowGraph() {

        // 初始化一个图
        String[] data = new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
        // 1 2 3 4 5 6 7 8 9
        int[][] edge = new int[][] {
                { 0, 5, 1 },
                { 1, 5, 1 },
                { 1, 7, 1 },
                { 2, 6, 1 },
                { 2, 7, 1 },
                { 2, 8, 1 },
                { 3, 7, 1 },
                { 4, 7, 1 }
        };

        // 节点
        nodes = new Node[data.length];
        table = new int[data.length][data.length];
        for (int i = 0; i < data.length; i++) {
            nodes[i] = new Node(i, data[i]);
        }
        // 边
        for (int[] item : edge) {
            table[item[0]][item[1]] = item[2];
            table[item[1]][item[0]] = item[2];
        }

        // 其他
        source = 0;
        target = data.length - 1;
        visit = new byte[data.length];
    }

    private void dnsFindPath(int index, int[][] survive, LinkedList<Node> path) {
        if (!resultPath.isEmpty())
            return;
        if (index == target) {
            resultPath.addAll(path);
            return;
        }
        for (int i = 0; i < nodes.length; i++) {
            if (survive[index][i] > 0 && visit[i] == 0) {
                visit[i] = 1;
                path.add(nodes[i]);
                dnsFindPath(i, survive, path);
                path.removeLast();
                visit[i] = 0;
            }
        }
    }

    public LinkedList<int[]> dnsFindPath(int[][] survive) {
        // 初始化
        Arrays.fill(this.visit, (byte) 0);
        visit[source] = 1;
        resultPath.clear();

        LinkedList<Node> path = new LinkedList<>();
        path.add(nodes[source]);
        dnsFindPath(source, survive, path);

        LinkedList<int[]> ret = new LinkedList<>();
        if (resultPath.size() < 2)
            return ret;
        Iterator<Node> it = resultPath.iterator();

        int minVal = INFITY;
        Node last = it.next();
        while (it.hasNext()) {
            Node next = it.next();
            ret.add(new int[] { last.index, next.index });
            minVal = Math.min(minVal, survive[last.index][next.index]);
            last = next;
        }
        ret.add(new int[] { minVal });
        return ret;
    }

    // 判断二分图
    // 开始对任意一未染色的顶点染色，之后判断其相邻的顶点中
    // 若未染色则将其染上和相邻顶点不同的颜色
    // 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图
    // 若颜色不同则继续判断
    private boolean isBisectGraph() {
        Arrays.fill(visit, (byte) 0);
        Queue<Node> queue = new LinkedList<>();
        queue.add(nodes[0]);
        visit[0] = -1;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (int i = 0; i < nodes.length; i++) {
                if (table[node.index][i] > 0) {
                    if (visit[i] == 0) {
                        // 染色
                        visit[i] = (byte) ((visit[node.index] == -1) ? 1 : -1);
                        queue.add(nodes[i]);
                    } else if (visit[i] == visit[node.index]) {
                        // 颜色相同
                        return false;
                    }
                }
            }
        }
        return true;
    }

    // 划分
    public void maxBisect() {
        // 划分集合
        if (!isBisectGraph()) {
            System.out.println("不是二分图");
            return;
        }
        // 集合划分
        LinkedList<Node> set0 = new LinkedList<>();
        LinkedList<Node> set1 = new LinkedList<>();
        for (int i = 0; i < visit.length; i++) {
            if (visit[i] == -1)
                set0.add(nodes[i]);
            else
                set1.add(nodes[i]);
        }

        int newLen = nodes.length + 2;
        Node[] newNodes = new Node[newLen];
        for (int i = 0; i < nodes.length; i++) {
            newNodes[i] = nodes[i];
        }
        // 新增源点和目标点
        source = nodes.length;
        target = nodes.length + 1;
        newNodes[source] = new Node(source, "new" + (source + 1));
        newNodes[target] = new Node(target, "new" + (target + 1));

        int[][] newTable = new int[newLen][newLen];
        for (Node n0 : set0) {
            for (Node n1 : set1) {
                newTable[n0.index][n1.index] = table[n0.index][n1.index];
            }
        }
        for (Node node : set0) {
            newTable[source][node.index] = 1;
        }
        for (Node node : set1) {
            newTable[node.index][target] = 1;
        }

        this.nodes = newNodes;
        this.table = newTable;
        this.visit = new byte[newLen];

        // 最大流算法
        List<int[]> ansPath = new LinkedList<>();
        while (true) {
            // 寻找路径
            LinkedList<int[]> ans = dnsFindPath(newTable);
            if (ans.isEmpty())
                break;
            // 寻找参数
            int minVal = ans.pollLast()[0];
            for (int[] item : ans) {
                int x = item[0];
                int y = item[1];

                newTable[x][y] -= minVal;
                newTable[y][x] += minVal;

                if (item[0] != source && item[1] != target) {
                    ansPath.add(new int[] { x, y });
                }
            }
        }

        for (int[] is : ansPath) {
            System.out.println(Arrays.toString(is));
        }
        System.out.println(ansPath.size());
    }

    public static void main(String[] args) {
        MaxBisectFlowGraph graph = new MaxBisectFlowGraph();
        graph.maxBisect();
    }
}