这一章，我们讨论一个全新的数据结构，图。

图的特点

首先，什么是图，图都有什么特点？

金庸先生有一部小说《天龙八部》，"天龙八部"这个名字出自佛经，意思是芸芸众生。所以，这部小说的一个特点就是人多，而且关系复杂。比如，这是《天龙八部》的人物关系图：

上面的图什么特点？
首先有一位一位的人物，然后人物之间还或有连接。而且上图中，连接都是有方向的，每个连接还带有一个关系。
我们把这个抽象出来。
图的特点是：

图由点的集合和边的集合组成
边上可能会带有权值
边会有方向

前两个特点，大家都是这么认为的。
但是对于第三个特点，可能会有争议，有些资料会把边分成两种：有向边和无向边。有向边组成的图是有向图，无向边组成的图是无向图。
比如在数据结构的经典教材，严蔚敏老师的《数据结构(C语言版)》中，就有向边和无向边。

严蔚敏老师是这么说的：
若 $<v,w> \in \bold{VR}$ 必有 $<w,v> \in \bold{VR}$ ，即 $\bold{VR}$ 是对称的，则以无序对 $(v,w)$ 代替这两个有序对，表示 $v$ 和 $w$ 之间的一条边(Edge)，此时的图称为无向图(Undigraph)。

你们看！用无序对代替两个有序对，那么我们也可以不代替咯，就用两个有序对表示一个无序对。
即：我们也可以用两个方向相反的有向边代替一个无向边。

图的表示

那么，图怎么表示呢？
这次我们不以天龙八部人物关系图为例了，因为关系太复杂。这部小说，无人不冤，有情皆孽。
只是为了讨论图的表示方法的话，我们以一个简单的图为例。

邻接表法

我们讨论的第一个表示图的方法是邻接表法。
在上图中，从A出发，一条边就能连接的邻居有C；从B出发，一条边就能连接的邻居有A和C, ···
所以，用邻接表，表示如下：

	邻接表
A	C
B	A,C
C
D	B,C

那么，对于权重怎么办呢？那我们这样。

	邻接表
A	(C,1)
B	(A,3),(C,4)
C
D	(B,1),(C,5)

这就是邻接表法。

邻接矩阵法

我们讨论的第二种方法是邻接矩阵法。
比如我们把最左侧的列记作from，把顶部的行记作to，在单元格中填入权重。对于没有这条边的我们填 $\infty$ 。
则有：

	A	B	C	D
A	$0$	$\infty$	$1$	$\infty$
B	$3$	$0$	$4$	$\infty$
C	$\infty$	$\infty$	$0$	$\infty$
D	$\infty$	$1$	$5$	$0$

这就是邻接矩阵法

Node-Edge-Graph

那么？还有没有第三种方法呢？
有，比如，我们可以只用一个矩阵来表示。

$\left[ \begin{matrix} 3 & 1 & 4 \\ 1 & 5 & 9 \\ 2 & 6 & 5 \\ \end{matrix} \right]$

这里每一行的第一个数字表示权重，第二个数字表示from，第三个数字表示to。
除此之外，还有很多，各种各样的表示方法。
那么这意味着什么？对于和图相关的算法，我们要针对每一种图的表示方法，都写一个！
这里给大家介绍一个东西。

我们只写一个标准的，剩下的用转接口。
而这个标准的表示方法，就是Node-Edge-Graph。
这种表示方法或许冗余，但实现算法更方便。

Node

示例代码：

package ch10;

import java.util.ArrayList;

/**
 * 点
 */
public class Node {
    // id 节点的唯一标示
    public Integer id;
    // 入度 指向该节点的边的数量
    public Integer in;
    // 出度 从该节点出发的边的数量，也是nexts的size
    public Integer out;
    // 从该节点出发的边数，指向所有节点 next
    public ArrayList<Node> nexts;
    // 从该节点出发的边
    public ArrayList<Edge> edges;

    /**
     *
     * @param id 节点的ID
     */
    public Node(Integer id){
        this.id = id;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", in=" + in +
                ", out=" + out +
                '}';
    }
}

示例代码：

class Node:
    def __init__(self, v):
        self.id = v
        self.in_size = 0
        self.out_size = 0
        self.nexts = []
        self.edges = []

    def __str__(self):
        return "Node{" + "id=" + str(self.id) + ", in_size =" + str(self.in_size) + ", out_size =" + str(self.out_size) + "}"

Edge

示例代码：

package ch10;

public class Edge {
    // 边的权重
    public Integer weight;
    // 边的出发节点
    public Node from;
    // 边的指向节点
    public Node to;

    /**
     *
     * @param weight 权重
     * @param from from节点
     * @param to to节点
     */
    public Edge(Integer weight,Node from,Node to){
        this.weight = weight;
        this.from = from;
        this.to = to;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "weight=" + weight +
                ", from=" + from.id +
                ", to=" + to.id +
                '}';
    }
}

示例代码：

class Edge:
    def __init__(self, w, f, t):
        self.weight = w
        self.from_node = f
        self.to_node = t

    def __str__(self):
        return "Edge{" + "weight=" + str(self.weight) + ", from_node=" + str(self.from_node.id) + ", to=" + str(self.to_node.id) + "}"

Graph

图是由点和集合和边的集合所组成的。

示例代码：

package ch10;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 图
 */
public class Graph {
    // 点集合，用Map的原因是因为Map根据Key找点方便
    public HashMap<Integer,Node> nodes;
    // 边集合
    public HashSet<Edge> edges;

