Search for strong connectivity components: Kosarayu algorithm
Instead of introduction: I found that there are no articles in the community about any search algorithm for strongly related components. Therefore, I decided to update the Habr's database with a small article.
Immediately to the point:
Recall the basic definitions:
An example of a strongly connected graph:
Notice, that:
')
Then, a strong connected component is the equivalence class of the set of vertices of an oriented graph with respect to the strong connected relation.
So, our task is to find all such equivalence classes.
Kosarayu algorithm
The Kosarayu method is simple enough to implement and understand. The idea is that the original graph and its inversion match the components of strong connectivity (because they are essentially cycles).
Let a directed graph G = (V, E) be given.
G '= (V, E') is a graph obtained by inverting the original graph G
Now perform a depth search on G '. We will mark the entry time and exit time (in / out). Let's additionally create an array of vertices. Add all vertices to it in order of increasing exit time. Thus, the verticles array will look like this:
Now we will start a detour to the outback on the source graph, but each time choosing to go around the not yet visited vertex with the maximum index in the array of verticles. All vertices visited during one iteration of dfs form a connected component (marked with colors).
Instead of concluding:
Note that if a graph is represented by an adjacency graph, then we do not need an inverted graph, we can work on the same graph. Otherwise, we need O (V + E) to get an inverted graph and another V + E memory for storing an inverted graph.
However, the main part of the algorithm consists of two DFS traversals. Each works in proportion to V + E for sparse graphs and V ^ 2 for saturated graphs. We also need V memory to store an array of vertices.
Immediately to the point:
Recall the basic definitions:
- Two peaks ( $ inline $ u $ inline $ and $ inline $ v $ inline $ ) a directed graph is called strongly connected if there exists a path from $ inline $ u $ inline $ at $ inline $ v $ inline $ and there is a way out $ inline $ v $ inline $ at $ inline $ u $ inline $ .
- A directed graph is said to be strongly connected if any two of its vertices are strongly connected.
- Inverting a directed graph, we call the procedure in which we change the direction of each edge to the opposite
An example of a strongly connected graph:
Notice, that:
')
A strong connectivity relation is an equivalence relation.
$ inline $ 1) Reflexivity: \ \ forall v \ v \ to v $ inline $
$ inline $ 2) Symmetry: \ \ forall v \ \ forall u \ v \ to u => u \ to v $ inline $
$ inline $ 3) Transitivity: \ forall v \ \ forall u \ \ forall t \ v \ to u \ \ wedge u \ to t => v \ to t $ inline $
$ inline $ 2) Symmetry: \ \ forall v \ \ forall u \ v \ to u => u \ to v $ inline $
$ inline $ 3) Transitivity: \ forall v \ \ forall u \ \ forall t \ v \ to u \ \ wedge u \ to t => v \ to t $ inline $
Then, a strong connected component is the equivalence class of the set of vertices of an oriented graph with respect to the strong connected relation.
So, our task is to find all such equivalence classes.
Kosarayu algorithm
The Kosarayu method is simple enough to implement and understand. The idea is that the original graph and its inversion match the components of strong connectivity (because they are essentially cycles).
Let a directed graph G = (V, E) be given.
G '= (V, E') is a graph obtained by inverting the original graph G
Now perform a depth search on G '. We will mark the entry time and exit time (in / out). Let's additionally create an array of vertices. Add all vertices to it in order of increasing exit time. Thus, the verticles array will look like this:
Now we will start a detour to the outback on the source graph, but each time choosing to go around the not yet visited vertex with the maximum index in the array of verticles. All vertices visited during one iteration of dfs form a connected component (marked with colors).
Instead of concluding:
Note that if a graph is represented by an adjacency graph, then we do not need an inverted graph, we can work on the same graph. Otherwise, we need O (V + E) to get an inverted graph and another V + E memory for storing an inverted graph.
However, the main part of the algorithm consists of two DFS traversals. Each works in proportion to V + E for sparse graphs and V ^ 2 for saturated graphs. We also need V memory to store an array of vertices.
Source: https://habr.com/ru/post/331904/
All Articles