Articulation Points

Definition

Definition

Articulation Points Algorithm is a graph algorithm used to identify critical points, or articulation points, within a connected graph. These points, when removed, disconnect the graph or increase its number of connected components

Explanation

Begin by initializing variables and data structures to represent the graph, then perform a Depth First Search (DFS) or Breadth First Search (BFS) traversal on the graph, marking vertices as visited and keeping track of discovery time and low value for each vertex during the traversal. Determine if a vertex is an articulation point by examining its children in the DFS tree, and finally output the identified articulation points

Guidance

• Initialize variables
  • initialize an empty list to store articulation points
  • implement a graph representation (adjacency list or matrix)
  • initialize arrays to track visited status, discovery time, and low values for vertices
• Traverse the graph
  • start DFS or BFS traversal from any vertex
  • during traversal, mark vertices as visited and update discovery time
  • keep track of the lowest discovery time reachable from each vertex (low value)
• Identify Articulation Points
  • in DFS, maintain a parent array to keep track of the parent of each vertex
  • for each vertex, traverse its adjacent vertices
  • if a vertex's child has a lower discovery time than the current vertex's low value, update the low value
  • if the current vertex is the root of the DFS tree and has more than one child, it's an articulation point
  • if the current vertex is not the root and has a child with a discovery time less than or equal to its low value, it's an articulation point Output
  • output the list of articulation points identified during traversal

Tips

• utilize efficient data structures for graph representation to optimize traversal
• ensure proper handling of back edges during traversal to accurately determine articulation points
• pay attention to the conditions for identifying articulation points, especially considering the root vertex and its children

Practice

Practice

function findArticulationPoints(graph):
  // Initialization
  articulationPoints = []
  visited = [False] * (number of vertices)
  discoveryTime = [0] * (number of vertices)
  low = [float('inf')] * (number of vertices)
  parent = [-1] * (number of vertices)
  time = 0

  // DFS traversal
  for vertex in range(number of vertices):
    if not visited[vertex]:
      dfsArticulationPoints(graph, vertex, visited, discoveryTime, low, parent, articulationPoints)

  return articulationPoints

function dfsArticulationPoints(graph, vertex, visited, discoveryTime, low, parent, articulationPoints):
  // Initialization
  visited[vertex] = True
  children = 0
  discoveryTime[vertex] = time
  low[vertex] = time
  time += 1

  // Traverse adjacent vertices
  for adjacentVertex in graph[vertex]:
    if not visited[adjacentVertex]:
      children += 1
      parent[adjacentVertex] = vertex
      dfsArticulationPoints(graph, adjacentVertex, visited, discoveryTime, low, parent, articulationPoints)

      // Update low value
      low[vertex] = min(low[vertex], low[adjacentVertex])

      // Check if vertex is articulation point
      if parent[vertex] == -1 and children > 1:
        articulationPoints.append(vertex)
      if parent[vertex] != -1 and low[adjacentVertex] >= discoveryTime[vertex]:
        articulationPoints.append(vertex)
    elif adjacentVertex != parent[vertex]:
      low[vertex] = min(low[vertex], discoveryTime[adjacentVertex])

Solution

package main

type Graph map[int][]int

