Strongly Connected Components - Kosaraju's Algorithm

Definition

Definition

Kosaraju's Algorithm is a method used to find strongly connected components (SCCs) within a directed graph. It efficiently identifies groups of vertices where each vertex is reachable from every other vertex within the same group. This algorithm relies on depth-first search (DFS) techniques to traverse the graph twice, first to determine the order of vertices for the second traversal, and then to identify the SCCs

Explanation

Operates in 2 main phases. First, it performs a DFS on the given graph to determine the order in which vertices should be processed. Then, it transposes the graph (reverses the direction of all edges) and performs another DFS based on the determined order to identify the strongly connected components

Guidance

• Start with a directed graph represented as an adjacency list or matrix
• Perform a DFS traversal on the graph, keeping track of the order in which vertices finish their recursive calls
• Reverse the direction of all edges in the graph to create a transposed graph
• Perform another DFS traversal on the transposed graph, using the order obtained from the first traversal
• Each tree in the DFS forest of the transposed graph represents a strongly connected component

Tips

• ensure proper implementation of the DFS algorithm with appropriate data structures (such as stacks or recursion)
• pay attention to the order of vertices obtained in the first traversal as it determines the sequence for the second traversal
• utilize efficient data structures for tracking visited vertices and storing the SCCs

Practice

Practice

kosaraju(graph):
    order = [] # to store the order of vertices
    visited = set() # set to keep track of visited vertices

    # Phase 1: Perform DFS to determine the order of vertices
    for each vertex in graph:
        if vertex not in visited:
            DFS(graph, vertex, visited, order)

    # Transpose the graph
    transposed_graph = transpose(graph)

    # Phase 2: Perform DFS on the transposed graph in the determined order
    visited.clear()
    SCCs = []
    while order is not empty:
        vertex = order.pop()
        if vertex not in visited:
            SCC = []
            DFS(transposed_graph, vertex, visited, SCC)
            SCCs.append(SCC)

    return SCCs

DFS(graph, vertex, visited, result):
    visited.add(vertex)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            DFS(graph, neighbor, visited, result)
    result.append(vertex)

transpose(graph):
    transposed_graph = {}
    for vertex in graph:
        transposed_graph[vertex] = []
    for vertex in graph:
        for neighbor in graph[vertex]:
            transposed_graph[neighbor].append(vertex)
    return transposed_graph

Solution

package main

type Graph struct {
    vertices int
    edges    [][]int
}

func NewGraph(vertices int) *Graph {
    return &Graph{
        vertices: vertices,
        edges:    make([][]int, vertices),
    }
}

func (g *Graph) AddEdge(u, v int) {
    g.edges[u] = append(g.edges[u], v)
}

func (g *Graph) dfsUtil(vertex int, visited []bool, stack *Stack) {
    visited[vertex] = true
    for _, adj := range g.edges[vertex] {
        if !visited[adj] {
            g.dfsUtil(adj, visited, stack)
        }
    }
    stack.Push(vertex)
}

func (g *Graph) getTranspose() *Graph {
    transpose := NewGraph(g.vertices)
    for i := 0; i < g.vertices; i++ {
        for _, adj := range g.edges[i] {
            transpose.AddEdge(adj, i)
        }
    }
    return transpose
}

func (g *Graph) fillOrder(vertex int, visited []bool, stack *Stack) {
    visited[vertex] = true
    for _, adj := range g.edges[vertex] {
        if !visited[adj] {
            g.fillOrder(adj, visited, stack)
        }
    }
    stack.Push(vertex)
}

func (g *Graph) Kosaraju() {
    stack := NewStack()
    visited := make([]bool, g.vertices)

    for i := 0; i < g.vertices; i++ {
        if !visited[i] {
            g.dfsUtil(i, visited, stack)
        }
    }

    transpose := g.getTranspose()
    for i := range visited {
        visited[i] = false
    }

    for !stack.IsEmpty() {
        vertex := stack.Pop()
        if !visited[vertex] {
            var scc []int
            transpose.fillOrder(vertex, visited, stack)
            for !stack.IsEmpty() {
                v := stack.Pop()
                scc = append(scc, v)
                visited[v] = true
            }
            fmt.Println(scc)
        }
    }
}

type Stack []int

func NewStack() *Stack {
    return &Stack{}
}

func (s *Stack) Push(value int) {
    *s = append(*s, value)
}

