[JS] 寻找桥实现

Question

/**
 * graph ：一个二位数组
 * graph[0]: 表示0号顶点，相邻的顶点
 */
function findBridge(graph) {
  let V = graph.length;
  //! 顶点遍历的序号
  let ord = Array(V).fill(0);
  //! 顶点可以遍历到以前的最小序号
  let low = Array(V).fill(0);
  let visited = Array(V).fill(false);
  let counter = 0;
  let res = [];

  function dfs(v, parent) {
    visited[v] = true;
    ord[v] = low[v] = counter++;

    for (const w of graph[v]) {
      if (!visited[w]) {
        dfs(w, v);
        low[v] = Math.min(low[v], low[w]);

        //! 说明：如果子节点不能抵达父节点之前的节点，说明构不成环，也就只有一条路，所以这两个节点就是桥
        if (low[w] > ord[v]) {
          res.push([v, w]);
        }
      } else if (w != parent) {
        //关键点：环位置
        //! 说明：如果当前节点可以抵达更前的节点，就更新当前节点的low[v]为相邻节点的low[w]
        low[v] = Math.min(low[v], low[w]);
      }
    }
  }

  dfs(0, 0);

  return res;
}

let res = findBridge([
  [1, 2],
  [0, 3],
  [0, 3],
  [1, 2, 5],
  [5, 6],
  [3, 4, 6],
  [4, 5],
]);

console.log(res);

输出结果：

[ [ 3, 5 ] ]

图解找桥过程，希望能给大家提供一点帮助

Answer 1

liuyubobobo 2023-04-27 08:00:43

力扣的 1192 号问题就是寻桥，可以用这个问题测试自己的算法：https://leetcode.cn/problems/critical-connections-in-a-network/

继续加油！：）

• 提问者 Potter520 #1

  写得有点问题，已更正并附上找桥的过程图示