Graph
Graph 的表示方法
一般求解Graph题的时候，input给你一些点或者一些边，需要你自己用数据结构来存储（方便之后的调用）。那么，一般有2种：
邻接表 (Adjacent List)
邻接矩阵 (Adjacent matrix)
space cost
O(|V| + |E|)
O(|V|^2)
scenario
sparse graph
dense graph
implementation
List<List<Integer>>, outer list with the size of |V|
int[N][M]
Graph的遍历方法 （DFS and BFS）
一般需要遍历所有情况的时候，比如连通性问题，用DFS
一般找最短路径的时候，用BFS
DAG (Directed Acyclic Graph)
Directed Acyclic Graph 有向无环图，不需要考虑infinite loop，即不需要boolean array记录状态。
Directed Cyclic Graph 有向有环图，需要考虑 infinite loop。
Reference
Last updated