Anonymous user
Tarjan: Difference between revisions
no edit summary
(Tarjan's strongly connected components algorithm) |
No edit summary |
||
Line 2:
{{wikipedia|Graph}}
[[Category:Algorithm]]
<br>
Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's Algorithm is named for its discoverer, Robert Tarjan.
<br>
;References:
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]].
=={{header|C sharp|C#}}==
<lang csharp>using System;
using System.Collections.Generic;
class Node
{
public int LowLink { get; set; }
public int Index { get; set; }
private int N_;
public int N
{
get
{
return N_;
}
}
public Node(int n)
{
N_ = n;
Index = -1;
LowLink = 0;
}
}
class Graph
{
public HashSet<Node> V { get; set; }
public Dictionary<Node, HashSet<Node>> Adj { get; set; }
/// <summary>
/// Tarjan's strongly connected components algorithm
/// </summary>
public void Tarjan()
{
var index = 0; // number of nodes
var S = new Stack<Node>();
Action<Node> StrongConnect = null;
StrongConnect = v =>
{
// Set the depth index for v to the smallest unused index
v.Index = index;
v.LowLink = index;
index++;
S.Push(v);
// Consider successors of v
foreach (var w in Adj[v])
if (w.Index < 0)
{
// Successor w has not yet been visited; recurse on it
StrongConnect(w);
v.LowLink = Math.Min(v.LowLink, w.LowLink);
}
else if (S.Contains(w))
// Successor w is in stack S and hence in the current SCC
v.LowLink = Math.Min(v.LowLink, w.Index);
// If v is a root node, pop the stack and generate an SCC
if (v.LowLink == v.Index)
{
Console.Write("SCC: ");
Node w;
do
{
w = S.Pop();
Console.Write(w.N + " ");
} while (w.N != v.N);
Console.WriteLine("");
}
};
foreach (var v in V)
if (v.Index < 0)
StrongConnect(v);
}
}</lang>
| |||