数据结构考试复习（4）

发表于   |  

Depth-First-Search即深度优先搜索

##0X00 算法介绍

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。

##0X01 算法过程

先选定图的类别（有向图、无向图），再选定图的存储结构，根据输入的顶点或者边建立图；

并把相应的邻接表或者邻接矩阵 测试输出；

根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法，并输出遍历结果；

假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则DFS递归调用包含以下操作：

（1）访问搜索到的未被访问的邻接点；

（2）将此顶点的visited数组元素值置1；

（3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。

深度优先搜索DFS可描述为：

（1）访问v0顶点；

（2）置 visited[v0]=1；

（3）搜索v0未被访问的邻接点w，若存在邻接点w，则DFS(w)。

##0X02 算法应用

深度优先搜索适用范围：在树深度已知情况下，并且树体系相当庞大时，深度优先搜索往往会比广度优先搜索优秀。

###剪枝策略：

1）最优化剪枝

记录下当前得到的最优值，如果当前所在的节点已经没有可能得到比当前最优值更好的结果，提起回溯。在使用最优化剪枝的过程中，关键是在第一次得到结果或到达叶子节点后记录下得到值作为当前最优值。当后续遍历树的过程中，通过比较如果得到比当前最优值更好的值则更新当前最优值，如果在某个节点中通过比较发现当前所在节点在继续扩展已经无法得到最优解，则剪枝。

2）可行性剪枝

可行性剪枝一般需要根据问题的理解来进行，需要对问题有深刻的理解同时需要敏锐的观察和思考。对于某个具体问题，当运行到某个节点后根据问题信息可以判断是不可行则不需要继续扩展。比较典型的可行性剪枝是奇偶剪枝。

###通常可以解决的问题有：

八皇后问题，迷宫问题，寻找强连通分量个数，最大连通分量的结点数，拓扑排序，Flood fill算法，穷举

用例子说明穷举问题：列出 A ~ F 这六个字母所能列出的所有组合（必须6位，不允许重复）。当然你可以用6重循环给出答案，但是随着字母数量增多，深度优先会是你的不二选择。

##0X03 算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//DFS递归实现
//邻接矩阵存图
gh[][]
vis[][]
dx[], dy[] //可用于DFS时的代码优化
//初始化图
Initial(gh,vis)
//主程序
for u
    if not vis[u] DFS(u)
//深度有限搜索
DFS(node u){
    judge if u reachable, if not, return
    vis[u] = true
    ...
    node v
    for v (linked by u)
        if not vis[v] DFS(v)
        //backtrack
    return
}
//注意图的连通性，考虑非连通图的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//DFS非递归实现
//如果栈顶节点的所有直接邻接点都已访问过，则弹出栈顶节点
//否则，将该栈顶节点的未访问的其中一个邻接点压入栈，同时，标记该邻接点为已访问
for u
    if not vis[u] DFS(u)
    
DFS(node u){
    stack<node> s
    s.push(u)

    node v,k
    while(!s.empty()){
        v = s.top()
        vis[v] = true  
        ...
        flag = true
        for k(linked by v) in nodes{
            if(!vis[k]){
                s.push(k)
                flag = false
                break
            }
        }
        if (flag) s.pop()
    }
}

loading any more