图的实现
图的节点数为V，边数为E，构造一个节点数组adj[V]，节点id为数组下标，每个节点的数据结构里维护一个邻接表（链表），链表保存和其连接的节点id。用一个Graph的类来封装这个节点数组。
对于无向图，连接a-b，则a和b的邻接表都有彼此的id
对于有向图，连接a->b，则a的邻接表有b，b的邻接表没有a
DFS
对于图：1-2，1-3，1-4，2-5，2-6 … …
1作为起始节点，访问1的邻接表（2-3-4），每次访问到的元素（234），都作为新的起始节点开始递归。
终止条件：当访问完节点的邻接表里的每个邻居或者该节点被访问过
可能会出现一个节点在DFS递归中多次被访问到，所以通过一个boolean[V]数组表示该节点是否已经被访问过了，被访问过的节点不会再被递归
BFS
对于图：1-2，1-3，1-4，2-5，2-6 … …
如果以1作为起始节点，访问1的邻接表（2-3-4），将1的邻居234加入到一个queue里，然后queue做出队操作，出队的每一个元素，访问邻接表，将邻居节点入队。队列为空返回。
用一个int[V]数组表示到节点的上一跳节点ID。通过该数组将回溯的结果push到Stack可以得到从起始节点到邻居的最短路径
也要维护一个boolean数组判断当前访问的元素是否已经被访问过，如果是，则不入队
DFS查找连通分量
用一个int[V]保存节点所属连通分量的id，保证用DFS搜索到的节点，与起始节点有相同的连通分量id，该id表示当前是第几个连通分量。
遍历节点时，判断当前节点是否被访问了，如果是，跳过DFS搜索
DFS判断二分图
二分图就是图中的节点划分为两派A、B，两派内部的节点中两两互不相连，A派的节点只会和B派的节点相连。
根据上面的性质，二分图中的每个链接都来自不同的派，如果将A派统一着色，B派统一着色，那么一条连接的两个端点颜色必然不同！
借鉴这种思想，DFS时可以判断图是否是二分图。
用一个boolean[V]表示两节点的颜色，如果DFS到节点1时，查找1的邻接表（2，3，4），然后递归节点2之前将链接两端的节点反色，boolean[1] = !boolean[2]
因为1和234链接，所以234是一派，假设23链接，就打破了二分图的定义
因为是DFS所以2会先访问到3，当2访问3时，boolean[2] = !boolean[3]
当1访问3时，尽管3已经被visit，还是会判断3的颜色，这时会发现boolean[1]和boolean[3]同色，就说明不是二分图了！
即，在DFS时，如果当前节点没有visit，递归前将其反色后递归。如果当前节点已经visit了，判断其和自己的颜色是否一致，如果一致说明不是二分图。
DFS判断有环图
1、无向图：
DFS时，每次递归都携带起始节点id，如果递归过程中，节点a的邻居节点b被visit了，但b不是起始节点，说明：从起始节点出发有到b的至少两条路径，所以是有环图。
2、有向图：
对图中的每个节点作为起始节点，调用V次DFS。每次DFS，除了用boolean[]标识已经visit的节点，在第一次递归前，用另一个boolean A[V]数组，将A[起始节点设为true。当DFS的过程中碰到节点j已经被visit，且A[j]为true，说明j节点就是起始节点，则存在环。如果DFS结束仍然没有遇到环，则说明到起始节点不存在环，重新置A[起始节点]为false，继续对后面的节点做DFS。
感觉这种方式比较麻烦，还不如在DFS时加一个参数表示起始节点，碰到邻居节点已经被访问，就拿其id和起始节点id比较。
符号图
图的应用，其节点往往是一个字符串。用一个TreeMap<String ,Integer>来保存每个节点。对于每个节点，在Graph类中用其索引来表示，所以对于每个节点依然可以创建邻接表。
因为图的操作用index表示单词，所以如果需要得到单词，可以创建一个String[]，用index作为索引存储单词。
最短路径
如果需要查找单词a在图中到另一个单词b的最短路径，先构造符号图，再对单词a用BFS，如果单词b在BFS访问的节点集里，返回最短路径。
因为BFS是按跳数访问邻居的，所以适合查找最短路径。
BFS时，用一个int[V]的数组保存节点i的上一跳，对于到b的最短路径，回溯int[b]直到a即可。
有向图的前序、后序、逆后序遍历
前序遍历就是DFS的调用顺序，在对当前节点DFS向后递归前，将节点入队
后序遍历就是节点完成DFS的顺序，如果节点完成了DFS（其邻居节点都已经向下DFS返回了），才将该节点入队
逆后序是后序的逆序，用一个Stack保存后序入队的节点即可
拓扑排序
对于有向无环图，拓扑排序满足如下条件：
如果有向图存在路径i->j，那么i在拓扑排序中一定在j的前面拓扑排序就是有向图的逆后序：因为逆后序的意思是，完成DFS的节点的逆序。所以如果逆后序里，i在j的前面说明节点j完成了DFS后节点i才完成。