Tarjan算法的非递归版本 [英] Non-recursive version of Tarjan's algorithm
问题描述
我有以下Tarjan算法的（递归）实现，可以在图中找到强连通的组件，并且可以正常工作：
I have the following (recursive) implementation of Tarjan's algorithm to find strongly connected components in a graph and it works fine:
public class StronglyConnectedComponents
{
public static List<List<int>> Search(Graph graph)
{
StronglyConnectedComponents scc = new StronglyConnectedComponents();
return scc.Tarjan(graph);
}
private int preCount;
private int[] low;
private bool[] visited;
private Graph graph;
private List<List<int>> stronglyConnectedComponents = new List<List<int>>();
private Stack<int> stack = new Stack<int>();
public List<List<int>> Tarjan(Graph graph)
{
this.graph = graph;
low = new int[graph.VertexCount];
visited = new bool[graph.VertexCount];
for (int v = 0; v < graph.VertexCount; v++) if (!visited[v]) DFS(v);
return stronglyConnectedComponents;
}
public void DFS(int v)
{
low[v] = preCount++;
visited[v] = true;
stack.Push(v);
int min = low[v];
int edgeCount = graph.OutgoingEdgeCount(v);
for (int i = 0; i < edgeCount; i++)
{
var edge = graph.OutgoingEdge(v, i);
int target = edge.Target;
if (!visited[target]) DFS(target);
if (low[target] < min) min = low[target];
}
if (min < low[v])
{
low[v] = min;
return;
}
List<int> component = new List<int>();
int w;
do
{
w = stack.Pop();
component.Add(w);
low[w] = graph.VertexCount;
} while (w != v);
stronglyConnectedComponents.Add(component);
}
}
但是在大图上，显然，递归版本会抛出StackOverflowException。因此，我想使算法非递归。
But on large graphs, obviously, the recursive version will throw a StackOverflowException. Therefore I want to make the algorithm non-recursive.
我尝试将函数 DFS 替换为以下命令（非递归），但该算法不再起作用。有人可以帮忙吗？
I tried to replace the function DFS with the following (non-recursive) one, but the algorithm doesn't work anymore. Can anybody help?
private void DFS2(int vertex)
{
bool[] visited = new bool[graph.VertexCount];
Stack<int> stack = new Stack<int>();
stack.Push(vertex);
int min = low[vertex];
while (stack.Count > 0)
{
int v = stack.Pop();
if (visited[v]) continue;
visited[v] = true;
int edgeCount = graph.OutgoingEdgeCount(v);
for (int i = 0; i < edgeCount; i++)
{
int target = graph.OutgoingEdge(v, i).Target;
stack.Push(target);
if (low[target] < min) min = low[target];
}
}
if (min < low[vertex])
{
low[vertex] = min;
return;
}
List<int> component = new List<int>();
int w;
do
{
w = stack.Pop();
component.Add(w);
low[w] = graph.VertexCount;
} while (w != vertex);
stronglyConnectedComponents.Add(component);
}
以下代码显示了测试：
public void CanFindStronglyConnectedComponents()
{
Graph graph = new Graph(8);
graph.AddEdge(0, 1);
graph.AddEdge(1, 2);
graph.AddEdge(2, 3);
graph.AddEdge(3, 2);
graph.AddEdge(3, 7);
graph.AddEdge(7, 3);
graph.AddEdge(2, 6);
graph.AddEdge(7, 6);
graph.AddEdge(5, 6);
graph.AddEdge(6, 5);
graph.AddEdge(1, 5);
graph.AddEdge(4, 5);
graph.AddEdge(4, 0);
graph.AddEdge(1, 4);
var scc = StronglyConnectedComponents.Search(graph);
Assert.AreEqual(3, scc.Count);
Assert.IsTrue(SetsEqual(Set(5, 6), scc[0]));
Assert.IsTrue(SetsEqual(Set(7, 3, 2), scc[1]));
Assert.IsTrue(SetsEqual(Set(4, 1, 0), scc[2]));
}
private IEnumerable<int> Set(params int[] set) => set;
private bool SetsEqual(IEnumerable<int> set1, IEnumerable<int> set2)
{
if (set1.Count() != set2.Count()) return false;
return set1.Intersect(set2).Count() == set1.Count();
}
推荐答案
这是直接的非递归方法原始递归实现的转换（假设正确）：
Here is a direct non recursive translation of the original recursive implementation (assuming it's correct):
public static List<List<int>> Search(Graph graph)
{
var stronglyConnectedComponents = new List<List<int>>();
int preCount = 0;
var low = new int[graph.VertexCount];
var visited = new bool[graph.VertexCount];
var stack = new Stack<int>();
var minStack = new Stack<int>();
var enumeratorStack = new Stack<IEnumerator<int>>();
var enumerator = Enumerable.Range(0, graph.VertexCount).GetEnumerator();
while (true)
{
if (enumerator.MoveNext())
{
int v = enumerator.Current;
if (!visited[v])
{
low[v] = preCount++;
visited[v] = true;
stack.Push(v);
int min = low[v];
// Level down
minStack.Push(min);
enumeratorStack.Push(enumerator);
enumerator = Enumerable.Range(0, graph.OutgoingEdgeCount(v))
.Select(i => graph.OutgoingEdge(v, i).Target)
.GetEnumerator();
}
else if (minStack.Count > 0)
{
int min = minStack.Pop();
if (low[v] < min) min = low[v];
minStack.Push(min);
}
}
else
{
// Level up
if (enumeratorStack.Count == 0) break;
enumerator = enumeratorStack.Pop();
int v = enumerator.Current;
int min = minStack.Pop();
if (min < low[v])
{
low[v] = min;
}
else
{
List<int> component = new List<int>();
int w;
do
{
w = stack.Pop();
component.Add(w);
low[w] = graph.VertexCount;
} while (w != v);
stronglyConnectedComponents.Add(component);
}
if (minStack.Count > 0)
{
min = minStack.Pop();
if (low[v] < min) min = low[v];
minStack.Push(min);
}
}
}
return stronglyConnectedComponents;
}
像通常的直接翻译一样，您需要一个显式堆栈来存储状态从递归调用返回后需要恢复。在这种情况下，它是级别顶点枚举器和 min 变量。
As usual for such direct translations, you need an explicit stack used to store the state that needs to be restored after "returning" from the recursive call. In this case, it's the level vertex enumerator and min variable.
请注意，现有的 stack 变量无法使用，因为在将处理顶点推入此处时，它并不总是弹出退出时（递归实现中的 return 行），这是此算法的特定要求。
Note that the existing stack variable cannot be used because while the processing vertex is pushed there, it's not always popped on exit (the return line in the recursive implementation), which is a specific requirement for this algorithm.
这篇关于Tarjan算法的非递归版本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
