为方便对DFS算法的考察, 为图G的每个结点设置属性color表示结点的颜色, color可取WHITE(白色), GRAY(灰色)或BLACK(黑色), 同时为每个结点设置属性d表示刚进行对此结点访问的时刻, 设置属性f表示刚结束对此结点访问的时刻, 先给出如下DFS和DFS_visit两个算法, 然后对其进行分析.
//深度优先遍历图G中所有结点
DFS(G)
time = 0
for G中每个结点v
v.color = WHITE
for G中每个结点v
if v.color == WHITE
v.p = NIL//NIL表示空
DFS_visit(v)
//深度优先遍历所有G中从点v可达, 且为白色的结点
DFS_visit(v)
v.d = ++time
v.color = GRAY
for G中以v为起点的所有边的终点u//若G为无向图, 则为G中所有与v邻接的结点u
if u.color == WHITE
u.p = v
DFS_visit(u)
v.f = ++time
v.color = BLACK
结论1: 算法DFS(G)必定在执行有限次数后终止(根据执行完第4至5行的循环体之后G中所有结点被设为白色, 且每对一个结点a调用DFS_visit(a), a立即被设置为灰色即可证明结论1, 此处不再赘述证明过程)
结论2(白色路径定理): 算法DFS_visit(v)将访问G中所有结点u, 其中u满足: 存在从v到u均为白色结点构成的路径
证明: 假设执行完DFS_visit(v)后, G中存在某个调用DFS_visit(G, v)初始时刻从从v到b均为白色结点构成的路径的结点b没有被访问, 设为v到b均由白色结点构成的路径,
, 由第15至18行代码易知如果
不被访问, 那么
也不会被访问, 一般的如果
(2 <= i <= k)不被访问那么
也不会被访问, 因此
不会被访问, 这显然与执行DFS_visit(v)矛盾, 因此假设不成立, 结论2得证.
结论3(括号化定理): 对于图G中任意两个节点u, v满足:
(1)u.f < v.d
(2)v.d < u.d < u.f < v.f
(3)u.d < v.d < v.f < u.f
(4)v.f < u.d
上述(1), (2), (3), (4)必居其一且仅居其一. (根据结论2较易证明此结论的正确性, 此处不再赘述证明过程)
结论4: 设有向图的结点集为G中所有结点构成的集合, 边集为{<v, u> | u.p = v}, 则
为森林, 且当G为无向图时, G的每个连通分量中的结点对应
中一个连通分量中的结点, 反之成立, 特别的, 算法DFS_visit(v)将创建
中以结点v为根的子树. 所有满足第7行if条件的结点v均为
中某棵树的根, (根据结论2较易证明结论4, 此处不再赘述证明过程)
结论5: 引入结论4定义的有向图, 并将
中的边称为树边, 每次第15行探索图G的一条边时, v为灰色, 对结点u的颜色分类, 满足如下结论
(1)u为白色, 则<v, u>为一条树边
(2)u为灰色, 称<v, u>为一条后向边, 在中u为v的祖先, 如果图G中存在环, 那么第15行必定发现后向边
(3)u为黑色, 称<v, u>为一条横向边, 则v, u在中位于两棵树中或者v, u在
中位于一棵树中且u为v的后代, 或者u不是v的后代, v也不是u的后代.
证明: 根据之前的结论2和结论4较易结论5的正确性, 此处不再赘述证明过程
结论6: 算法DFS的时间复杂度为O(v + e), v为G中结点个数, e为G中边的个数(证明从略)