[JS] 寻找桥实现

来源:8-3 模拟寻找桥算法

Potter520

2023-04-26

/**
 * 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 ] ]

图解找桥过程,希望能给大家提供一点帮助
图片描述

写回答

1回答

liuyubobobo

2023-04-27

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


继续加油!:)

0
1
Potter520
写得有点问题,已更正并附上找桥的过程图示
2023-04-27
共1条回复

玩转算法系列--图论精讲(Java版)

30+小时系统学习,bobo带你克服被图论支配的恐惧

1599 学习 · 330 问题

查看课程