一 图的表示

1. 总体表示

import java.util.HashMap;
import java.util.HashSet;
public class Graph {
  // 点的集合，key为点的序号
    public HashMap<Integer,Node> nodes;
  // 边的集合
    public HashSet<Edge> edges;
    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

2. 点的表示

import java.util.ArrayList;
public class Node {
  // 节点的值，也可以是其他类型
    public int value;
  // 入度：有多少个节点指向这个节点
    public int in;
  // 出度：该节点指向多少个节点
    public int out;
  // 指向的点的集合
    public ArrayList<Node> nexts;
  // 该点发散出去的边的集合
    public ArrayList<Edge> edges;
    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

3. 边的表示

public class Edge {
  // 边的权重
  public int weight;
  // 边出发的点
    public Node from;
  // 边的终点
    public Node to;
    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

4. 示例

public class GraphGenerator {
  /**
  *  一个二维数组来表示图
      [weight,from,to]
  */
    public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            Integer weight = matrix[i][0];
            Integer from = matrix[i][1];
            Integer to = matrix[i][2];
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight, fromNode, toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}