请稍等 ...

8-4 寻找桥算法的JS实现

Edge.js

function Edge(v, w) {
    this.v = v;
    this.w = w;
    this.toString = function () {
        return `[${v}-${w}]`;
    }
}
module.exports = Edge;

FindBridges.js

const Graph = require("../../graph/Graph");
const Edge = require("./Edge");
function FindBridges($G) {
    var G = $G, visited = new Array(G.V()).fill(false);
    var low = new Array(G.V()), ord = new Array(G.V());
    var cnt = 0;
    var res = new Array();
    this.result = function () {
        return res.toString();
    }
    var dfs = function($v, $parent) {
        visited[$v] = true;
        low[$v] = cnt;
        ord[$v] = cnt;
        cnt ++;
        for (var w of G.adj($v)) {
            if (!visited[w]) {
                dfs(w, $v);
                low[$v] = Math.min(low[w], low[$v]);
                if (low[w] > ord[$v]) {
                    res.push(new Edge($v, w));
                }
            } else if (w != $parent) {
                low[$v] = Math.min(low[w], low[$v]);
            }
        }
    }
    for (var v = 0; v < G.V(); v++) {
        if (!visited[v]) {
            dfs(v, v);
        }
    }
}
var g = new Graph("data/寻找桥的算法/g3.txt");
var fb = new FindBridges(g);
console.log(fb.result())