DFS 和 BFS

作者:江月迟迟

发表于:2025-01-05

字数统计:1018 字

预计阅读4分钟

所谓 DFS 就是 Depth-First Search 深度优先搜索，BFS 就是 Breadth-First Search 广度优先搜索。

DFS

遍历二叉树

class TreeNode {
    constructor(val = undefined, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const result = [];

// 前序遍历：中左右
function dfsPreorder(node) {
    if (!node) return;
    result.push(node.val);
    dfsPreorder(node.left);
    dfsPreorder(node.right);
}

// 中序遍历：左中右
function dfsInorder(node) {
    if (!node) return;
    dfsInorder(node.left);
    result.push(node.val);
    dfsInorder(node.right);
}

// 后序遍历：左右中
function dfsPostorder(node) {
    if (!node) return;
    dfsPostorder(node.left);
    dfsPostorder(node.right);
    result.push(node.val);
}

遍历树

interface TreeNode {
    val: string;
    children: TreeNode[];
}

const result: string[] = [];

function dfs(node: TreeNode) {
    result.push(node.val);
    for (const child of node.children) {
        dfs(child);
    }
}

遍历有向图

// 示例图的邻接表表示
const graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
};

const result = [];

// 遍历这个图，每个节点只访问一次
function dfs(graph, node, visited = new Set()) {
    if (!visited.has(node)) {
        result.push(node);
        visited.add(node);
        for (const neighbor of graph[node]) {
            dfs(graph, neighbor, visited);
        }
    }
}

遍历二维数组（图中找路径或者方案）

const matrix = [
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
];

const m = matrix.length;
const n = matrix[0].length;
const result = [];

// i, j 代表从哪开始，假设搜索方式是搜索相邻的四个节点
function dfs(i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n) return;
    // 标记 used，这里用置 -1 代替
    if (matrix[i][j] === -1) return;
    result.push(matrix[i][j]);
    matrix[i][j] = -1;
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
    return;
}

BFS

遍历二叉树

class TreeNode {
    constructor(val = undefined, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const result = [];

function bfs(root) {
    if (!root) return;
    const queue = [root];
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

遍历树

interface TreeNode {
    val: string;
    children: TreeNode[];
}

const result: string[] = [];

function bfs(root: TreeNode) {
    if (!root) return;
    const queue: TreeNode[] = [root];
    while (queue.length > 0) {
        const node = queue.shift()!;
        result.push(node.val);
        for (const child of node.children) {
            queue.push(child);
        }
    }
}

遍历有向图

// 示例图的邻接表表示
const graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
};

const result = [];

// 遍历这个图，每个节点只访问一次
function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    while (queue.length > 0) {
        const node = queue.shift();
        if (!visited.has(node)) {
            result.push(node);
            visited.add(node);
            for (const neighbor of graph[node]) {
                queue.push(neighbor);
            }
        }
    }
}

遍历二维数组（图中找路径或者方案）

const matrix = [
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
    [1, 1, 4, 5, 1, 4],
];

const m = matrix.length;
const n = matrix[0].length;
const result = [];

function bfs(i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n) return;
    if (matrix[i][j] === -1) return;
    const queue = [[i, j]];
    while (queue.length > 0) {
        const [x, y] = queue.shift();
        result.push(matrix[x][y]);
        matrix[x][y] = -1;
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        for (const [dx, dy] of directions) {
            const newX = x + dx;
            const newY = y + dy;
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] !== -1) {
                queue.push([newX, newY]);
            }
        }
    }
}

DFS 和 BFS 的比较

特性	DFS	BFS
遍历顺序	深度优先	广度优先
数据结构	栈（递归或显式栈）	队列
时间复杂度	O(V + E)	O(V + E)
空间复杂度	O(V)（递归栈或显式栈）	O(V)（队列）
应用场景	寻找路径、连通性、拓扑排序	最短路径、层次遍历、宽度搜索

• DFS：适用于需要深入探索的场景，如迷宫问题、连通性问题、拓扑排序等。
• BFS：适用于需要按层次遍历的场景，如最短路径问题、宽度搜索等。