图的搜索树

原文链接：https://blog.csdn.net/sodacoco/java/article/details/86488033

参看资料：
http://www.gonglin91.com/dfs-graph-edge/
http://www.cnblogs.com/bofengyu/p/5003049.html
图的搜索树是：在图的遍历过程中的形成的一棵树。

先明确几个概念：树边，前向边，后向边，横叉边
       树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式也是多样的，所以不同的遍历会得到不同的DFS树，进而产生不同的树边，前向边，后向边，横叉边。所以这4种边，是一个相对的概念。

树枝边：DFS时经过的边，即DFS搜索树上的边；

前向边：与DFS方向一致，从某个节点指向某个子孙的边；

后向边：与DFS方向相反，从某个节点指向某个祖先的边；

横叉边：从某个节点指向搜索树中另一子树中的某节点的边；

在很多算法中，后向边都是有作用的，但是前向边和横叉边的作用往往被淡化，其实它们没有太大作用。

《算法导论》334页有这4种边的准确定义，在此不累述
DFS过程中，对于一条边u->v
vis[v] = 0,说明v还没被访问，v是首次被发现，u->v是一条树边
vis[v] = 1,说明v已经被访问，但其子孙后代还没有被访问完（正在访问中），而u又指向v？说明u就是v的子孙后代，u->v是一条后向边，因此后向边又称返祖边
vis[v] = 2,z说明v已经被访问，其子孙后代也已经全部访问完，u->v这条边可能是一条横叉边，或者前向边

挖张图：

搜索树和原来的树并无差别，只是原来的每条边在深搜的过程中被赋予了不同的意义。

不同的遍历会得到不同的DFS树，进而产生不同的树边，前向边，后向边，横叉边。