Algorithm to find bridges from cut vertices

Question

Im trying to figure out the best way to find bridges in an undirected graph given its cut vertices. Should I use dfs? if so how do I go about determining whether its a bridge or not? I know how to do on paper but not in code.

Answer 1

I don't think you can take any benefit of knowing the cut vertices for determining what the bridges are.

A graph can have cut vertices but no bridges:

A graph can have no cut vertices but still a bridge:

Even an edge between two cut vertices is not guaranteed to be a bridge:

Algorithm for finding bridges

Bridges are those edges which are not on a cycle.

You can find the cycles in a graph with a depth-first search (DFS) from an arbitrarily selected node in the graph:

• Whenever you encounter an already visited node, then you have found a cycle. We could call this node the "cycle" node. This cycle node is by necessity on the current path from the starting node followed by the DFS.

• Mark all edges on this cycle as cycle. Or, alternatively, as not being bridges. This marking can be done during the backtracking part of the DFS. If the "cycle" node(s) are still higher up the path, mark the current edge. As soon as we backtrack further back than the visited nodes, that marking is no longer performed.

• There can be several cycles we find before having backtracked to the cycle node: we can have several cycle nodes pending, but only need to remember the one that is highest up the path. For this we can just store the "depth" such cycle node has in the DFS search path.

Here is pseudo code to perform the DFS and identify the bridges:

visited = new Map # keyed by vertices, giving depth at which a vertext was visited
bridges = new Set(edges) # collection of all edges

func dfs(previous, current, depth):
    visited.set(current, depth)
    cycleParent = depth + 1 # This means: no cycle detected
    for edge in edgesFrom(current):
        next = nodesOnEdge(edge)[0] # get one vertex on this edge
        if next == current: next = nodesOnEdge(edge)[1] # take the other vertex 
        if next != previous: # Not yet visited this edge
            # Either already visited this node, or recursion is initiated
            cycle = visited.get(next)
            if not cycle: cyle = dfs(current, next, depth+1)
            if cycle <= depth: bridges.remove(edge) # Edge is on a cycle
            if cycle < cycleParent: cycleParent = cycle
    return cycleParent

dfs(null, nodes[0], 1) # Start from any node, and depth = 1

# At the end of this process: bridges contains the answer.

Based on the data structures you have you would have to implement two functions:

• edgesFrom(node): returns the edges that are incident to the given vertex
• nodesOnEdge(edge): returns the two vertices (as array) that are connected by the given edge.

Here is an implementation in JavaScript, just to demonstrate it on an example:

function getBridges(graph) {
    const visited = new Map,
        bridges = new Set(graph.edges().toArray());

    function dfs(previous, current, depth) {
        visited.set(current, depth);
        let cycleParent = depth+1; // = No cycle
        for (let edge of current.connectedEdges().toArray()) {
            // Get other node on this edge
            const next = edge.source() === current ? edge.target() : edge.source();
            if (next === previous) continue; // Already visited this edge
            // Either already visited this node, or recursion is initiated
            const cycle = visited.get(next) || dfs(current, next, depth+1);
            if (cycle <= depth) bridges.delete(edge); // Edge is on a cycle
            if (cycle < cycleParent) cycleParent = cycle;
        }
        return cycleParent;
    }
    dfs(null, graph.nodes()[0], 1);
    return bridges;
}

function pairsToGraph(pairs) {
    // Initialise Cytoscape
    const cy = cytoscape({ container: document.getElementById('cy') });
    // Add points and edges to graph
    cy.add(Array.from(new Set([].concat(...pairs)), id => ({data:{id}})));
    cy.add(pairs.map(pair => ({data:{id: pair.join('_'), source: pair[0], target: pair[1]}})));
    // Render graph
    cy.layout({ name: 'cola', animate: true }).run();
    return cy;
}

// Define graph
const pairs = [
    [0,1], [1,2], [2,3], [3,1], [3,4], [4,5], [5,6], [6,3],
    [6,7], [7,3], [7,8], [8,9], [9,10], [10,11], [11,12], [12,9],
    [8,13], [13,14], [14,15], [15,16], [16,14], [16,13]  
];

// Use cytoscape for creating a graph object and its rendering
const cy = pairsToGraph(pairs);

// Get the bridges, and highlight them
const bridges = getBridges(cy);
for (const bridge of bridges) bridge.select();

#cy {
    width: 100%;
    height: 100%;
    position: absolute;
    top: 0px;
    left: 0px;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/cytoscape/3.2.8/cytoscape.min.js"></script>
<script src="http://marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>
<script src="https://cdn.rawgit.com/cytoscape/cytoscape.js-cola/2.0.0/cytoscape-cola.js"></script>
<div id="cy"></div>