一、深度优先搜索
它的定义是:递归探索图,必要时要回溯,同时避免重复。
关于深度优先搜索的伪代码如下:
左边DFS-Visit(V, Adj.s)是只实现visit所有连接某个特定点(例如s)的其他点。右边是实现整张图的visit,即DFS(v, Adj)。DFS-Visit是DFS的重要组成模块。
用上图右侧的实例图解释下运作过程:
先从a出发,DFS-Visit到b上。
递归到b上,从b出发,DFS-Visit到e上。
递归到e上,从e出发,DFS-Visit到d上。
递归到d上,从d出发,本来是要DFS-Visit到b上的,因为DFS要避免重复,所以这里就断了。
由于b已经被visit过了,现在从c出发,DFS-Visit到f上。
f不能visit自己,且e被visit过了,这里就断了。
之后c,d,e,f都被visit过了,所有就完成了。
DFS的时间复杂度如下(这里不做多余的解释):
二、边分类
Edge Classification可以解决两个问题:cycle detection和topological sort。
它有四种边:
tree edge:即带有parent pointer的边,通过该边可以visit到新的点。
forward edge:点到树中的子辈。
backward edge:点到树中的父辈。
cross edge:在两个无父辈关系的子树之间。
(如果是无向图,只存在tree edge和backward edge)
三、循环检测
如果图G有个循环,那么DFS就存在反向边back edge。反过来也成立,即如果DFS就存在反向边back edge,图G就有个循环。
在Job scheduling问题上,给定有向非循环图(DAG),排序点使得所有变从低位指向高位。这里使用拓扑排序Topological sort可以实现:使用DFS,然后反着输出点的完成时间。这这里面有个常理就是对于任何从u到v的边即e =(u,v),都满足v完成早于u完成。