Я пытаюсь реализовать повторяющуюся версию решительно связанных компонентов Тарьяна (SCCs), воспроизведенный здесь для Вашего удобства (источник: 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)
Моя повторяющаяся версия использует следующую структуру Узла.
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 *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();
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;
}
}
}
}
Моя повторяющаяся версия выполняет и дает мне тот же вывод как рекурсивную версию. Проблема состоит в том, что повторяющаяся версия медленнее, и я не уверен почему. Кто-либо может дать мне некоторое понимание на моей реализации? Существует ли лучший способ реализовать рекурсивный алгоритм многократно?
Рекурсивный алгоритм использует стек в качестве области хранения. В итеративной версии вы используете некоторые векторы, которые сами зависят от распределения кучи. Известно, что выделение на основе стека происходит очень быстро, поскольку это всего лишь вопрос перемещения указателя конца стека, тогда как выделение кучи может быть значительно медленнее. То, что итерационная версия работает медленнее, совсем не удивительно.
Вообще говоря, если рассматриваемая проблема хорошо вписывается в рекурсивную модель только для стека, то, во что бы то ни стало, используйте рекурсию.