当前课程知识点:Data Structures and Algorithm Design Part I > 06.Graph > D.DFS > 06D-3
返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part I》慕课在线视频列表
以下我们就给出
对于不同状态邻居节点的处理方法
可以看到 无非三种情况
如果邻接顶点
是处于最初的UNDISCOVERED状态
那么就与BFS一样
意味着我们的支撑树
在这个位置可以进一步地拓展
为此我们要将从v
通往u的那样一条边
引入到遍历树中
相应地 在遍历树中顶点u
就将以顶点v为父亲
相应地 此后的控制权
也就转移到了新的这个邻居u
因此根据此前所约定的算法策略
我们就应该以这个新的顶点u为基准
继续递归地执行深度优先搜索
另一种可能的情况是
下一个邻接顶点u是处于第二种状态
也就是DISCOVERED
此时的处理方法是
将v和u之间的那条连边
标记为backward 回向边
或者简称回边
最后一种可能是
我们所遇到的下一个邻接顶点 u
已经被访问完毕
也就是处于最终的VISITED状态
这种情况又可以继续细分为
两种小的情况
而判别的依据是要看
顶点v和顶点u的
dTime时间标签孰大孰小
也就是看它们谁更早被发现
如果是v更早被发现
那么我们就将v到u的这条边
标记为FORWARD
也就是前向边 或者叫向前边
反过来 如果是u更早被发现
那么v到u的这条边
就将会标记成CROSS
交叉边或者是跨越边
整个算法至此已经封闭
以下我们需要通过一些实例
来体会整个算法的过程以及走向
并进而确立它的正确性
-A.Computation
--01A-1
--01A-2
--01A-3
--01A-4
--01A-5
--演示
--01A-6
--(a)计算--作业
-B.Computational_Models
--01B-1
--01B-2
--01B-3
--01B-4
--01B-5
--01B-6
--01B-7
--01B-8
-B.Computational_Models--Homework
-C.Big_o
--01C-1
--01C-2
--01C-3
--01C-4
--01C-5
--01C-6
--01C-7
-C.Big_o--Homework
-D.Algorithm_analysis
--01D-1
--01D-2
--01D-3
--01D-4
--01D-5
--01D-6
--01D-7
-D.Algorithm_analysis--Homework
-E.Iteration+Recursion
--01E-1
--01E-2
--01E-3
--01E-4
--01E-5
--01E-6
--01E-7
--01E-8
--01E-09
-E.Iteration+Recursion--Homework
-F.Dynamic_Programming
--01XC-1
--01XC-2
--01XC-3
--01XC-4
--01XC-5
--01XC-6
-- 演示
--01XC-7
--01XC-8
--01XC-9
--01XC-A
-F.Dynamic_Programming--Homework
-Homework
-A.Interface+Implementation
--02A-1
--02A-2
--02A-3
--02A-4
--02A-5
-A.Interface+Implementation--Homework
-B.extendable_vector
--02B-1
--02B-2
--02B-3
--02B-4
--02B-5
-B.extendable_vector--Homework
-C.unsorted_Vector
--02C-1
--02C-2
--02C-3
--02C-4
--02C-5
--02C-6
--02C-7
--02C-8
-C.unsorted_Vector--Homework
-D1.Sorted_Vector.uniquify
--02D1-1
--02D1-2
--02D1-3
--02D1-4
--02D1-5
-D1.Sorted_Vector.uniquify--Homework
-D2.Sorted_Vector.binary_search
--02D2-1
--02D2-2
--02D2-3
--02D2-4
--02D2-5
--02D2-6
--02D2-7
-D2.Sorted_Vector.binary_search--Homework
-D3.Sorted_Vector.fibonaccian_search
--02D3-1
--02D3-2
--02D3-3
--02D3-4
-D3.Sorted_Vector.fibonaccian_search--Homework
-D4.Sorted_Vector.binary_search_optimized
--02D4-1
--02D4-2
--02D4-3
--02D4-4
--02D4-5
-D4.Sorted_Vector.binary_search_optimized--Homework
-D5.Sorted_Vector.interpolation_search
--02D5-1
--02D5-2
--02D5-3
--02D5-4
--02D5-5
-D5.Sorted_Vector.interpolation_search--Homework
-E.Bubblesort
--02 E-1
--02E-2
--02E-3
--02E-4
--02E-5
-E.Bubblesort--Homework
-F.Mergesort
--02F-1
--02F-2
--02F-3
--02F-4
--02F-5
--02F-6
-F.Mergesort-Homework
-Homework
-A.interface+Implementation
--03A-1
--03A-2
--03A-3
--03A-4
-A.interface+Implementation--Homework
-B.Unsorted_list
--03B-1
--03B-2
--03B-3
--03B-4
--03B-5
-B.Unsorted_list--Homewrok
-C.Sorted_list
--03C-1
--03C-2
--03C-3
-C.Sorted_list--Homewrok
-D.Selectionsort
--03D-1
--03D-2
--03D-3
--03D-4
--03D-5
--03D-6
-D.Selectionsort--Homework
-E.Insertionsort
--03E-1
--03E-2
--03E-3
--03E-4
--03E-5
--03E-6
--03E-7
--03E-8
-E.Insertionsort--Homework
-(xd):LightHouse
--03XD
-Homework
-A.stack-ADT+implementation
--04A-1
--04A-2
--04A-3
-A.stack-ADT+implementation--Homework
-C1.stack-App-conversion
--04C1-1
--04C1-2
--04C1-3
-C1.stack-App-conversion--Homework
-C2.stack-App-parentheses
--04C2-1
--04C2-2
--04C2-3
--04C2-4
--04C2-5
--04C2-6
-C2.stack-App-parentheses--Homewrok
-C3.stack-App-permutation
--04C3-1
--04C3-2
--04C3-3
--04C3-4
--04C3-5
-C3.stack-App-permutation--Homework
-C4.stack-App-infix
--04C4-1
--04C4-2
--04C4-3
--04C4-4
--04C4-5
--04C4−6A
--04C4−6B
--04C4−6C
--04C4-6D
-C4.stack-App-infix--Homework
-C5.stack-App-rpn
--04C5-1
--04C5-2
--04C5-3
--04C5-4
-C5.stack-App-rpn--Homework
-D.Queue-ADT+implementation
--04D-1
--04D-2
--04D-3
-Homework
-A.Tree
--05A-1
--05A-2
--05A-3
--05A-4
--05A-5
--05A-6
--05A-7
-A.Tree--Homework
-B.Representation
--05B-1
--05B-2
--05B-3
--05B-4
--05B-5
-B.Representation--Homework
-C.Binary_Tree
--05C-1
--05C-2
--05C-3
-C.Binary_Tree--Homework
-D.Implementation
--05D-1
--05D-2
--05D-3
--05D-4
--05D-5
-D.Implementation--Homework
-E1.Preorder
--05E1-1
--05E1-2
--05E1-3
--05E1-4
--05E1-5
--05E1-6
--05E1-7
--05E1-8
--05E1-9
-E1.Preorder--Homework
-E2.Inorder
--05E2-1
--05E2-2
--05E2-3
--05E2-4
--05E2-5
--05E2-6
--05E2-7
-E2.Inorder--Homework
-E4.LevelOrder
--05E4-1
--05E4-2
--05E4-3
-E4.LevelOrder--Homework
-E5.reconstruction
--05E5-1
--05E5-2
--05E5-3
-E5.reconstruction--Homework
-Homework
-A.Introduction
--06A-1
--06A-2
--06A-3
-A.Introduction--Homework
-B1.Adjacency_Matrix
--06B1-1
--06B1-2
--06B1-3
--06B1-4
--06B1-5
--06B1-6
--06B1-7
--06B1-8
--06B1-9
-B1.Adjacency_Matrix--Homework
-C.BFS
--06C-1
--06C-2
--06C-3
--06C-4
--06C-5
--06C-6
--06C-7
--06C-8
-C.BFS--Homework
-D.DFS
--06D-1
--06D-2
--06D-3
--06D-4
--06D-5
--06D-6
--06D-7
-D.DFS--Homework
-Homework