How to resolve the algorithm Kosaraju step by step in the Go programming language
How to resolve the algorithm Kosaraju step by step in the Go programming language
Table of Contents
Problem Statement
Kosaraju's algorithm (also known as the Kosaraju–Sharir algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju. The same algorithm was independently discovered by Micha Sharir and published by him in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
For this task consider the directed graph with these connections: And report the kosaraju strongly connected component for each node.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Kosaraju step by step in the Go programming language
- The input to the function is a graph
g
represented as a map from vertices to their adjacent vertices. - The function first performs a depth-first search on the graph to create a topological ordering of the vertices.
- It then creates a transpose of the graph, where the edges are reversed.
- Finally, it performs a second depth-first search on the transpose graph, starting from the vertices in topological order.
- As it visits each vertex, it assigns it to the strongly connected component that it belongs to.
- The function returns a slice
c
of integers, where each element represents the strongly connected component that the corresponding vertex belongs to.
Example: Consider the following graph:
0 -> 1
1 -> 2
2 -> 0
3 -> 1
3 -> 2
3 -> 4
4 -> 3
4 -> 5
5 -> 2
5 -> 6
6 -> 5
7 -> 4
7 -> 6
7 -> 7
This graph has three strongly connected components:
{0, 1, 2}
,{3, 4, 5}
,{6, 7}
.
The function kosaraju
will return the following slice c
:
[0, 0, 0, 1, 1, 1, 2, 2, 2]
where the index of each element corresponds to a vertex in the graph, and the value of each element represents the strongly connected component that the corresponding vertex belongs to.
Source code in the go programming language
package main
import "fmt"
var g = [][]int{
0: {1},
1: {2},
2: {0},
3: {1, 2, 4},
4: {3, 5},
5: {2, 6},
6: {5},
7: {4, 6, 7},
}
func main() {
fmt.Println(kosaraju(g))
}
func kosaraju(g [][]int) []int {
// 1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
vis := make([]bool, len(g))
L := make([]int, len(g))
x := len(L) // index for filling L in reverse order
t := make([][]int, len(g)) // transpose graph
// 2. recursive subroutine:
var Visit func(int)
Visit = func(u int) {
if !vis[u] {
vis[u] = true
for _, v := range g[u] {
Visit(v)
t[v] = append(t[v], u) // construct transpose
}
x--
L[x] = u
}
}
// 2. For each vertex u of the graph do Visit(u)
for u := range g {
Visit(u)
}
c := make([]int, len(g)) // result, the component assignment
// 3: recursive subroutine:
var Assign func(int, int)
Assign = func(u, root int) {
if vis[u] { // repurpose vis to mean "unassigned"
vis[u] = false
c[u] = root
for _, v := range t[u] {
Assign(v, root)
}
}
}
// 3: For each element u of L in order, do Assign(u,u)
for _, u := range L {
Assign(u, u)
}
return c
}
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Prime triangle step by step in the Raku programming language
You may also check:How to resolve the algorithm Dynamic variable names step by step in the Scheme programming language
You may also check:How to resolve the algorithm One-dimensional cellular automata step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Decorate-sort-undecorate idiom step by step in the Julia programming language