Bridge in a graph that makes the graph disconnected

Question

I am working on programming where I need to find the articulation points of a graph (nodes such that removing any of them makes the graph disconnected)

For example, I have these links:

Example 1

[[0,1], [0,2], [1,3], [2,3], [5,6], [3,4]]

The answer should be [2,3,5], because removing these nodes makes the graph disconnected.

Explanation:

If I remove node 2 here, the graph becomes 2 parts 0,1,3,4 and 5,6
If I remove node 3 here, the graph becomes 2 parts 0,1,2,5,6 and 4
If I remove node 5 here, the graph becomes 2 parts 0,1,2,3,4 and 6

Example 2:

[[1,2], [2,3], [3,4], [4,5], [6,3]]

The output should be: [2, 3, 4]

Explanation:

If I remove node 2 here, the graph becomes 2 parts 1, and 3,4,5,6
If I remove node 3 here, the graph becomes 3 parts 1,2 and 6 and 4,5
If I remove node 4 here, the graph becomes 2 parts 1,2,3,6 and 5

How to achieve this in a Java program?

Alex Thai · Accepted Answer

import static java.lang.Math.min;

import java.util.ArrayList;
import java.util.List;

public class ArticulationPointsAdjacencyList {

  private int n, id, rootNodeOutcomingEdgeCount;
  private boolean solved;
  private int[] low, ids;
  private boolean[] visited, isArticulationPoint;
  private List> graph;

  public ArticulationPointsAdjacencyList(List> graph, int n) {
    if (graph == null || n <= 0 || graph.size() != n) throw new IllegalArgumentException();
    this.graph = graph;
    this.n = n;
  }

  // Returns the indexes for all articulation points in the graph even if the
  // graph is not fully connected.
  public boolean[] findArticulationPoints() {
    if (solved) return isArticulationPoint;

    id = 0;
    low = new int[n]; // Low link values
    ids = new int[n]; // Nodes ids
    visited = new boolean[n];
    isArticulationPoint = new boolean[n];

    for (int i = 0; i < n; i++) {
      if (!visited[i]) {
        rootNodeOutcomingEdgeCount = 0;
        dfs(i, i, -1);
        isArticulationPoint[i] = (rootNodeOutcomingEdgeCount > 1);
      }
    }

    solved = true;
    return isArticulationPoint;
  }

  private void dfs(int root, int at, int parent) {

    if (parent == root) rootNodeOutcomingEdgeCount++;

    visited[at] = true;
    low[at] = ids[at] = id++;

    List edges = graph.get(at);
    for (Integer to : edges) {
      if (to == parent) continue;
      if (!visited[to]) {
        dfs(root, to, at);
        low[at] = min(low[at], low[to]);
        if (ids[at] <= low[to]) {
          isArticulationPoint[at] = true;
        }
      } else {
        low[at] = min(low[at], ids[to]);
      }
    }
  }

  /* Graph helpers */

  // Initialize a graph with 'n' nodes.
  public static List> createGraph(int n) {
    List> graph = new ArrayList<>(n);
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    return graph;
  }

  // Add an undirected edge to a graph.
  public static void addEdge(List> graph, int from, int to) {
    graph.get(from).add(to);
    graph.get(to).add(from);
  }

  /* Example usage: */

  public static void main(String[] args) {
    testExample2();
  }

  private static void testExample1() {
    int n = 7;
    List < List < Integer >> graph = createGraph (n);

    addEdge (graph, 0, 1);
    addEdge (graph, 0, 2);
    addEdge (graph, 1, 3);
    addEdge (graph, 2, 3);
    addEdge (graph, 2, 5);
    addEdge (graph, 5, 6);
    addEdge (graph, 3, 4);

    ArticulationPointsAdjacencyList solver = new ArticulationPointsAdjacencyList(graph, n);
    boolean[] isArticulationPoint = solver.findArticulationPoints();

    // Prints:
    // Node 2 is an articulation
    // Node 3 is an articulation
    // Node 5 is an articulation
    for (int i = 0; i < n; i++)
      if (isArticulationPoint[i]) System.out.printf("Node %d is an articulation
", i);
  }

  private static void testExample2() {
    int n = 7;
    List < List < Integer >> graph = createGraph (n);

    addEdge (graph, 1, 2);
    addEdge (graph, 2, 3);
    addEdge (graph, 3, 4);
    addEdge (graph, 3, 6);
    addEdge (graph, 4, 5);


    ArticulationPointsAdjacencyList solver = new ArticulationPointsAdjacencyList(graph, n);
    boolean[] isArticulationPoint = solver.findArticulationPoints();

    // Prints:
    // Node 2 is an articulation
    // Node 3 is an articulation
    // Node 4 is an articulation
    for (int i = 0; i < n; i++)
      if (isArticulationPoint[i]) System.out.printf("Node %d is an articulation
", i);
  }
}

Reference: https://github.com/williamfiset/Algorithms/blob/master/com/williamfiset/algorithms/graphtheory/ArticulationPointsAdjacencyList.java

Bridge in a graph that makes the graph disconnected

Answers (2)

Tarjan Algorithm

Algorithm description

Example

Code

Related Questions