Я пытаюсь реализовать итеративную версию сильно связанных компонентов (SCC) Тарьяна, воспроизведенную здесь для вашего удобства (источник: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm).
Input: Graph G = (V, E)
index = 0 // DFS node number counter
S = empty // An empty stack of nodes
forall v in V do
if (v.index is undefined) // Start a DFS at each node
tarjan(v) // we haven't visited yet
procedure tarjan(v)
v.index = index // Set the depth index for v
v.lowlink = index
index = index + 1
S.push(v) // Push v on the stack
forall (v, v') in E do // Consider successors of v
if (v'.index is undefined) // Was successor v' visited?
tarjan(v') // Recurse
v.lowlink = min(v.lowlink, v'.lowlink)
else if (v' is in S) // Was successor v' in stack S?
v.lowlink = min(v.lowlink, v'.lowlink )
if (v.lowlink == v.index) // Is v the root of an SCC?
print "SCC:"
repeat
v' = S.pop
print v'
until (v' == v)
В моей итерационной версии используется следующая структура Node.
struct Node {
int id; //Signed int up to 2^31 - 1 = 2,147,483,647
int index;
int lowlink;
Node *caller; //If you were looking at the recursive version, this is the node before the recursive call
unsigned int vindex; //Equivalent to the iterator in the for-loop in tarjan
vector<Node *> *nodeVector; //Vector of adjacent Nodes
};
Вот что я сделал для итерационной версии:
void Graph::runTarjan(int out[]) { //You can ignore out. It's a 5-element array that keeps track of the largest 5 SCCs
int index = 0;
tarStack = new stack<Node *>();
onStack = new bool[numNodes];
for (int n = 0; n < numNodes; n++) {
if (nodes[n].index == unvisited) {
tarjan_iter(&nodes[n], index);
}
}
}
void Graph::tarjan_iter(Node *u, int &index) {
u->index = index;
u->lowlink = index;
index++;
u->vindex = 0;
tarStack->push(u);
u->caller = NULL; //Equivalent to the node from which the recursive call would spawn.
onStack[u->id - 1] = true;
Node *last = u;
while(true) {
if(last->vindex < last->nodeVector->size()) { //Equivalent to the check in the for-loop in the recursive version
Node *w = (*(last->nodeVector))[last->vindex];
last->vindex++; //Equivalent to incrementing the iterator in the for-loop in the recursive version
if(w->index == unvisited) {
w->caller = last;
w->vindex = 0;
w->index = index;
w->lowlink = index;
index++;
tarStack->push(w);
onStack[w->id - 1] = true;
last = w;
} else if(onStack[w->id - 1] == true) {
last->lowlink = min(last->lowlink, w->index);
}
} else { //Equivalent to the nodeSet iterator pointing to end()
if(last->lowlink == last->index) {
numScc++;
Node *top = tarStack->top();
tarStack->pop();
onStack[top->id - 1] = false;
int size = 1;
while(top->id != last->id) {
top = tarStack->top();
tarStack->pop();
onStack[top->id - 1] = false;
size++;
}
insertNewSCC(size); //Ranks the size among array of 5 elements
}
Node *newLast = last->caller; //Go up one recursive call
if(newLast != NULL) {
newLast->lowlink = min(newLast->lowlink, last->lowlink);
last = newLast;
} else { //We've seen all the nodes
break;
}
}
}
}
Моя итерационная версия запускается и выдает мне тот же вывод, что и рекурсивная версия. Проблема в том, что итерационная версиямедленнее, и я не уверен, почему. Кто-нибудь может дать мне некоторое представление о моей реализации? Есть ли лучший способ реализовать рекурсивный алгоритм итеративно?