数据结构模板，所有需要用图解决的问题都先转化为以下数据结构，然后处理。

节点

  1. public class Node {
  2.     public int value; // 当前点的值
  3.     public int in; // 入度数
  4.     public int out; // 出度数
  5.     public ArrayList<Node> nexts; // 出度点集
  6.     public ArrayList<Edge> edges; // 出度边
  8.     public Node(int value) {
  9.         this.value = value;
  10.         in = 0;
  11.         out = 0;
  12.         nexts = new ArrayList<>();
  13.         edges = new ArrayList<>();
  14.     }
  15. }

边

  1. public class Edge {
  2.     public int weight; // 权重
  3.     public Node from; // 开始点
  4.     public Node to; // 结束点
  6.     public Edge(int weight, Node from, Node to) {
  7.         this.weight = weight;
  8.         this.from = from;
  9.         this.to = to;
  10.     }
  11. }

图

  1. public class Graph {
  2.     // 所有的点信息
  3.     // key是编号，value是点
  4.     public HashMap<Integer, Node> nodes;
  5.     // 所有的边信息
  6.     public HashSet<Edge> edges;
  8.     public Graph() {
  9.         nodes = new HashMap<>();
  10.         edges = new HashSet<>();
  11.     }
  12. }

创建图

  1. public class GraphGenerator {
  2.     /**
  3.      * matrix所有的边
  4.      * 假如是N * 3的矩阵，那么有：
  5.      * [weight, from节点上面的值，to节点上面的值]
  6.      * [5, 0, 7]
  7.      * [3, 0, 1]
  8.      */
  9.     public static Graph createGraph(int[][] matrix) {
  10.         Graph graph = new Graph();
  11.         for (int i = 0; i < matrix.length; i++) {
  12.             // 拿到每条边，matrix[i]
  13.             int weight = matrix[i][0];
  14.             int from = matrix[i][1];
  15.             int to = matrix[i][2];
  16.             // 如果图中不包含节点，则加入到图中
  17.             if (!graph.nodes.containsKey(from)) {
  18.                 graph.nodes.put(from, new Node(from));
  19.             }
  20.             if (!graph.nodes.containsKey(to)) {
  21.                 graph.nodes.put(to, new Node(to));
  22.             }
  24.             Node fromNode = graph.nodes.get(from);
  25.             Node toNode = graph.nodes.get(to);
  26.             // 设置边
  27.             Edge newEdge = new Edge(weight, fromNode, toNode);
  28.             // 设置出度点
  29.             fromNode.nexts.add(toNode);
  30.             fromNode.out++; // 出度数+1
  31.             toNode.in++; // 入度数+1
  32.             // 点中加入边
  33.             fromNode.edges.add(newEdge);
  34.             // 图中加入边
  35.             graph.edges.add(newEdge);
  36.         }
  37.         return graph;
  38.     }
  39. }