A brief introduction of Tarjan and SCC

Правка en1, от RDFZzzx, 2022-07-30 17:49:11

Definiation : What is SCC

"SCC" means "strongly connected components.

In a directed graph , the nodes in the same SCC can visit each other.

In an easy way of understanding, if node $$$x$$$ and node $$$y$$$ are in the same SCC, there is a path from $$$x$$$ to $$$y$$$ and a path from $$$y$$$ to $$$x$$$.

For example, in this graph, nodes in same color are in the same SCC:

Tarjan

Tarjan is one of the algorithms which can solve this problems.

First I am going to introduce two arrays to you:

  • $$$low_x$$$: An array of trace values representing the minimum idx of points on a search tree rooted at $$$x$$$ which can be reached by only one edge which is not in the search tree.

  • $$$dfn_x$$$: Timestamp array, representing the order it was visited.

For example we can get the two values of the nodes:

How to calculate $$$low_x$$$?

We assume that there is an undirected edge from the node $$$x$$$ to the node $$$y$$$. There are two conditions:

  • First: If node $$$y$$$ is a node of the subtree of node $$$x$$$, so low[x] = min(low[x], low[y]);
  • Secound: Else low[x] = min(low[x], dfn[y]);

Node that: In the secound condition, it is $$$dfn_y$$$, and it isn't $$$low_y$$$.

We should look back to the defination:

by only one edge which is not in the search tree

Only one edge!

How to find SCC base on $$$low$$$ and $$$dfn$$$?

Lets look back to the sample:

We can find that in each SCC there is a "head" which $$$low_x = dfn_x$$$. In this graph, the "heads" are node $$$1$$$ and node $$$3$$$.

We can use a stack to put the nodes we visited. When we get a "head", we should pop the elements in the stack and put them in the same SCC.

Lets read the sample together:

node we meet nodes in the stack "head" SCC
$$$1$$$ $$$1$$$
$$$2$$$ $$$1\ 2$$$
$$$5$$$ $$$1 \ 2 \ 5$$$
$$$4$$$ $$$1 \ 2 \ 5 \ 4$$$ There is an edge from $$$4$$$ to $$$1$$$, and we find a "head" node $$$1$$$
pop the stack $$$empty$$$ $$$1 \ 2 \ 5 \ 4$$$
$$$3$$$ $$$3$$$ $$$low_3 = dfn_3 = 5$$$, so node $$$3$$$ is a "head"
pop the stack $$$empty$$$ $$$1 \ 2 \ 5 \ 4 \ and \ 3$$$

In this way, we can find the SCCs.

code in c++

void tarjan(int node)
{
	printf("%d ", node);
	stack[top++] = node;
	low[node] = dfn[node] = ++id;
	for (int i = head[node]; i; i = e[i].nxt)
	{
		int to = e[i].to;
		if (dfn[to] == 0)
		{
			tarjan(to);
			low[node] = min(low[node], low[to]);
		}
		else if (scc[to] == 0)
			low[node] = min(low[node], dfn[to]);
	}
	if (low[node] == dfn[node])
	{
		++color_cnt;
		ans.push_back(vector <int>());
		while (true)
		{
			int to = stack[--top];
			ans[color_cnt-1].push_back(to);
			scc[to] = color_cnt;
			if (node == to) break;
		}
	}
}

Recommend : More about connected components

If you want to learn more about connected components, can can read this aritical : A brief introduction of Tarjan and E-DCC(EBC).

Теги connected component, strongly connected, graphs, algorithms, tarjan

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский RDFZzzx 2022-07-30 18:11:48 7 Tiny change: '| node we meet | nodes ' -> '| node we visit | nodes '
en2 Английский RDFZzzx 2022-07-30 17:56:07 156
en1 Английский RDFZzzx 2022-07-30 17:49:11 3301 Initial revision (published)