func (s *Stack) Pop() int {
    stack := *s
    top := stack[len(stack)-1]
    *s = stack[:len(stack)-1]
    return top
}

func (s *Stack) IsEmpty() bool {
    return len(*s) == 0
}

import java.util.*;

class Graph {

  private int vertices;
  private LinkedList<Integer>[] adj;

  Graph(int vertices) {
    this.vertices = vertices;
    adj = new LinkedList[vertices];
    for (int i = 0; i < vertices; ++i) {
      adj[i] = new LinkedList();
    }
  }

  void addEdge(int v, int w) {
    adj[v].add(w);
  }

  void dfsUtil(int v, boolean[] visited, Stack<Integer> stack) {
    visited[v] = true;
    for (Integer i : adj[v]) {
      if (!visited[i]) {
        dfsUtil(i, visited, stack);
      }
    }
    stack.push(v);
  }

  Graph getTranspose() {
    Graph g = new Graph(vertices);
    for (int v = 0; v < vertices; v++) {
      for (Integer i : adj[v]) {
        g.addEdge(i, v);
      }
    }
    return g;
  }

  void fillOrder(int v, boolean[] visited, Stack<Integer> stack) {
    visited[v] = true;
    for (Integer i : adj[v]) {
      if (!visited[i]) {
        fillOrder(i, visited, stack);
      }
    }
    stack.push(v);
  }

  void printSCCs() {
    Stack<Integer> stack = new Stack<>();

    boolean[] visited = new boolean[vertices];
    for (int i = 0; i < vertices; i++) {
      visited[i] = false;
    }

    for (int i = 0; i < vertices; i++) {
      if (!visited[i]) {
        dfsUtil(i, visited, stack);
      }
    }

    Graph transpose = getTranspose();

    for (int i = 0; i < vertices; i++) {
      visited[i] = false;
    }

    while (!stack.empty()) {
      int v = stack.pop();
      if (!visited[v]) {
        transpose.fillOrder(v, visited, stack);
        System.out.println();
      }
    }
  }
}

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

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

  dfsUtil(v, visited, stack) {
    visited[v] = true;
    for (let i of this.adj[v]) {
      if (!visited[i]) {
        this.dfsUtil(i, visited, stack);
      }
    }
    stack.push(v);
  }

  getTranspose() {
    let g = new Graph(this.vertices);
    for (let v = 0; v < this.vertices; v++) {
      for (let i of this.adj[v]) {
        g.addEdge(i, v);
      }
    }
    return g;
  }

  fillOrder(v, visited, stack) {
    visited[v] = true;
    for (let i of this.adj[v]) {
      if (!visited[i]) {
        this.fillOrder(i, visited, stack);
      }
    }
    stack.push(v);
  }

  printSCCs() {
    let stack = [];

    let visited = new Array(this.vertices).fill(false);
    for (let i = 0; i < this.vertices; i++) {
      if (!visited[i]) {
        this.dfsUtil(i, visited, stack);
      }
    }

    let transpose = this.getTranspose();

    visited = new Array(this.vertices).fill(false);

    while (stack.length !== 0) {
      let v = stack.pop();
      if (!visited[v]) {
        transpose.fillOrder(v, visited, stack);
        console.log();
      }
    }
  }
}

import java.util.*

class Graph(private val vertices: Int) {
    private val adj: Array<LinkedList<Int>> = Array(vertices) { LinkedList() }

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

    private fun dfsUtil(v: Int, visited: BooleanArray, stack: Stack<Int>) {
        visited[v] = true
        for (i in adj[v]) {
            if (!visited[i]) {
                dfsUtil(i, visited, stack)
            }
        }
        stack.push(v)
    }

    private fun getTranspose(): Graph {
        val g = Graph(vertices)
        for (v in 0 until vertices) {
            for (i in adj[v]) {
                g.addEdge(i, v)
            }
        }
        return g
    }

    private fun fillOrder(v: Int, visited: BooleanArray, stack: Stack<Int>) {
        visited[v] = true
        for (i in adj[v]) {
            if (!visited[i]) {
                fillOrder(i, visited, stack)
            }
        }
        stack.push(v)
    }

