图的搜索算法

并查集是用来检查两个顶点之间的连通性。而找出图所有的顶点呢、找出它两个顶点之间的路径等都需要深度优先搜索算法或广度优先搜索算法。

深度优先搜索算法

Depth First Search DFS => always use stack .

时间复杂度 空间复杂度
DFS 遍历所有节点 $$O(V+E)$$ \[O(V)\]
DFS 遍历两点之间所有路径 $$O((2^V)∗(V+E))$$ $$O((2^V)∗V)$$

V 表示顶点数，E 表示边数。

练习题 - 力扣 797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j] 存在一条有向边）。

1
2
3
4
5
6
7
8
示例1：
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

注意：

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] != i（即不存在自环）
  • graph[i] 中的所有元素 互不相同
  • 保证输入为 有向无环图（DAG）

本题可用 DFS / 递归 或 回溯 的方法做。这里给出 DFS 的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function(graph) {
    let answer = [];
    const n = graph.length;
    (function dfs(start = 0, arr = []) {
        arr.push(start);
        if(start === n - 1) {
            answer.push(arr.slice());
            return;
        }
        for(let i = 0; i < graph[start].length; i++) {
            dfs(graph[start][i], arr.slice());
        }
    })()
    return answer;
};

广度优先搜索算法

Breath First Search BFS => always use queue .

“广度优先搜索” 最高效的用途是：当在 权重相等且均为正数的图中，它可以快速的找到两点之间的最短路径

  1. 遍历「图」中所有顶点
  2. 针对 权重相等且均为正数的「图」，快速找出两点之间的最短路径
时间复杂度 空间复杂度
BFS 遍历所有顶点 $$O(V+E)$$ $$O(V)$$
BFS 求两点之间最短路径 $$O(V+E)$$ $$O(V)$$

V 表示顶点数，E 表示边数。

上题也可用 BFS 做（不建议）：

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
27
/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function(graph) {
    let ans = [];
    const n = graph.length;
    if(!graph || n === 0) {
        return ans;
    }
    let path = [0];
    let queue = [path];
    while(queue.length) {
        let cur = queue.shift();
        let node = cur[cur.length - 1];
        for(let next of graph[node]) {
            let t = cur.slice();
            t.push(next);
            if(next == n - 1) {
                ans.push(t.slice());
            } else {
                queue.push(t.slice());
            }
        }
    }
    return ans;
};
JavaScript 算法 图 图的搜索
JavaScript 算法
作者：Kart Jim
链接：https://github.com/can-dy-jack/delicate/2022/12/15/algorithm/图的搜索算法/
来源：Hexo
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 许可协议。著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
上一篇 图 - 最小生成树
长风破浪会有时，直挂云帆济沧海