图的遍历 Traversal
DFS
一直向深处寻找。每次探索一个新的未探索的node。
关键是记录哪个node是已探索了的，可以是一个hashset，也可以直接在node上标记，还可以是一个size为n的数组（boolean或者0、1），甚至是一个hashmap记录node的parent（从parent探索到node，这种还可以做topological sort，结合并查集等）。可以用递归，也可以用迭代，迭代需要一个stack辅助（递归其实用到递归栈）。
伪代码 pseudocode
1. 递归
dfs(graph):
for
dfs_visit(node):
复杂度
最通用的DFS时间复杂度是O(|V|+|E|)，|V|是因为要遍历所有节点以保证图不是都相连的情况下能遍历完。如果已知都是相连的，则只要O(|E|)。空间复杂度是O(|V|)，因为要追踪每个节点是否已访问。
DFS森林
名字叫DFS森林，对于一个相连的图，则是一个树。
遇到一个新的节点a，它是从节点b访问到的，就连接a和b，是为tree edge，称b为a的parent，而如果遇到已经访问过的非parent的ancestor，则用虚线连，是为back edge。所有tree edge在一起形成树或者森林，而加上back edge就是原图了。
DFS森林可以用来找环。
DFS得到的节点序列
两个序列，一个是新访问到的节点（从stack push），一个是访问完的节点（从stack pop）。
判断连通性 connectivity
小循环跑完，大循环还发现未访问节点，则不连通，找到新的一块了。
判断无环性 acyclicity
DFS森林没有back edge则无环。如果有back edge，比方说a到b有个back edge，则从a到b的tree edge加上该back edge就是一个环。