    fun printSCCs() {
        val stack = Stack<Int>()

        val visited = BooleanArray(vertices)
        for (i in 0 until vertices) {
            visited[i] = false
        }

        for (i in 0 until vertices) {
            if (!visited[i]) {
                dfsUtil(i, visited, stack)
            }
        }

        val transpose = getTranspose()

        for (i in 0 until vertices) {
            visited[i] = false
        }

        while (!stack.isEmpty()) {
            val v = stack.pop()
            if (!visited[v]) {
                transpose.fillOrder(v, visited, stack)
                println()
            }
        }
    }
}

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def dfsUtil(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.dfsUtil(i, visited, stack)
        stack.append(v)

    def getTranspose(self):
        g = Graph(self.V)
        for i in self.graph:
            for j in self.graph[i]:
                g.addEdge(j, i)
        return g

    def fillOrder(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.fillOrder(i, visited, stack)
        stack.append(v)

    def printSCCs(self):
        stack = []
        visited = [False] * self.V
        for i in range(self.V):
            if not visited[i]:
                self.dfsUtil(i, visited, stack)
        gr = self.getTranspose()
        visited = [False] * self.V
        while stack:
            i = stack.pop()
            if not visited[i]:
                gr.fillOrder(i, visited, [])
                print()

use std::collections::LinkedList;
use std::collections::VecDeque;

struct Graph {
    vertices: usize,
    adj: Vec<LinkedList<usize>>,
}

impl Graph {
    fn new(vertices: usize) -> Graph {
        Graph {
            vertices,
            adj: vec![LinkedList::new(); vertices],
        }
    }

    fn add_edge(&mut self, v: usize, w: usize) {
        self.adj[v].push_back(w);
    }

    fn dfs_util(&self, v: usize, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
        visited[v] = true;
        for i in &self.adj[v] {
            if !visited[*i] {
                self.dfs_util(*i, visited, stack);
            }
        }
        stack.push(v);
    }

    fn get_transpose(&self) -> Graph {
        let mut g = Graph::new(self.vertices);
        for v in 0..self.vertices {
            for i in &self.adj[v] {
                g.add_edge(*i, v);
            }
        }
        g
    }

    fn fill_order(&self, v: usize, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
        visited[v] = true;
        for i in &self.adj[v] {
            if !visited[*i] {
                self.fill_order(*i, visited, stack);
            }
        }
        stack.push(v);
    }

    fn print_sccs(&self) {
        let mut stack: Vec<usize> = Vec::new();
        let mut visited: Vec<bool> = vec![false; self.vertices];
        for i in 0..self.vertices {
            if !visited[i] {
                self.dfs_util(i, &mut visited, &mut stack);
            }
        }

        let transpose = self.get_transpose();

        for i in 0..self.vertices {
            visited[i] = false;
        }

        while let Some(v) = stack.pop() {
            if !visited[v] {
                transpose.fill_order(v, &mut visited, &mut Vec::new());
                println!();
            }
        }
    }
}

class Graph {
  private vertices: number;
  private adj: number[][];

  constructor(vertices: number) {
    this.vertices = vertices;
    this.adj = Array.from({ length: vertices }, () => []);
  }

  addEdge(v: number, w: number) {
    this.adj[v].push(w);
  }

  dfsUtil(v: number, visited: boolean[], stack: number[]) {
    visited[v] = true;
    for (let i of this.adj[v]) {
      if (!visited[i]) {
        this.dfsUtil(i, visited, stack);
      }
    }
    stack.push(v);
  }

  getTranspose(): Graph {
    let g = new Graph(this.vertices);
    for (let v = 0; v < this.vertices; v++) {
      for (let i of this.adj[v]) {
        g.addEdge(i, v);
      }
    }
    return g;
  }

  fillOrder(v: number, visited: boolean[], stack: number[]) {
    visited[v] = true;
    for (let i of this.adj[v]) {
      if (!visited[i]) {
        this.fillOrder(i, visited, stack);
      }
    }
    stack.push(v);
  }

  printSCCs() {
    let stack: number[] = [];

    let visited: boolean[] = new Array(this.vertices).fill(false);
    for (let i = 0; i < this.vertices; i++)
      if (!visited[i]) this.dfsUtil(i, visited, stack);

    let transpose = this.getTranspose();

    visited = new Array(this.vertices).fill(false);

    while (stack.length !== 0) {
      let v = stack.pop()!;
      if (!visited[v]) {
        transpose.fillOrder(v, visited, stack);
        console.log();
      }
    }
  }
}