DFS 深度优先搜索

概念¶

DFS（Depth First Search），深度优先算法，深度优先就是搜索到一个节点之后继续搜索下一个节点，直到无法继续搜索
和BFS不同，DFS第一次搜索到的结果不一定是距离最短的；若要找到最短路线，需要在一个节点搜索多次，具体见下面的C++实现下面是一个示例，*代表障碍物

011-11-21-31-41-51-61-72-12-22-32-1-12-1-22-2-12-2-2

0 ? ? ? ?
* ? * * ?
* ? * * ?
? ? ? * ?
? * ? * ?

0 1 ? ? ?
* ? * * ?
* ? * * ?
? ? ? * ?
? * ? * ?

0 1 2 ? ?
* ? * * ?
* ? * * ?
? ? ? * ?
? * ? * ?

0 1 2 3 ?
* ? * * ?
* ? * * ?
? ? ? * ?
? * ? * ?

0 1 2 3 4
* ? * * ?
* ? * * ?
? ? ? * ?
? * ? * ?

0 1 2 3 4
* ? * * 5
* ? * * ?
? ? ? * ?
? * ? * ?

0 1 2 3 4
* ? * * 5
* ? * * 6
? ? ? * ?
? * ? * ?

0 1 2 3 4
* ? * * 5
* ? * * 6
? ? ? * 7
? * ? * ?

0 1 2 3 4
* ? * * 5
* ? * * 6
? ? ? * 7
? * ? * 8

0 1 2 3 4
* 2 * * 5
* ? * * 6
? ? ? * 7
? * ? * 8

0 1 2 3 4
* 2 * * 5
* 3 * * 6
? ? ? * 7
? * ? * 8

0 1 2 3 4
* 2 * * 5
* 3 * * 6
? 4 ? * 7
? * ? * 8

0 1 2 3 4
* 2 * * 5
* 3 * * 6
5 4 ? * 7
? * ? * 8

0 1 2 3 4
* 2 * * 5
* 3 * * 6
5 4 ? * 7
6 * ? * 8

0 1 2 3 4
* 2 * * 5
* 3 * * 6
5 4 5 * 7
6 * ? * 8

实现¶

DFS的实现有很多，可以基于递归和栈

二维DFS¶

递归实现¶

C++PythonJavascript

#include <stdio.h>
using namespace std;
struct Vector2
{
    int x = 0, y = 0;

    Vector2 operator+(Vector2 v)
    {
        return {x + v.x, y + v.y};
    }
};
// vis: 储存所有搜索过的格子  n、m: 地图尺寸
int vis[10000][10000], n, m;

const Vector2 SIDES[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 搜索点坐标
Vector2 now, u, v;
void DFS(Vector2 u)
{
    vis[u.x][u.y]++;
    for (int i = 0; i < 4; i++)
    {
        Vector2 v = u + SIDES[i];
        if (v.x < 0 || v.x >= n || v.y < 0 || v.y >= m)
            continue;
        if (vis[v.x][v.y] != 0/* && vis[v.x][v.y] < vis[u.x][u.y] + 1*/) // 把注释去掉会变成自动寻找最短路线
            continue;
        // 在这里添加if(...) continue; 实现避开障碍物的效果
        vis[v.x][v.y] = vis[u.x][u.y];
        DFS(v);
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &now.x, &now.y);
    DFS(now);
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < m; y++)
        {
            printf("%d ", vis[x][y] - 1);
        }
        putchar('\n');
    }
    return 0;
}

class Vector2:
    x = 0
    y = 0
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def add(self, v):
        return Vector2(self.x + v.x, self.y + v.y)

SIDES = (Vector2(-1, 0), Vector2(1, 0), Vector2(0, -1), Vector2(0, 1))
vis = []
n = 10
m = 10

def DFS(u: Vector2):
    vis[u.x][u.y] += 1
    for i in range(0, 4):
        v: Vector2 = u.add(SIDES[i])
        if v.x < 0 or v.x >= n or v.y < 0 or v.y >= m:
            continue
        if vis[v.x][v.y] != -1:
            continue
        vis[v.x][v.y] = vis[u.x][u.y]
        DFS(v)

n = int(input())
m = int(input())
for i in range(0, n):
    l = []
    for j in range(0, m):
        l.append(-1)
    vis.append(l)

sx = int(input())
sy = int(input())
DFS(Vector2(sx, sy))
for i in range(0, n):
    for j in range(0, m):
        print(vis[i][j], end=' ')
    print('')

class Vector2 {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
    /**
     * @param {Vector2} v 
     * @returns {Vector2}
     */
    add(v) {
        return new Vector2(this.x + v.x, this.y + v.y);
    }
    clone() {
        return new Vector2(this.x, this.y);
    }
}

const SIDES = [new Vector2(-1, 0), new Vector2(1, 0), new Vector2(0, -1), new Vector2(0, 1)];
let n = 10, m = 10;
let vis = [];
for(let i = 0; i < n; i++)
    vis.push(new Array(m).fill(-1));

/**
 * DFS算法示例
 * @param {Vector2} u 起始点坐标
 */
function DFS(u) {
    vis[u.x][u.y]++;
    for(let d of SIDES){
        let v = u.add(d);
        if(v.x < 0 || v.x >= n || v.y < 0 || v.y >= m)
            continue;
        if(vis[v.x][v.y] !== -1)
            continue;
        // 在这里添加if(...) continue; 实现避开障碍物的效果
        vis[v.x][v.y] = vis[u.x][u.y];
        DFS(v);
    }
}

DFS(new Vector2(5, 5));
for(let line in vis)
    console.log(vis[line].join(' '));

栈实现¶

基于栈实现的DFS和BFS十分相似，只是把队列换成了栈