    public Graph(){
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

示例代码：

class Graph:
    def __init__(self):
        self.nodes = dict()
        self.edges = set()

如此，我们图的结构就定义好了。之后，如果我们收到了各种奇奇怪怪的图表示方法，都可以转换成这种的。比如就以我们刚刚说的矩阵为例，每一行的第一个数字表示权重，第二个数字表示from，第三个数字表示to。

示例代码：

package ch10;

public class Converter {

    /**
     * 把矩阵结构的图转换成我们自己的图
     * @param matrix 矩阵
     * @return 转后后的图
     */
    public static Graph FromMatrixToGraph(Integer[][] matrix){
        // 初始化图
        Graph graph = new Graph();
        // 遍历矩阵的行
        for (int i = 0; i < matrix.length; i++) {
            // 第一个数代表权重
            Integer weight = matrix[i][0];
            // 第二个数代表from节点的Id
            Integer fromId = matrix[i][1];
            // 第三个数代表to节点的Id
            Integer toId = matrix[i][2];
            // 如果图不包含fromId的节点，即这个节点从来没出现过
            if (!graph.nodes.containsKey(fromId)){
                // 把节点添加到图中
                Node node = new Node(fromId);
                graph.nodes.put(fromId,node);
            }
            // 如果图中不包含toId的节点，即这个节点从来没出现过
            if (!graph.nodes.containsKey(toId)){
                // 把节点添加到图中
                Node node = new Node(toId);
                graph.nodes.put(toId,node);
            }
            // 遍历的这一行的fromNode
            Node fromNode = graph.nodes.get(fromId);
            // 遍历的这一行的toNode
            Node toNode = graph.nodes.get(toId);
            // 实例化边
            Edge edge = new Edge(weight,fromNode,toNode);

            // fromNode的出度加一
            fromNode.out++;
            // toNode的入度加一
            toNode.in++;
            // fromNode的nexts增加一个节点
            fromNode.nexts.add(toNode);
            // 从fromNode出发的边新增一个
            fromNode.edges.add(edge);
            // 图新增一条边
            graph.edges.add(edge);
        }
        return graph;
    }

    public static void main(String[] args) {
        Integer[][] m = { {1,1,2},{2,1,3},{3,2,3} };
        Graph g = FromMatrixToGraph(m);
        System.out.println(g.nodes);
        System.out.println(g.edges);
    }

}

运行结果：

1 2	{1=Node{id=1, in=0, out=2}, 2=Node{id=2, in=1, out=1}, 3=Node{id=3, in=2, out=0}} [Edge{weight=1, from=1, to=2}, Edge{weight=3, from=2, to=3}, Edge{weight=2, from=1, to=3}]

示例代码：

from Node_Edge_Graph import *


def from_matrix_to_graph(matrix):
    # 初始化图
    graph = Graph()
    # 遍历矩阵的行
    for i in range(0, len(matrix)):
        # 第一个数代表权重
        weight = matrix[i][0]
        # 第二个数代表from节点的Id
        from_id = matrix[i][1]
        # 第三个数代表to节点的Id
        to_id = matrix[i][2]
        # 如果图不包含fromId的节点，即这个节点从来没出现过
        if from_id not in graph.nodes.keys():
            # 把节点添加到图中
            node = Node(from_id)
            graph.nodes[from_id] = node
        # 如果图中不包含toId的节点，即这个节点从来没出现过
        if to_id not in graph.nodes.keys():
            # 把节点添加到图中
            node = Node(to_id)
            graph.nodes[to_id] = node
        # fromNode
        from_node = graph.nodes.get(from_id)
        # toNode
        to_node = graph.nodes.get(to_id)
        # 实例化边
        edge = Edge(weight, from_node, to_node)
        # fromNode的出度加一
        from_node.out_size = from_node.out_size + 1
        # toNode的入度加一
        to_node.in_size = to_node.in_size + 1
        # from_node的nexts增加一个节点
        from_node.nexts.append(to_node)
        # 从fromNode出发的边新增一个
        from_node.edges.append(edge)
        # 图新增一条边
        graph.edges.add(edge)
    return graph


if __name__ == '__main__':
    m = [[1, 1, 2], [2, 1, 3], [3, 2, 3]]
    g = from_matrix_to_graph(m)

    for n in g.nodes:
        print(g.nodes.get(n))

    for e in g.edges:
        print(e)

运行结果：

Node{id=1, in_size =0, out_size =2}
Node{id=2, in_size =1, out_size =1}
Node{id=3, in_size =2, out_size =0}
Edge{weight=1, from_node=1, to=2}
Edge{weight=2, from_node=1, to=3}
Edge{weight=3, from_node=2, to=3}

在讨论了图之后，我们开始讨论图的各种算法。而图作为一个综合的数据结构，在接下来，我们会重新见到我们之前讨论的各种数据结构在图算法中的应用。

图的遍历

我们讨论的第一个算法是图的遍历。
在二叉树那一章，我们已经讨论过遍历。前序、中序和后序遍历，同属于深度优先，此外，还有一个层序优先遍历，这个属于广度优先。
在图中，也有两种方式，深度优先和广度优先。

我们以这张无向图为例。

深度优先

对于深度优先：

从1出发，可以遍历2、4，比如2。
从2出发，可以遍历3、5，比如3。
从3出发，可以遍历6。
从6出发，可以遍历5、8，比如5。
从5出发，可以遍历4。
从4出发，回到5。
从5出发，遍历7。
从7出发，遍历8。

即：1、2、3、6、5、4、7、8

示例代码：

package ch10;

import java.util.HashSet;
import java.util.Stack;

// 深度优先遍历
public class DFS {

    /**
     * 深度优先
     * @param node 出发节点
     * @return
     */
    public static HashSet<Node> dfs(Node node){

        // 做一个是否为空的判断
        if (null == node){
            return null;
        }
        // 定义一个栈
        Stack<Node> stack = new Stack<>();
        // 用一个set来记录已经遍历过的节点
        HashSet<Node> set = new HashSet<>();
        // 进栈
        stack.add(node);
        // 记录
        set.add(node);
        // 打印
        System.out.println(node);
        while (!stack.empty()){
            // 栈，后进先出
            Node cur = stack.pop();
            // 遍历 next
            for (Node iter: cur.nexts){
                // 这个节点没有被遍历过
                if (!set.contains(iter)) {
                    // 把cur压回栈
                    stack.add(cur);
                    // 把当前节点压回栈
                    stack.add(iter);
                    // 记录
                    set.add(iter);
                    // 打印
                    System.out.println(iter);
                    // break，不再循环遍历，从iter出发
                    break;
                }
            }
        }
        return set;
    }

    public static void main(String[] args) {
        Integer[][] m = {
                         {null,1,2},{null,2,1},
                         {null,2,3},{null,3,2},
                         {null,1,4},{null,4,1},
                         {null,2,5},{null,5,2},
                         {null,3,6},{null,6,3},
                         {null,4,5},{null,5,4},
                         {null,5,6},{null,6,5},
                         {null,5,7},{null,7,5},
                         {null,6,8},{null,8,6},
                         {null,7,8},{null,8,7}
                        };
        Graph g = Converter.FromMatrixToGraph(m);
        HashSet<Node> set = dfs(g.nodes.get(1));
        System.out.println(set);
    }
}

运行结果：

Node{id=1, in=2, out=2}
Node{id=2, in=3, out=3}
Node{id=3, in=2, out=2}
Node{id=6, in=3, out=3}
Node{id=5, in=4, out=4}
Node{id=4, in=2, out=2}
Node{id=7, in=2, out=2}
Node{id=8, in=2, out=2}
[Node{id=3, in=2, out=2}, Node{id=7, in=2, out=2}, Node{id=8, in=2, out=2}, Node{id=5, in=4, out=4}, Node{id=6, in=3, out=3}, Node{id=4, in=2, out=2}, Node{id=2, in=3, out=3}, Node{id=1, in=2, out=2}]

示例代码：

from ch10 import Converter


def dfs(node):
    # 做一个是否为空的判断
    if node is None:
        return None
    # 定义一个栈
    # 我们用Python的list
    # append()表示入栈
    # pop()表示出栈
    stack = []
    # 用一个set来记录已经遍历过的节点
    s = set()
    # 进栈
    stack.append(node)
    # 记录
    s.add(node)
    # 打印
    print(node)
    while len(stack) > 0:
        # 栈，后进先出
        cur = stack.pop()
        # 遍历 next
        for iter in cur.nexts:
            # 这个节点没有被遍历过
            if iter not in s:
                # 把cur压回栈
                stack.append(cur)
                # 把当前节点压回栈
                stack.append(iter)
                # 记录
                s.add(iter)
                # 打印
                print(iter)
                # break，不再循环遍历，从iter出发
                break
    return s


if __name__ == '__main__':
    m = [[None, 1, 2], [None, 2, 1],
         [None, 2, 3], [None, 3, 2],
         [None, 1, 4], [None, 4, 1],
         [None, 2, 5], [None, 5, 2],
         [None, 3, 6], [None, 6, 3],
         [None, 4, 5], [None, 5, 4],
         [None, 5, 6], [None, 6, 5],
         [None, 5, 7], [None, 7, 5],
         [None, 6, 8], [None, 8, 6],
         [None, 7, 8], [None, 8, 7]]
    g = Converter.from_matrix_to_graph(m)
    s = dfs(g.nodes.get(1))
    print('-' * 20)
    for iter in s:
        print(iter)

运行结果：

Node{id=1, in_size =2, out_size =2}
Node{id=2, in_size =3, out_size =3}
Node{id=3, in_size =2, out_size =2}
Node{id=6, in_size =3, out_size =3}
Node{id=5, in_size =4, out_size =4}
Node{id=4, in_size =2, out_size =2}
Node{id=7, in_size =2, out_size =2}
Node{id=8, in_size =2, out_size =2}
--------------------
Node{id=5, in_size =4, out_size =4}
Node{id=7, in_size =2, out_size =2}
Node{id=3, in_size =2, out_size =2}
Node{id=2, in_size =3, out_size =3}
Node{id=4, in_size =2, out_size =2}
Node{id=1, in_size =2, out_size =2}
Node{id=6, in_size =3, out_size =3}
Node{id=8, in_size =2, out_size =2}

广度优先

对于广度优先：

从1出发，依次遍历2、4。
从2出发，依次遍历3、5。
从4出发，没有遍历。
从3出发，遍历6。
从5出发，遍历7。
从7出发，遍历8。

即：1、2、4、3、5、6、7、8。

示例代码：

package ch10;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class BFS {

    /**
     * 广度优先
     * @param node 出发节点
     * @return
     */
    public static HashSet<Node> bfs(Node node){
        // 做一个是否为空的判断
        if (null == node){
            return null;
        }
        // 定义一个队列
        Queue<Node> queue = new LinkedList<>();
        // 用一个set来记录已经遍历过的节点
        HashSet<Node> set = new HashSet<>();
        // 节点进入队列
        queue.add(node);
        // 节点添加进set
        set.add(node);
        // 打印
        System.out.println(node);
        // 只要队列不为空
        while (!queue.isEmpty()){
            // 队列是先进先出
            Node cur = queue.poll();
            // 遍历nexts
            for (Node iter : cur.nexts){
                if (!set.contains(iter)){
                    // 添加进队列，下次要从这个出发，进行遍历
                    queue.add(iter);
                    // 如果不在set中，说明之前没有遍历过，添加进set
                    set.add(iter);
                    // 打印
                    System.out.println(iter);
                }
            }
        }
        return set;
    }

    public static void main(String[] args) {
        Integer[][] m = {
                {null,1,2},{null,2,1},
                {null,2,3},{null,3,2},
                {null,1,4},{null,4,1},
                {null,2,5},{null,5,2},
                {null,3,6},{null,6,3},
                {null,4,5},{null,5,4},
                {null,5,6},{null,6,5},
                {null,5,7},{null,7,5},
                {null,6,8},{null,8,6},
                {null,7,8},{null,8,7}
        };
        Graph g = Converter.FromMatrixToGraph(m);
        HashSet<Node> set = bfs(g.nodes.get(1));
        System.out.println(set);
    }

}

运行结果：

Node{id=1, in=2, out=2}
Node{id=2, in=3, out=3}
Node{id=4, in=2, out=2}
Node{id=3, in=2, out=2}
Node{id=5, in=4, out=4}
Node{id=6, in=3, out=3}
Node{id=7, in=2, out=2}
Node{id=8, in=2, out=2}
[Node{id=4, in=2, out=2}, Node{id=7, in=2, out=2}, Node{id=8, in=2, out=2}, Node{id=5, in=4, out=4}, Node{id=3, in=2, out=2}, Node{id=6, in=3, out=3}, Node{id=2, in=3, out=3}, Node{id=1, in=2, out=2}]

示例代码：

from queue import Queue

from ch10 import Converter


def bfs(node):
    # 做一个是否为空的判断
    if node is None:
        return None
    # 定义一个队列
    q = Queue()
    # 用一个set来记录已经遍历过的节点
    s = set()
    # 节点进入队列
    q.put(node)
    # 节点添加进set
    s.add(node)
    # 打印
    print(node)
    # 只要队列不为空
    while not q.empty():
        # 队列是先进先出
        cur = q.get()
        # 遍历nexts
        for iter in cur.nexts:
            if iter not in s:
                # 添加进队列，下次要从这个出发，进行遍历
                q.put(iter)
                # 如果不在set中，说明之前没有遍历过，添加进set
                s.add(iter)
                # 打印
                print(iter)

    return s


if __name__ == '__main__':
    m = [[None, 1, 2], [None, 2, 1],
         [None, 2, 3], [None, 3, 2],
         [None, 1, 4], [None, 4, 1],
         [None, 2, 5], [None, 5, 2],
         [None, 3, 6], [None, 6, 3],
         [None, 4, 5], [None, 5, 4],
         [None, 5, 6], [None, 6, 5],
         [None, 5, 7], [None, 7, 5],
         [None, 6, 8], [None, 8, 6],
         [None, 7, 8], [None, 8, 7]]
    g = Converter.from_matrix_to_graph(m)
    s = bfs(g.nodes.get(1))
    print('-' * 20)
    for iter in s:
        print(iter)

运行结果：

Node{id=1, in_size =2, out_size =2}
Node{id=2, in_size =3, out_size =3}
Node{id=4, in_size =2, out_size =2}
Node{id=3, in_size =2, out_size =2}
Node{id=5, in_size =4, out_size =4}
Node{id=6, in_size =3, out_size =3}
Node{id=7, in_size =2, out_size =2}
Node{id=8, in_size =2, out_size =2}
--------------------
Node{id=4, in_size =2, out_size =2}
Node{id=8, in_size =2, out_size =2}
Node{id=6, in_size =3, out_size =3}
Node{id=7, in_size =2, out_size =2}
Node{id=2, in_size =3, out_size =3}
Node{id=3, in_size =2, out_size =2}
Node{id=5, in_size =4, out_size =4}
Node{id=1, in_size =2, out_size =2}

拓扑排序

在第二章，我们讨论的第一个数据结构数组之前，还专门讨论了算法和数据结构的关系。当时我们以蛋炒饭为例。我们说热锅、倒油、打蛋等，这些就是算法；而米饭、鸡蛋、油、盐就是数据结构。
现在，我们就来炒一份蛋炒饭。
如图，是我们做蛋炒饭的工序和工序之间的依赖关系。

即，加油依赖于热锅，加米饭依赖于加油，打个蛋依赖于加米饭，撒点葱花依赖于打个蛋，最后吃蛋炒饭依赖于加油、加米饭、打个蛋和撒点葱花。
那么？我们应该怎么合理的安排我们的工序呢？
我们先热锅，热锅之后我们加油，加油之后呢？吃蛋炒饭？反正我不吃。
我们这样，先遍历入度为0的节点，完成之后，把这个节点及从这个节点出发的边删除，然后遍历下一个入度为0的节点。

这就是拓扑排序。

我们用1、2、3、4、5、6，分别代表蛋炒饭的热锅、加油、加米饭、打个蛋、撒点葱花、吃蛋炒饭。以此为例，实现拓扑排序。

示例代码：

package ch10;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class TopologySort {

    /**
     * 拓扑排序
     * @param graph 进行排序的图
     * @return 排序后的节点
     */
    public static ArrayList<Node> topologySort(Graph graph){
        ArrayList<Node> rnt = new ArrayList<>();
        // 用一个Map，来记录所有的剩余入度
        HashMap<Node,Integer> inMap = new HashMap<>();
        // 入度为0的点，进入队列
        Queue<Node> zeroInQueue = new LinkedList<>();

        // 遍历节点
        for (Node iter: graph.nodes.values()) {
            // 记录初始阶段的所有节点及其入度
            inMap.put(iter,iter.in);
            // 如果该节点的入度是0
            if (iter.in == 0){
                // 加入队列
                zeroInQueue.add(iter);
            }
        }

        // 如果队列不为空
        while (!zeroInQueue.isEmpty()){
            // 队列，先进先出
            Node cur = zeroInQueue.poll();
            // 记录
            rnt.add(cur);
            // 遍历队列的nexts
            for (Node iter: cur.nexts) {
                // 入度减一
                inMap.put(iter,inMap.get(iter) - 1);
                // 如果入度等于0
                if (inMap.get(iter) == 0){
                    // 加入zeroInQueue队列
                    zeroInQueue.add(iter);
                }
            }
        }
        return rnt;
    }

    public static void main(String[] args) {
        Integer[][] m = {
                {null,1,2},
                {null,2,3},
                {null,3,4},
                {null,4,5},
                {null,2,6},
                {null,3,6},
                {null,4,6},
                {null,5,6}
        };
        Graph g = Converter.FromMatrixToGraph(m);
        ArrayList<Node> list = topologySort(g);
        System.out.println(list);
    }
}

运行结果：

1	[Node{id=1, in=0, out=1}, Node{id=2, in=1, out=2}, Node{id=3, in=1, out=2}, Node{id=4, in=1, out=2}, Node{id=5, in=1, out=1}, Node{id=6, in=4, out=0}]

示例代码：

from queue import Queue

from ch10 import Converter


def topologySort(graph):
    rnt = []
    # 用一个Dict，来记录所有的剩余入度
    in_dict = dict()
    # 入度为0的点，进入队列
    zero_in_queue = Queue()
    # 遍历节点
    for iter_key in graph.nodes:
        iter = graph.nodes.get(iter_key)
        # 记录初始阶段的所有节点及其入度
        in_dict[iter] = iter.in_size
        # 如果该节点的入度是0
        if iter.in_size == 0:
            # 加入队列
            zero_in_queue.put(iter)

    # 如果队列不为空
    while not zero_in_queue.empty():
        # 队列，先进先出
        cur = zero_in_queue.get()
        # 记录
        rnt.append(cur)
        # 遍历队列的nexts
        for iter in cur.nexts:
            # 入度减一
            in_dict[iter] = in_dict.get(iter) - 1
            # 如果入度等于0
            if in_dict.get(iter) == 0:
                zero_in_queue.put(iter)
    return rnt


if __name__ == '__main__':
    m = [[None, 1, 2],
         [None, 2, 3],
         [None, 3, 4],
         [None, 4, 5],
         [None, 2, 6],
         [None, 3, 6],
         [None, 4, 6],
         [None, 5, 6]]
    g = Converter.from_matrix_to_graph(m)
    l = topologySort(g)
    for iter in l:
        print(iter)

运行结果：

Node{id=1, in_size =0, out_size =1}
Node{id=2, in_size =1, out_size =2}
Node{id=3, in_size =1, out_size =2}
Node{id=4, in_size =1, out_size =2}
Node{id=5, in_size =1, out_size =1}
Node{id=6, in_size =4, out_size =0}

特别的，如果我们养了猫呢？而且这猫还特别喜欢在锅里。

那么蛋炒饭的工序就是：首先，把猫从锅里赶出去，洗锅，把锅放好，再把猫从锅里赶出去，再洗锅，再把把锅放好，第三次把猫从锅里赶出去，第三次洗锅······，点个外卖。

即，出现了环，无法进行拓扑排序。

拓扑排序在计算机方面最常见的一个应用就是编译过程，而出现了环就无法进行拓扑排序，任务无法进行。这也是我们写代码不要循环依赖的原因。

并查集

在电影《我不是潘金莲》中有一幕特别有意思，就是影片开头李雪莲第一次见王公道的时候。

王公道和陈阿大是亲戚
陈阿大和陈阿大他老婆的妹妹是亲戚
陈阿大他老婆的的妹妹和陈阿大他老婆的妹妹的婆家是亲戚
陈阿大他老婆的妹妹的婆家和陈阿大他老婆的妹妹的婆家的叔伯侄子是亲戚
······

总之，最后，李雪莲和王公道是亲戚。

过程

那么，在上述过程中，李雪莲主要做的事情有：

合并(Union)：把两个不相交的集合合并为一个集合。
查询(Find)：查询两个元素是否在同一个集合中。

合并，查找，这也就是并查集名字的由来，而这两个方法就是并查集的核心方法。
这两件事情其实很好理解，但是为了提高效率，我们可以在具体实现中，每个集合设置一位代表。这样的话，我们判断两个元素是否在同一个集合中，只需要看代表是不是同一位；把两个不相交的集合合并为一个集合，也只需要把其中小集合的代表换掉就够了。

我们举个例子。
现在我们有1、2、3、4、5、6，他们每个人都是独立的个体，一个人就是一个家族，这个家族的代表就是他们自己。

然后，我们发现，原来1和3是亲戚，那么1和3合并成一个新的家族之后，谁是代表呢？
两个家族一样大，谁是代表又有什么区别呢？随便选一个，1是代表。

接下来，我们发现2和3也是亲戚，那么，又可以合并成一个新的家族了。这时候谁是代表呢？
这就有讲究了，大家族的代表继续作为代表。

直到最后，李雪莲和王公道就是亲戚了。

实现

过程就是这么一个过程，在具体实现中，我们还可以做一些简单的优化，大家特别注意我们的find_top()。
实施扁平化，这样提高以后find_top()的效率。

示例代码：

package ch10;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class UnionFindExample {

    // 节点
    public static class Node<V> {
        V value;
        public Node(V v) {
            value = v;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    // 并查集
    public static class UnionFind<V> {
        // 并查集中的所有节点
        public HashMap<V, Node<V>> nodes;
        // 节点和节点之间的UP关系
        public HashMap<Node<V>, Node<V>> ups;
        // 家族的大小
        public HashMap<Node<V>, Integer> sizeMap;

        /**
         * 构造方法
         * @param values
         */
        public UnionFind(List<V> values) {
            nodes = new HashMap<>();
            ups = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node);
                // 一开始自己就是一个家族，那么自己就是自己的UP
                ups.put(node, node);
                // 大小就是1
                sizeMap.put(node, 1);
            }
        }

        // 找家族的大代表
        public Node<V> findTop(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            // 只要自己不是自己的代表，就一直网上找
            while (cur != ups.get(cur)) {
                path.push(cur);
                cur = ups.get(cur);
            }
            while (!path.isEmpty()) {
                ups.put(path.pop(), cur);
            }
            return cur;
        }

        /**
         * 是否是同一个集合 查
         * @param a
         * @param b
         * @return
         */
        public boolean isSameSet(V a, V b) {
            // 看看TOP代表是不是同一位
            return findTop(nodes.get(a)) == findTop(nodes.get(b));
        }

        /**
         * 两个集合合并 并
         * @param a
         * @param b
         */
        public void union(V a, V b) {
            // a节点的家族的代表
            Node<V> aHead = findTop(nodes.get(a));
            // b节点的家族的代表
            Node<V> bHead = findTop(nodes.get(b));
            // 如果代表不是同一位，合并
            if (aHead != bHead) {
                // a家族的大小
                int aSetSize = sizeMap.get(aHead);
                // b家族的大小
                int bSetSize = sizeMap.get(bHead);
                // 如果a家族大于等于b家族
                if (aSetSize >= bSetSize){
                    // 直接把b家族的代表的代表设置为a家族的代表
                    ups.put(bHead,aHead);
                    // 家族的大小
                    sizeMap.put(aHead,aSetSize + bSetSize);
                    // 一个家族，一个代表，一个大小
                    sizeMap.remove(bHead);
                }else{
                    // 把if反过来就是else
                    ups.put(aHead,bHead);
                    sizeMap.put(bHead,aSetSize + bSetSize);
                    sizeMap.remove(aHead);
                }
            }
        }

    }


    public static void main(String[] args) {
        List<Integer> l = new ArrayList<>();
        l.add(1);
        l.add(2);
        l.add(3);
        l.add(4);
        l.add(5);
        l.add(6);
        UnionFind<Integer> unionFind = new UnionFind<Integer>(l);
        System.out.println(unionFind.nodes);
        System.out.println(unionFind.ups);
        System.out.println(unionFind.sizeMap);
        System.out.println(unionFind.isSameSet(1,2));
        unionFind.union(1,2);
        System.out.println(unionFind.isSameSet(1,2));
        System.out.println(unionFind.nodes);
        System.out.println(unionFind.ups);
        System.out.println(unionFind.sizeMap);
    }
}

运行结果：

{1=Node{value=1}, 2=Node{value=2}, 3=Node{value=3}, 4=Node{value=4}, 5=Node{value=5}, 6=Node{value=6}}
{Node{value=1}=Node{value=1}, Node{value=4}=Node{value=4}, Node{value=5}=Node{value=5}, Node{value=3}=Node{value=3}, Node{value=2}=Node{value=2}, Node{value=6}=Node{value=6}}
{Node{value=1}=1, Node{value=4}=1, Node{value=5}=1, Node{value=3}=1, Node{value=2}=1, Node{value=6}=1}
false
true
{1=Node{value=1}, 2=Node{value=2}, 3=Node{value=3}, 4=Node{value=4}, 5=Node{value=5}, 6=Node{value=6}}
{Node{value=1}=Node{value=1}, Node{value=4}=Node{value=4}, Node{value=5}=Node{value=5}, Node{value=3}=Node{value=3}, Node{value=2}=Node{value=1}, Node{value=6}=Node{value=6}}
{Node{value=1}=2, Node{value=4}=1, Node{value=5}=1, Node{value=3}=1, Node{value=6}=1}

示例代码：

class Node:
    def __init__(self, v):
        self.value = v

    def __str__(self):
        return str(self.value)


class UnionFind:
    def __init__(self, values):
        # 并查集中的所有节点
        self.nodes = dict()
        # 节点和节点之间的UP关系
        self.ups = dict()
        # 家族的大小
        self.size_map = dict()
        for iter in values:
            node = Node(iter)
            self.nodes[iter] = node
            # 一开始自己就是一个家族，那么自己就是自己的UP
            self.ups[node] = node
            # 大小就是1
            self.size_map[node] = 1

    def find_top(self, cur):
        # 定义一个栈
        # 我们用Python的list
        # append()表示入栈
        # pop()表示出栈
        path = []
        while cur is not self.ups.get(cur):
            path.append(cur)
            cur = self.ups.get(cur)
        while len(path) > 0:
            self.ups[path.pop()] = cur
        return cur

    def is_same_set(self, a, b):
        """
        是否是同一个集合 查
        :param a:
        :param b:
        :return:
        """
        return self.find_top(self.nodes.get(a)) == self.find_top(self.nodes.get(b))

    def union(self, a, b):
        # a节点的家族的代表
        a_head = self.find_top(self.nodes.get(a))
        # b节点的家族的代表
        b_head = self.find_top(self.nodes.get(b))
        if a_head is not b_head:
            # a家族的大小
            a_set_size = self.size_map.get(a_head)
            # b家族的大小
            b_set_size = self.size_map.get(b_head)
            if a_set_size >= b_set_size:
                self.ups[b_head] = a_head
                # 家族的大小
                self.size_map[a_head] = a_set_size + b_set_size
                # 一个家族，一个代表，一个大小
                self.size_map.pop(b_head)
            else:
                self.ups[a_head] = b_head
                # 家族的大小
                self.size_map[b_head] = a_set_size + b_set_size
                # 一个家族，一个代表，一个大小
                self.size_map.pop(a_head)


if __name__ == '__main__':
    unionFind = UnionFind([1, 2, 3, 4, 5, 6])
    for iter in unionFind.nodes:
        print(iter, unionFind.nodes.get(iter))
    print('-' * 10)
    for iter in unionFind.ups:
        print(iter, unionFind.ups.get(iter))
    print('-' * 10)
    for iter in unionFind.size_map:
        print(iter, unionFind.size_map.get(iter))
    print('-' * 10)

    print(unionFind.is_same_set(1, 2))
    unionFind.union(1, 2)
    print(unionFind.is_same_set(1, 2))

    for iter in unionFind.nodes:
        print(iter, unionFind.nodes.get(iter))
    print('-' * 10)
    for iter in unionFind.ups:
        print(iter, unionFind.ups.get(iter))
    print('-' * 10)
    for iter in unionFind.size_map:
        print(iter, unionFind.size_map.get(iter))

运行结果：

1 1
2 2
3 3
4 4
5 5
6 6
----------
1 1
2 2
3 3
4 4
5 5
6 6
----------
1 1
2 1
3 1
4 1
5 1
6 1
----------
False
True
1 1
2 2
3 3
4 4
5 5
6 6
----------
1 1
2 1
3 3
4 4
5 5
6 6
----------
1 2
3 1
4 1
5 1
6 1

通过代码，我们可以发现，我们每调用一次find_top()都会把该链路打平，那么find_top()调用的越频繁，复杂度越低。
如果有 $n$ 个节点，当find_top()的调用次数达到或者超过 $O(n)$ 时，find_top()的时间复杂度是 $O(1)$ 。

接下来我们就会见识到并查集的作用。

最小生成树

金庸先生还有一部小说《笑傲江湖》。在这部小说中，推动剧情发展的一个主要矛盾是五岳剑派的合并。
我们知道在小说最后，五岳剑派合并失败了，失败的原因有很多，我认为其中一个原因是各门派之间相隔甚远，沟通交流不方便。为了解决这个问题，在五岳剑派合并这件宏大的工程中，其中必不可少的一个环节是修路。

如图，是五岳剑派所处的位置，和之间的修路所需要花费的黄金(单位万两)。
现在问，修哪几条路，可以把五岳剑派连通起来，并且成本最小？
这就是最小生成树。

这里，我们讨论两种方案：

Kruskal
Prim

这两种算法都属于贪心算法

Kruskal

过程

首先，我们把所有的路，根据成本从小到大排序。所以，我们有：

路名	From	To	成本
华嵩路	华山	嵩山	2
恒泰路	恒山	泰山	5
嵩泰路	嵩山	泰山	10
嵩恒路	嵩山	恒山	20
嵩衡路	衡山	衡山	20
华恒路	华山	恒山	50
华衡路	华山	衡山	100

我们从成本最小的路开始修，华嵩路，连通集合有：

$\{\text{华山},\text{嵩山}\}$

然后再修恒泰路，恒山和泰山都不在连通集合中，所以这时候连通集合有两个有：

$\{\text{华山},\text{嵩山}\},\{\text{恒山},\text{泰山}\}$

再修嵩泰路。嵩山和泰山都在连通集合中，但是各自在不同的集合中。所以这条路修。这时候得到的连通集合有

$\{\text{华山},\text{嵩山},\text{恒山},\text{泰山}\}$

那么嵩恒路修不修，不修。因为嵩山和恒山在同一个连通集合中。
那嵩衡路呢？修，因为衡山不在连通集合中。
这时候得到的连通集合有

$\{\text{华山},\text{嵩山},\text{恒山},\text{泰山},\text{衡山}\}$

需要修的路有

$\{\text{华嵩路},\text{恒泰路},\text{嵩泰路},\text{嵩衡路}\}$

这个算法叫做Kruskal。

特点如下：

每次都从权值最小的边开始考虑
当前考虑的边要么进入最小生成树的集合，要么丢弃。
如果当前考虑的边进入最小生成树的集合中不会形成环，就要当前考虑的边。
如果当前考虑的边计入最小生成树的集合中会形成环，就不要当前考虑的边。
考察完所有边之后，最小生成树的集合也得到了。

实现

在具体实现中，我们就会见到之前讨论的并查集的作用了。
过程就是：
把所有的边，按照权重从小到大排序，做并查集。

示例代码：

package ch10;

import java.util.*;

public class Kruskal {

    public static class UnionFind {
        // key 某一个节点， value key节点往上的节点
        private HashMap<Node, Node> upsMap;
        // key 某一个集合的代表节点, value key所在集合的节点个数
        private HashMap<Node, Integer> sizeMap;

        public UnionFind(Collection<Node> nodes) {
            upsMap = new HashMap<Node, Node>();
            sizeMap = new HashMap<Node, Integer>();
            for (Node node : nodes) {
                upsMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        private Node findTop(Node n) {
            Stack<Node> path = new Stack<>();
            while (n != upsMap.get(n)) {
                path.add(n);
                n = upsMap.get(n);
            }
            while (!path.isEmpty()) {
                upsMap.put(path.pop(), n);
            }
            return n;
        }

        public boolean isSameSet(Node a, Node b) {
            return findTop(a) == findTop(b);
        }

        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aDai = findTop(a);
            Node bDai = findTop(b);
            if (aDai != bDai) {
                int aSetSize = sizeMap.get(aDai);
                int bSetSize = sizeMap.get(bDai);
                if (aSetSize <= bSetSize) {
                    upsMap.put(aDai, bDai);
                    sizeMap.put(bDai, aSetSize + bSetSize);
                    sizeMap.remove(aDai);
                } else {
                    upsMap.put(bDai, aDai);
                    sizeMap.put(aDai, aSetSize + bSetSize);
                    sizeMap.remove(bDai);
                }
            }
        }
    }

    public static class EdgeComparator implements Comparator<Edge> {
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    public static Set<Edge> kruskal(Graph graph) {
        UnionFind unionFind = new UnionFind(graph.nodes.values());
        // 从小的边到大的边，依次弹出，小根堆！
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        for (Edge edge : graph.edges) { // M 条边
            priorityQueue.add(edge);  // O(logM)
        }
        Set<Edge> result = new HashSet<>();
        while (!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll();
            if (!unionFind.isSameSet(edge.from, edge.to)) {
                result.add(edge);
                unionFind.union(edge.from, edge.to);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 1 恒山
        // 2 华山
        // 3 嵩山
        // 4 泰山
        // 5 衡山
        Integer[][] m = {
                {50, 1, 2}, {50, 2, 1},
                {20, 1, 3}, {20, 3, 1},
                {10, 1, 4}, {10, 4, 1},
                {2, 2, 3}, {2, 3, 2},
                {5, 3, 4}, {5, 4, 3},
                {100, 2, 5}, {100, 5, 2},
                {20, 4, 5}, {20, 5, 4}};
        Graph g = Converter.FromMatrixToGraph(m);
        System.out.println(Kruskal.kruskal(g));
    }

}

运行结果：

1	[Edge{weight=2, from=3, to=2}, Edge{weight=10, from=1, to=4}, Edge{weight=20, from=4, to=5}, Edge{weight=5, from=4, to=3}]

示例代码：

import heapq

from ch10 import Converter


class UnionFind:

    def __init__(self, nodes):
        # key:某一个节点， value:key节点往上的节点
        self.ups_map = dict()
        # key某一个集合的代表节点, value:key所在集合的节点个数
        self.size_map = dict()
        for iter in nodes:
            node = nodes[iter]
            # 一开始自己就是一个家族，那么自己就是自己的UP
            self.ups_map[node] = node
            # 大小就是1
            self.size_map[node] = 1

    def find_top(self, n):
        # 定义一个栈
        # 我们用Python的list
        # append()表示入栈
        # pop()表示出栈
        path = []
        while n is not self.ups_map[n]:
            path.append(n)
            n = self.ups_map[n]
        while len(path) > 0:
            self.ups_map[path.pop()] = n
        return n

    def is_same_set(self, a, b):
        return self.find_top(a) == self.find_top(b)

    def union(self, a, b):
        if a is None and b is None:
            return
        a_dai = self.find_top(a)
        b_dai = self.find_top(b)
        if a_dai != b_dai:
            a_set_size = self.size_map[a_dai]
            b_set_size = self.size_map[b_dai]
            if a_set_size <= b_set_size:
                self.ups_map[a_dai] = b_dai
                self.size_map[b_dai] = a_set_size + b_set_size
                self.size_map.pop(a_dai)
            else:
                self.ups_map[b_dai] = a_dai
                self.size_map[a_dai] = a_set_size + b_set_size
                self.size_map.pop(b_dai)


def kruskal(graph):
    unionFind = UnionFind(graph.nodes)
    # 从小的边到大的边，依次弹出，小根堆！
    p = []
    for edge in graph.edges:
        heapq.heappush(p, edge)
    result = set()
    while len(p) > 0:
        edge = heapq.heappop(p)
        if not unionFind.is_same_set(edge.from_node, edge.to_node):
            result.add(edge)
            unionFind.union(edge.from_node, edge.to_node)
    return result


if __name__ == '__main__':
    # 1 恒山
    # 2 华山
    # 3 嵩山
    # 4 泰山
    # 5 衡山
    m = [[50, 1, 2], [50, 2, 1],
         [20, 1, 3], [20, 3, 1],
         [10, 1, 4], [10, 4, 1],
         [2, 2, 3], [2, 3, 2],
         [5, 3, 4], [5, 4, 3],
         [100, 2, 5], [100, 5, 2],
         [20, 4, 5], [20, 5, 4]]
    g = Converter.from_matrix_to_graph(m)
    r = kruskal(g)
    for iter in r:
        print(iter)

运行结果：

Edge{weight=2, from_node=3, to=2}
Edge{weight=10, from_node=4, to=1}
Edge{weight=5, from_node=4, to=3}
Edge{weight=20, from_node=5, to=4}

Prim

过程

刚刚我们的修路方案是先修成本最小的路，这样先联通的华山和嵩山，但是其他门派不答应了，为了掌握修路的控制权，纷纷表示要先修自己家门口的路。
那怎么办？
抓阄吧，随机选一个门派开始吧。
这就是Prim算法。
比如我们从泰山派开始。
已连通的门派有：

$\{\text{泰山}\}$

在泰山的可控范围内，可以修的路有：

$\{\text{恒泰路},\text{嵩泰路}\}$

我们选择最便宜的一条路：嵩泰路。
这时候，已连通的门派有：

$\{\text{泰山},\text{嵩山}\}$

在泰山的可控范围内，可以修的路有：

$\{\text{恒泰路},\text{华嵩路},\text{嵩恒路},\text{嵩衡路}\}$

再选择最便宜的一条路：华嵩路。
这时候，已连通的门派有：

$\{\text{泰山},\text{嵩山},\text{华山}\}$

在华山的可控范围内，可以修的路有：

$\{\text{恒泰路},\text{嵩恒路},\text{嵩衡路},\text{华恒路},\text{嵩衡路}\}$

如此循环，得到最小生成树。

这个算法有没有问题？
我们来看这么一个情况。

假如在图中就存在本来就无法联通的点呢？
这种情况，如果我们随机选择的点是A，那么D,E，G,H,I,K都无法处理。
那怎么办？
这时候，一个For循环遍历所有的点，就可以搞定。我们来看具体实现。

实现

示例代码：

package ch10;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Prim {

    public static class EdgeComparator implements Comparator<Edge> {
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    public static Set<Edge> prim(Graph graph) {
        // 选择的边
        Set<Edge> rnt = new HashSet<>();
        // 解锁的边进入小根堆
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        // 被解锁的点
        HashSet<Node> nodeSet = new HashSet<>();
        // 被解锁过的边
        Set<Edge> edgeSet = new HashSet<>();
        // 遍历所有的点
        for (Node node : graph.nodes.values()) {
            // node 是开始点
            if (!nodeSet.contains(node)) {
                nodeSet.add(node);
                // 由一个点，解锁所有相连的边
                for (Edge edge : node.edges) {
                    if (!edgeSet.contains(edge)) {
                        edgeSet.add(edge);
                        priorityQueue.add(edge);
                    }
                }
                while (!priorityQueue.isEmpty()) {
                    // 弹出解锁的边中，最小的边
                    Edge edge = priorityQueue.poll();
                    // 可能的一个新的点
                    Node toNode = edge.to;
                    // 不含有的时候，就是新的点
                    if (!nodeSet.contains(toNode)) {
                        nodeSet.add(toNode);
                        rnt.add(edge);
                        for (Edge nextEdge : toNode.edges) {
                            if (!edgeSet.contains(nextEdge)) {
                                edgeSet.add(nextEdge);
                                priorityQueue.add(nextEdge);
                            }
                        }
                    }
                }
            }
        }
        return rnt;
    }

    public static void main(String[] args) {
        // 1 恒山
        // 2 华山
        // 3 嵩山
        // 4 泰山
        // 5 衡山
        Integer[][] m = {
                {50, 1, 2}, {50, 2, 1},
                {20, 1, 3}, {20, 3, 1},
                {10, 1, 4}, {10, 4, 1},
                {2, 2, 3}, {2, 3, 2},
                {5, 3, 4}, {5, 4, 3},
                {100, 2, 5}, {100, 5, 2},
                {20, 4, 5}, {20, 5, 4}};
        Graph g = Converter.FromMatrixToGraph(m);
        System.out.println(Prim.prim(g));
    }

}

运行结果：

1	[Edge{weight=2, from=3, to=2}, Edge{weight=10, from=1, to=4}, Edge{weight=20, from=4, to=5}, Edge{weight=5, from=4, to=3}]

示例代码：

import heapq

from ch10 import Converter


def prim(graph):
    # 选择的边
    rnt = set()
    # 解锁的边进入小根堆
    p = []
    # 被解锁的点
    node_set = set()
    # 被解锁过的边
    edge_set = set()
    # 遍历所有的点
    for iter in graph.nodes:
        node = graph.nodes[iter]
        # node 是开始点
        if node not in node_set:
            node_set.add(node)
            # 由一个点，解锁所有相连的边
            for edge in node.edges:
                if edge not in edge_set:
                    edge_set.add(edge)
                    heapq.heappush(p, edge)
            while len(p) > 0:
                # 弹出解锁的边中，最小的边
                edge = heapq.heappop(p)
                # 可能的一个新的点
                to_node = edge.to_node
                # 不含有的时候，就是新的点
                if to_node not in node_set:
                    node_set.add(to_node)
                    rnt.add(edge)
                    for next_edge in to_node.edges:
                        if next_edge not in edge_set:
                            edge_set.add(next_edge)
                            heapq.heappush(p, next_edge)
    return rnt


if __name__ == '__main__':
    # 1 恒山
    # 2 华山
    # 3 嵩山
    # 4 泰山
    # 5 衡山
    m = [[50, 1, 2], [50, 2, 1],
         [20, 1, 3], [20, 3, 1],
         [10, 1, 4], [10, 4, 1],
         [2, 2, 3], [2, 3, 2],
         [5, 3, 4], [5, 4, 3],
         [100, 2, 5], [100, 5, 2],
         [20, 4, 5], [20, 5, 4]]
    g = Converter.from_matrix_to_graph(m)
    r = prim(g)
    for iter in r:
        print(iter)

运行结果：

Edge{weight=5, from_node=4, to=3}
Edge{weight=2, from_node=3, to=2}
Edge{weight=10, from_node=1, to=4}
Edge{weight=20, from_node=4, to=5}

Dijkstra

过程

现在我们的路已经修好了，为了方便五岳剑派的各位弟子出行，我们修的还是路网。新的地图如下：

其中不同的数字，代表的是这条路需要多少天。当然天数肯定不会是负数，即边的权值必须大于0，这就是Dijkstra的前提。
那么，问，我们要从华山派到其它门派的最快方法是什么？这就是Dijkstra所要解决的问题。

首先，我们从华山派可以去恒山派、嵩山派和衡山派，其距离分别为3、1、9，无法直接达到泰山派。

华山	嵩山	泰山	恒山	衡山
$\widehat{\bold{0}}$	1	$\infty$	3	9

粗体字并戴帽子表示已经确定了的天数，不修改，下同。

那么，从华山去哪座山的距离最小呢？嵩山。我们从华山出发，经由嵩山，还可以去恒山派、泰山派和衡山派，距离分别是1+1、1+5、1+2。所以，我们更新上面的表格

华山	嵩山	泰山	恒山	衡山
$\widehat{\bold{0}}$	$\widehat{\bold{1}}$	6	2	3

那么在剩下的三座山中，最方便的恒山，我们从华山出发，经由恒山之后，可以去泰山，距离是2+2。所以，我们更新上面的表格

华山	嵩山	泰山	恒山	衡山
$\widehat{\bold{0}}$	$\widehat{\bold{1}}$	4	$\widehat{\bold{2}}$	3

那么在剩下的两座山中，最方便的衡山，我们从华山出发，经由衡山之后，也可以去泰山，距离是3+6。所以，对于上面的表格，我们不更新。

华山	嵩山	泰山	恒山	衡山
$\widehat{\bold{0}}$	$\widehat{\bold{1}}$	4	$\widehat{\bold{2}}$	$\widehat{\bold{3}}$

最后

华山	嵩山	泰山	恒山	衡山
$\widehat{\bold{0}}$	$\widehat{\bold{1}}$	$\widehat{\bold{4}}$	$\widehat{\bold{2}}$	$\widehat{\bold{3}}$

实现

示例代码：

package ch10;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

public class Dijkstra {

    /**
     * Dijkstra 算法
     *
     * @param from from节点
     * @return from节点到其他节点的距离，表格
     */
    public static HashMap<Node, Integer> dijkstra(Node from) {
        // 最后要返回的表，记录从from节点到其他节点的最小距离
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        // 从from节点到from节点的距离为0
        distanceMap.put(from, 0);
        // 已经求过距离的节点，放在recordNodes中，登记
        HashSet<Node> recordNodes = new HashSet<>();

        // 找到在未登记的节点中，距离最小的节点
        Node minNode = getMinDistanceInUnrecordedNode(distanceMap, recordNodes);
        // 如果minNode不是空的，说明找到了距离最小点
        while (minNode != null) {
            // 获取距离
            Integer distance = distanceMap.get(minNode);
            // 遍历距离最小点的边
            for (Edge edge : minNode.edges) {
                // 边的to节点
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    // 如果to节点不在distanceMap中
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    // 否则记录
                    distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            // 登记
            recordNodes.add(minNode);
            // 循环
            minNode = getMinDistanceInUnrecordedNode(distanceMap, recordNodes);
        }
        return distanceMap;
    }

    /**
     * 在未登记的节点中，找距离最小的节点
     *
     * @param distanceMap 距离表
     * @param recordNodes 登记节点
     * @return
     */
    public static Node getMinDistanceInUnrecordedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> recordNodes) {
        // 距离最小的节点
        Node minNode = null;
        // 最小距离，一开始初始化未最大值
        Integer minDistance = Integer.MAX_VALUE;
        // 遍历距离表
        for (Entry<Node, Integer> iter : distanceMap.entrySet()) {
            // iter 节点
            Node node = iter.getKey();
            // iter 距离
            Integer distance = iter.getValue();
            // 如果这个节点没有登记，并且距离比minDistance还要小
            if (!recordNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    public static void main(String[] args) {
        // 1 恒山
        // 2 华山
        // 3 嵩山
        // 4 泰山
        // 5 衡山
        Integer[][] m = {
                {3, 1, 2}, {3, 2, 1},
                {1, 1, 3}, {1, 3, 1},
                {2, 1, 4}, {2, 4, 1},
                {1, 2, 3}, {1, 3, 2},
                {5, 3, 4}, {5, 4, 3},
                {9, 2, 5}, {9, 5, 2},
                {2, 3, 5}, {2, 5, 3},
                {6, 4, 5}, {6, 5, 4}};
        Graph g = Converter.FromMatrixToGraph(m);
        // 从华山派出发
        System.out.println(dijkstra(g.nodes.get(2)));
    }
}

运行结果：

1	{Node{id=2, in=3, out=3}=0, Node{id=1, in=3, out=3}=2, Node{id=3, in=4, out=4}=1, Node{id=5, in=3, out=3}=3, Node{id=4, in=3, out=3}=4}

示例代码：

import sys

from ch10 import Converter


def dijkstra(from_node):
    # 最后要返回的表，记录从from节点到其他节点的最小距离
    distance_dict = dict()
    # 从from节点到from节点的距离为0
    distance_dict[from_node] = 0
    # 已经求过距离的节点，放在recordNodes中，登记
    record_nodes = set()
    # 找到在未登记的节点中，距离最小的节点
    min_node = get_min_distance_in_unrecorded_node(distance_dict, record_nodes)
    # 如果minNode不是空的，说明找到了距离最小点
    while min_node is not None:
        # 获取距离
        distance = distance_dict[min_node]
        # 遍历距离最小点的边
        for edge in min_node.edges:
            # 边的to节点
            to_node = edge.to_node
            if to_node not in distance_dict:
                # 如果to节点不在distanceMap中
                distance_dict[to_node] = distance + edge.weight
            else:
                # 否则记录
                distance_dict[edge.to_node] = min(distance_dict[to_node], distance + edge.weight)

        # 登记
        record_nodes.add(min_node)
        # 循环
        min_node = get_min_distance_in_unrecorded_node(distance_dict, record_nodes)

    return distance_dict


def get_min_distance_in_unrecorded_node(distance_dict, record_nodes):
    # 距离最小的节点
    min_node = None
    # 最小距离，一开始初始化未最大值
    min_distance = sys.maxsize
    # 遍历距离表
    for iter in distance_dict:
        # 节点
        # 距离
        distance = distance_dict[iter]
        # 如果这个节点没有登记，并且距离比minDistance还要小
        if iter not in record_nodes and distance < min_distance:
            min_node = iter
            min_distance = distance

    return min_node


if __name__ == '__main__':
    # 1 恒山
    # 2 华山
    # 3 嵩山
    # 4 泰山
    # 5 衡山
    m = [[3, 1, 2], [3, 2, 1],
         [1, 1, 3], [1, 3, 1],
         [2, 1, 4], [2, 4, 1],
         [1, 2, 3], [1, 3, 2],
         [5, 3, 4], [5, 4, 3],
         [9, 2, 5], [9, 5, 2],
         [2, 3, 5], [2, 5, 3],
         [6, 4, 5], [6, 5, 4]]
    g = Converter.from_matrix_to_graph(m)
    # 从华山派出发
    r = dijkstra(g.nodes.get(2))
    for i in r:
        print(i, r[i])

运行结果：

Node{id=2, in_size =3, out_size =3} 0
Node{id=1, in_size =3, out_size =3} 2
Node{id=3, in_size =4, out_size =4} 1
Node{id=5, in_size =3, out_size =3} 3
Node{id=4, in_size =3, out_size =3} 4

文章作者: Kaka Wan Yifan

文章链接: https://kakawanyifan.com/10610

留言板