图的表示（数组）

图的数据结构

/***
 * 图
 */
public class Graph {
	public HashMap<Integer,Node> nodes;//点
	public HashSet<Edge> edges;//边

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

点的数据结构

/***
 *图中节点
 */
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<>();
	}
}

边的数据结构

/***
 * 图的边
 */
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;
	}
}

生成图算法

	/***
	 * 从数组获取两节点，和权重
	 * 将两个点添加到图中
	 * 从图中获取两个点
	 * 起始点的邻居添加结束点
	 * 起始点的出度增加1
	 * 结束点的入度增加1
	 * 起始点的边添加一条新的边
	 * 图的边添加一条新的边
	 * @param matrix
	 * @return
	 */
	public static Graph createGraph(Integer[][] matrix) {
		Graph graph = new Graph();
		for (int i = 0; i < matrix.length; i++) {
			Integer from = matrix[i][0];
			Integer to = matrix[i][1];
			Integer weight = 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;
	}