func dfs(u int, visited map[int]bool, parent map[int]int, low map[int]int, disc map[int]int, ap map[int]bool, g Graph) {
    children := 0
    visited[u] = true
    disc[u] = disc[parent[u]] + 1
    low[u] = disc[u]

    for _, v := range g[u] {
        if !visited[v] {
            children++
            parent[v] = u
            dfs(v, visited, parent, low, disc, ap, g)
            low[u] = min(low[u], low[v])
            if parent[u] != -1 && low[v] >= disc[u] {
                ap[u] = true
            }
        } else if v != parent[u] {
            low[u] = min(low[u], disc[v])
        }
    }

    if parent[u] == -1 && children > 1 {
        ap[u] = true
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func findArticulationPoints(g Graph) []int {
    visited := make(map[int]bool)
    parent := make(map[int]int)
    disc := make(map[int]int)
    low := make(map[int]int)
    ap := make(map[int]bool)

    for v := range g {
        visited[v] = false
        parent[v] = -1
        disc[v] = 0
        low[v] = 0
        ap[v] = false
    }

    for v := range g {
        if !visited[v] {
            dfs(v, visited, parent, low, disc, ap, g)
        }
    }

    result := []int{}
    for v := range g {
        if ap[v] {
            result = append(result, v)
        }
    }
    return result
}

import java.util.*;

class ArticulationPoints {

  private final int NIL = -1;
  private int time;

  private void dfs(int u, boolean[] visited, int[] disc, int[] low, int[] parent, boolean[] ap, List<Integer>[] graph) {
    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;

    for (int v : graph[u]) {
      if (!visited[v]) {
        children++;
        parent[v] = u;
        dfs(v, visited, disc, low, parent, ap, graph);
        low[u] = Math.min(low[u], low[v]);
        if (parent[u] == NIL && children > 1 || parent[u] != NIL && low[v] >= disc[u]) {
          ap[u] = true;
        }
      } else if (v != parent[u]) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  public List<Integer> findArticulationPoints(List<Integer>[] graph, int V) {
    boolean[] visited = new boolean[V];
    int[] disc = new int[V];
    int[] low = new int[V];
    int[] parent = new int[V];
    boolean[] ap = new boolean[V];
    time = 0;

    Arrays.fill(parent, NIL);

    for (int i = 0; i < V; i++) {
      if (!visited[i]) {
        dfs(i, visited, disc, low, parent, ap, graph);
      }
    }

    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < V; i++) {
      if (ap[i]) {
        result.add(i);
      }
    }
    return result;
  }
}

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Array(vertices).fill(null).map(() => []);
  }

  addEdge(u, v) {
    this.adj[u].push(v);
    this.adj[v].push(u);
  }

  dfs(u, visited, parent, low, disc, ap) {
    let children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++this.time;

    for (const v of this.adj[u]) {
      if (!visited[v]) {
        children++;
        parent[v] = u;
        this.dfs(v, visited, parent, low, disc, ap);
        low[u] = Math.min(low[u], low[v]);
        if (
          (parent[u] === -1 && children > 1) ||
          (parent[u] !== -1 && low[v] >= disc[u])
        ) {
          ap[u] = true;
        }
      } else if (v !== parent[u]) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  findArticulationPoints() {
    const visited = new Array(this.V).fill(false);
    const parent = new Array(this.V).fill(-1);
    const disc = new Array(this.V).fill(0);
    const low = new Array(this.V).fill(0);
    const ap = new Array(this.V).fill(false);
    this.time = 0;

    for (let i = 0; i < this.V; i++) {
      if (!visited[i]) {
        this.dfs(i, visited, parent, low, disc, ap);
      }
    }

    const result = [];
    for (let i = 0; i < this.V; i++) {
      if (ap[i]) {
        result.push(i);
      }
    }
    return result;
  }
}

class Graph(private val V: Int) {
    private val adj: Array<MutableList<Int>> = Array(V) { mutableListOf() }
    private var time = 0

    fun addEdge(u: Int, v: Int) {
        adj[u].add(v)
        adj[v].add(u)
    }

    private fun dfs(u: Int, visited: BooleanArray, parent: IntArray, low: IntArray, disc: IntArray, ap: BooleanArray) {
        var children = 0
        visited[u] = true
        disc[u] = ++time
        low[u] = disc[u]

        for (v in adj[u]) {
            if (!visited[v]) {
                children++
                parent[v] = u
                dfs(v, visited, parent, low, disc, ap)
                low[u] = minOf(low[u], low[v])
                if ((parent[u] == -1 && children > 1) || (parent[u] != -1 && low[v] >= disc[u])) {
                    ap[u] = true
                }
            } else if (v != parent[u]) {
                low[u] = minOf(low[u], disc[v])
            }
        }
    }

    fun findArticulationPoints(): List<Int> {
        val visited = BooleanArray(V)
        val parent = IntArray(V) { -1 }
        val disc = IntArray(V)
        val low = IntArray(V)
        val ap = BooleanArray(V)

        for (i in 0 until V) {
            if (!visited[i]) {
                dfs(i, visited, parent, low, disc, ap)
            }
        }

        return ap.indices.filter { ap[it] }
    }
}

class Graph:
    def __init__(self, V):
        self.V = V
        self.adj = [[] for _ in range(V)]
        self.time = 0

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def dfs(self, u, visited, parent, low, disc, ap):
        children = 0
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.adj[u]:
            if not visited[v]:
                children += 1
                parent[v] = u
                self.dfs(v, visited, parent, low, disc, ap)
                low[u] = min(low[u], low[v])
                if (parent[u] == -1 and children > 1) or (parent[u] != -1 and low[v] >= disc[u]):
                    ap[u] = True
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def find_articulation_points(self):
        visited = [False] * self.V
        parent = [-1] * self.V
        disc = [float("inf")] * self.V
        low = [float("inf")] * self.V
        ap = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                self.dfs(i, visited, parent, low, disc, ap)

        return [i for i in range(self.V) if ap[i]]

use std::collections::HashMap;

struct Graph {
    vertices: usize,
    adj_list: HashMap<usize, Vec<usize>>,
    time: usize,
}

impl Graph {
    fn new(vertices: usize) -> Self {
        Graph {
            vertices,
            adj_list: HashMap::new(),
            time: 0,
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.adj_list.entry(u).or_insert(Vec::new()).push(v);
        self.adj_list.entry(v).or_insert(Vec::new()).push(u);
    }

    fn dfs(
        &mut self,
        u: usize,
        visited: &mut Vec<bool>,
        parent: &mut Vec<isize>,
        disc: &mut Vec<usize>,
        low: &mut Vec<usize>,
        ap: &mut Vec<bool>,
    ) {
        let mut children = 0;
        visited[u] = true;
        disc[u] = self.time;
        low[u] = self.time;
        self.time += 1;

        for &v in self.adj_list.get(&u).unwrap().iter() {
            if !visited[v] {
                children += 1;
                parent[v] = u as isize;
                self.dfs(v, visited, parent, disc, low, ap);
                low[u] = low[u].min(low[v]);
                if (parent[u] == -1 && children > 1) || (parent[u] != -1 && low[v] >= disc[u]) {
                    ap[u] = true;
                }
            } else if v as isize != parent[u] {
                low[u] = low[u].min(disc[v]);
            }
        }
    }

    fn find_articulation_points(&mut self) -> Vec<usize> {
        let mut visited = vec![false; self.vertices];
        let mut parent = vec![-1; self.vertices];
        let mut disc = vec![0; self.vertices];
        let mut low = vec![0; self.vertices];
        let mut ap = vec![false; self.vertices];

        for i in 0..self.vertices {
            if !visited[i] {
                self.dfs(i, &mut visited, &mut parent, &mut disc, &mut low, &mut ap);
            }
        }

        ap.iter()
            .enumerate()
            .filter_map(|(i, &b)| if b { Some(i) } else { None })
            .collect()
    }
}

class Graph {
  V: number;
  adj: Map<number, number[]>;
  time: number;

  constructor(V: number) {
    this.V = V;
    this.adj = new Map();
    this.time = 0;
    for (let i = 0; i < V; i++) {
      this.adj.set(i, []);
    }
  }

  addEdge(u: number, v: number) {
    this.adj.get(u).push(v);
    this.adj.get(v).push(u);
  }

  dfs(
    u: number,
    visited: boolean[],
    parent: number[],
    disc: number[],
    low: number[],
    ap: boolean[],
  ) {
    let children = 0;
    visited[u] = true;
    disc[u] = this.time;
    low[u] = this.time;
    this.time++;

    for (const v of this.adj.get(u)!) {
      if (!visited[v]) {
        children++;
        parent[v] = u;
        this.dfs(v, visited, parent, disc, low, ap);
        low[u] = Math.min(low[u], low[v]);
        if (
          (parent[u] === -1 && children > 1) ||
          (parent[u] !== -1 && low[v] >= disc[u])
        ) {
          ap[u] = true;
        }
      } else if (v !== parent[u]) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  findArticulationPoints(): number[] {
    const visited: boolean[] = new Array(this.V).fill(false);
    const parent: number[] = new Array(this.V).fill(-1);
    const disc: number[] = new Array(this.V).fill(0);
    const low: number[] = new Array(this.V).fill(0);
    const ap: boolean[] = new Array(this.V).fill(false);

    for (let i = 0; i < this.V; i++) {
      if (!visited[i]) {
        this.dfs(i, visited, parent, disc, low, ap);
      }
    }

    return ap.map((val, idx) => (val ? idx : -1)).filter((val) => val !== -1);
  }
}