Strongly connected components (SCC)

Definition

Stronly connected component(SCC)的定義為component中任兩個點都相連(connected)。

Pseudo code

STRONGLY-CONNECTED-COMPONENTS(G)
1. call DFS(G) to compute finish times u.f for each vertex u
2. create G^T
3. call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing u.f (as computed in line 1)
4. output the vertices of each tree in the depth-first forest in line 3 as a separate strongly connected component

Proofs

Lemma 1

Statement: Let $C$ and $C'$ be distinct strongly connected components in directed graph $G = (V, E)$，let $u', v' \in C'$, and suppose that $G$ contains a path $u\overset p\leadsto u'$. Then G cannot conotain a path $v'\overset p \leadsto v$

Proof:

如果$v'\overset p \leadsto v$，則存在路徑$u\leadsto u' \leadsto v'$和$v' \leadsto v \leadsto u$，代表$u$可以reach到 $v'$，且$v'$也可以到$u$，與假設 $C$, $C'$是兩個SCC矛盾。

Lemma 2

Statement: Let $C$ and $C'$ be distinct strongly connected components in directed graph $G = (V, E)$。Suppose, that there is an edge $(u, v) \in E$, where $u \in C'$ and $v \in C$. Then $f(C') > f(C)$

Proof: 我們假設兩個情況：

1. $C'$先被探訪
2. $C$先被探訪

在第一種情況，因為edge $(u, v)$，所以$C$必定先被玩成 $u$才會完成，故$f(C') > f(C)$。在第二種情況，因為不存在路徑使$C$可以reach $C'$，所以$C$先完成，然後才探訪$C'$，故$f(C') > f(C)$。

由以上兩種狀況可得證， $f(C') > f(C)$。

Corollary

Statement: Let $C$ and $C'$ be distinct strongly connected components in directed graph $G = (V, E)$，and suppose that $f(C) > f(C')$. Then $E^T$ contains no edge $(v, u) \in E^T$ such that $u \in C'$ and $v \in C$。

Proof:

根據Lemma 1，如果$E^T$含有edge $(v, u)$，則代表$E$含有edge $(u, v)$，而這與Lemma 2矛盾，所以$G^T$不含有edge $(u, v)$。

Theorem 1

Statement: The STRONGLY-CONNECTED-COMPONENTS procedure correctly computes the strongly connected components of the directed graph G provided as its input。

Proof:

我們可以用induction來證明。假設圖有$k$個SCC，當$k = 0$很明顯得證，假設$k = n$的時候也成立，我們嘗試證明$k = n+1$也成立。

根據STRONGLY-CONNECTED-COMPONENTS line 3，我們根據$v.f$的值，由大到小在$G^T$做DFS。而根據Lemma 2，如果$f(C') > f(C)$，代表$G$存在一個edge $(u, v)$，$u \in C', v \in C$，或是兩個SCC之間沒有edge存在。

不管是何種情況，在$G^T$都不存在一組edge $(v, u)$, $u \in C', v \in C$，因此DFS走訪完第k+1個scc後也會停止，故$k = n+1$也成立，故得證。

Time complexity

$\Theta$($V + E$)。在line 1做了一次DFS，take $\Theta$($V + E$)，在line 2將圖transpose，也take $\Theta$($V + E$)，line 3又做了一次DFS，所以total的time complexity是 $\Theta$($V + E$)。

Golang implementation

scc.go

import "fmt"

type Vertex struct {
  finished bool
  idx int
}

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

// dfsUtil returns vertices with finish in reverse order
func dfsUtil(g Graph, v Vertex, result []Vertex) []Vertex{
  for _, neighbor := range g.edges[v.idx] {
    // has been visited
    if neighbor.finished {
      continue
    }

    result = dfsUtil(g, neighbor, result)
  }

  v.finished = true
  result = append([]Vertex{v}, result...)

  return result
}

func transpose(g Graph) Graph {
  gTranspose := Graph{
    edges: map[int][]Vertex{}
  }

  // init vertices
  for vIdx := range g.vertices {
    gTranspose.vertices[vIdx] = Vertex {
      idx: vIdx,
    }
  }

  // build edges
  for vIdx, edges := range g.edges {
    v := gTranspose.vertices[vIdx]

    for _, neighbor := range edges {
      if _, ok := gTranspose.edges[neighbor.idx] {
        gTranspose.edges[neighbor.idx] = []Vertex{}
      }

      // reverse the edge direction
      gTranspose.edges[neighbor.idx] = append(gTranspose.edges[neighbor.idx], v)
    }
  }

  return gTranspose
}

func sccUtil(g, gTranspose Graph, v Vertex, sccResults []Graph, sccComponent *Graph) []Graph {
  var shouldAddToResult bool
  if sccComponent == nil {
    sccComponent = &Graph{}
    shouldAddToResult = true
  }

  for _, neighbor := range gTranspose.edges[v.idx] {
    if neighbor.finished {
      continue
    }

    sccResults = sccUtil(g, neighbor, sccResults, sccComponent)
  }

  neighbor.finsihed = true

  // add the vertex and its edges to the SCC component
  sccComponent.vertices[v.idx] = v
  sccComponent.edges[v.idx] = []Vertex{}
  for _, edge := range g.edges[v.idx] {
    sccComponent.edges[v.idx] = append(sccComponent.edges[v.idx], edge)
  }

  if shouldAddToResult {
    sccResult = append(sccResult, *sccComponent)
  }

  return sccResult
} 

func SCC(g Graph) []Vertex {
  // do DFS to g
  verticesInReverseVisitedOrder := []Vertex{}

  for vIdx, v := range g.vertices {
    if v.finished {
      continue
    }

    verticesInReverseVisitedOrder = dfsUtil(g, vIdx, verticesInReverseVisitedOrder)
  }

  // compose graph transpose
  gTranspose := transpose(g)

  // do dfs to gTranspose with finish time in reverse order
  results := []Graph{}
  for _, v := range verticesInReverseVisitedOrder {
    vInTranspose := gTranspose.vertices[v.idx]

    if vInTranspose.finished {
      continue
    }

    results = sccUtil(g, gTranspose, results, nil)
  }

  return results
}