无向图深度优先算法

所谓深度优先：从图中某个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。
对于一个无向图的深度优先访问，需要注意，每条边被访问了两次，对边的第一次访问v-w，存在两种情况：第一种直接进行w的递归调用，因为w没有访问过；第二种情况是w已经被访问过，忽略对w的调用。需要注意的是第二种情况下，v-w是形成了一个回边，也就是说，实际上与原来的递归调用路径形成了一个环。这点很有用。对边的第二次访问，都忽略递归调用，也存在两种情况，第一种是访问的节点是其父节点；第二种是访问的节点的递归调用已经完成，而本节点还在进行递归调用。
总结一句话：边分为树边（进行递归调用的边）和回边（不进行递归调用的边，形成环的边）。根据访问次数，可以分为四种链接：树链接，父链接（树边的两次访问）；回链接，下链接（回边的对应的两次访问）。
怎么来识别这些边呢？因为树的递归调用，在调用前，我们使用一个数组ord来记录调用的秩序，类似树的前序遍历，再使用一个数组st来记录每条递归调用边的父节点。通过这两个数组就可以识别上面的边的两次访问情况。
对于每次边的调用v-w
1） ord[w]=-1，那么v-w是树链接，进行递归调用。
2） ord[w]<ord[v]，说明w已经原来进行访问过，如果st[v]=w，则v-w是父链接。否则是回链接。（既然是回链接，则指向的节点肯定已经先访问过）。
3） ord[w]>ord[v]，则v-w是下链接，w节点的递归调用已经完成，v节点还在进行。
DFS的应用：
1） 环的检测，这个是很容易。根据上面的分析，判断是否是回链接就可以实现。
2） 可分离图：就是说图中存在桥（一个桥是一条特定的边，可以把一个连通图分解为不相交的两个子图）的图。根据DFS的边的特性的分析，回边是不可能是桥。桥v-w有个特性，对于节点w，没有一条回边将其子孙与其某个祖先相连。可以使用一个数组来记录节点w为根的的子树中任何回边所引用的最小前序编号（ord值）。
public void dfs (int v) {
ord[v] = cnt++;
low[v] = ord[v];
for (int w : G.adj(v)) {
if (ord[w] == -1) {

st[w] = v;
dfs2(w);
/**
* 访问完一个节点后，看这个节点子树中回边指向的最小祖先节点
*/
if (low[v] > low[w])
low[v] = low[w];
/**
* 一个节点回边指向的最先祖先节点是其本身，那么这条边是桥
*/
if (low[w] == ord[w]) {
System.out.println(v + "-------------------->" + w
+ " is bridge!");
}
} else

if (st[v] != w && ord[w] < ord[v]) {
/**
* 节点v的子节点的回边的节点小于本节点记录值
*/
if (low[v] > ord[w])
low[v] = ord[w];

}
}

}
3）图的连通性。