For any graph sum of total indegree should be equal to total outdegree
图的表示：
(1) Adjacency Matrix 邻接矩阵 便于check两个结点是否相连 | 适合稠密图
(2) Adjacency list 邻接链表 适合稀疏图遍历
屏幕快照 2017-09-21 上午1.16.47.png
(1) Java 邻接矩阵初始化
// i -> j node pairs
int[][] adj_matrix = new int[node_num][node_num];
for (int i = 0; i < pairs.length; i++) {
int pre = pairs[i][0];
int post = pairs[i][1];
adj_matrix[pre][post] = 1; // for directed edges
// adj_matrix[post][pre] = 1; // for undirected edges
}
(2) Java 邻接链表初始化
// graph = adj_list init
List<List<Integer>> graph = new ArrayList<List<Integer>>();
for(int i = 0; i < num_node; i++) {
graph.add(new ArrayList<Integer>()); // LinkedList is also OK
}
// graph(adj_list) build
// i -> j node pairs
for (int i = 0; i < pairs.length; i++) {
int pre = pairs[i][0];
int post = pairs[i][1];
graph.get(pre).add(post); // for directed edges
// graph.get(post).add(pre); // for undirected edges
}
