Kosaraju Sharir SCC Algorithm

The Kosaraju-Sharir algorithm is a linear-time algorithm used for finding the strongly connected components (SCCs) in a directed graph. Strongly connected components are subgraphs where every pair of nodes, u and v, are connected by a path from u to v and a path from v to u. Developed independently by S. Rao Kosaraju and Micha A. Sharir in 1979, the algorithm is based on the idea of performing two depth-first search (DFS) traversals on a given graph to identify the SCCs. The algorithm has several applications, including identifying cycles in graphs, analyzing social networks, and solving problems in computer networks and compilers.

The Kosaraju-Sharir algorithm works by first performing a DFS traversal on the original graph, marking the finish time of each node in a stack. The graph is then transposed, meaning that all the edges are reversed. A second DFS traversal is performed on the transposed graph, exploring nodes in the order of their finish times from the first DFS traversal. Each tree generated during this second DFS traversal corresponds to a strongly connected component. By exploiting the properties of SCCs and the transposed graph, the Kosaraju-Sharir algorithm efficiently identifies all the SCCs in linear time, making it an essential tool in graph theory and computer science.

 package org.gs.digraph
 
import scala.annotation.tailrec
 
/** Compute strongly-connected components of a digraph
  *
  * @constructor creates a new KosarajuSharirSCC with a digraph
  * @param g digraph
  * @see [[https://algs4.cs.princeton.edu/42directed/KosarajuSharirSCC.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
class KosarajuSharirSCC(g: Digraph) {
  private val depthFirstOrder = new DepthFirstOrder(g.reverse)
  private val marked = Array.fill[Boolean](g.numV)(false)
  private val _id = new Array[Int](g.numV)
 
  @tailrec
  private def searchUnmarked(count: Int, rp: List[Int]): Int = rp match {
    case v :: xs => if (!marked(v)) {
      dfs(v, count)
      searchUnmarked(count + 1, xs)
    } else searchUnmarked(count, xs)
    case Nil => count
  }
 
  /** returns number of strong components */
  val count = searchUnmarked(0, depthFirstOrder.reversePost)
 
  private def dfs(v: Int, count: Int): Unit = {
    marked(v) = true
    _id(v) = count
    g.adj(v) foreach (w => if (!marked(w)) dfs(w, count))
  }
 
  /** returns if  v and  w are strongly connected */
  def stronglyConnected(v: Int, w: Int): Boolean = _id(v) == _id(w)
 
  /** returns component id of  v vertex */
  def id(v: Int): Int = _id(v)
}

Kosaraju Sharir SCC Algorithm

LANGUAGE:

DARK MODE:

PROGRAMMING LANGUAGES:

Python

Java

Javascript

C#

C++

C

Ruby

Scala

MATLAB

Kotlin

Rust

R

Go

	package org.gs.digraph

	import scala.annotation.tailrec

	/** Compute strongly-connected components of a digraph
	*
	* @constructor creates a new KosarajuSharirSCC with a digraph
	* @param g digraph
	* @see [[https://algs4.cs.princeton.edu/42directed/KosarajuSharirSCC.java.html]]
	* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
	*/
	class KosarajuSharirSCC(g: Digraph) {
	private val depthFirstOrder = new DepthFirstOrder(g.reverse)
	private val marked = Array.fill[Boolean](g.numV)(false)
	private val _id = new Array[Int](g.numV)

	@tailrec
	private def searchUnmarked(count: Int, rp: List[Int]): Int = rp match {
	case v :: xs => if (!marked(v)) {
	dfs(v, count)
	searchUnmarked(count + 1, xs)
	} else searchUnmarked(count, xs)
	case Nil => count
	}

	/** returns number of strong components */
	val count = searchUnmarked(0, depthFirstOrder.reversePost)

	private def dfs(v: Int, count: Int): Unit = {
	marked(v) = true
	_id(v) = count
	g.adj(v) foreach (w => if (!marked(w)) dfs(w, count))
	}

	/** returns if v and w are strongly connected */
	def stronglyConnected(v: Int, w: Int): Boolean = _id(v) == _id(w)

	/** returns component id of v vertex */
	def id(v: Int): Int = _id(v)
	}