Топологическая сортировка с использованием итерации вместо рекурсии

Question

Топологическая сортировка с использованием итерации вместо рекурсии

У меня изначально было это рекурсивное решение для топологической сортировки:

void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) {
visited[v] = true;
node* curr = adjList[v];

while (curr != NULL) {
if(!visited[curr->val]) {
dfs(curr->val, visited, adjList, myStack);
}
curr = curr->next;
}
myStack.push(v);
}

и это, казалось, работало для моих целей. Но у меня проблемы с переводом в итеративное решение. Это моя попытка:

void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) {
std::stack<int> recursion;
visited[v] = true;

recursion.push(v);

while( !recursion.empty() ) {
v = recursion.top();
recursion.pop();
node* curr = adjList[v];

myStack.push(v);

while (curr != NULL) {
if(!visited[curr->val]) {
visited[curr->val] = true;
recursion.push(curr->val);
}
curr = curr->next;
}
}
}

Но заказ полностью испорчен! Я думаю, что это может быть связано с позиционированием моего myStack.push(v), но я не знаю, как подойти к этому. Любая помощь будет оценена.

2

c++depth-first-search graph recursion topological-sort

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я думаю, что решил свою проблему. По сути, вы можете получить топологический порядок, отсортировав узлы по времени их окончания. Но вместо того, чтобы выполнять сортировку и получать решение O (nlogn), мы можем оставить это как O (n). Когда вы закончите работу с узлом, вместо того, чтобы записывать время его окончания, мы можем вставить уникальный идентификатор узла в стек. Поскольку в моем случае мы имеем дело только с положительными вершинами, было бы достаточно сделать уникальный идентификатор просто отрицательным по значению вершины. Таким образом, если мы последовательно вытолкаем наш стек, мы получим наш топологический порядок.

 void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) {
std::stack<int> recursion;
visited[v] = true;
recursion.push(v);

while( !recursion.empty() ) {
v = recursion.top();
recursion.pop();

//A dummy node to denote finish order (e.g. topological order)
if (v < 0) {
myStack.push(v * -1);
} else {
node* curr = adjList[v];
recursion.push(v * -1);

while (curr != NULL) {
if(!visited[curr->val]) {
visited[curr->val] = true;
recursion.push(curr->val);
}
curr = curr->next;
}
}
}
}

0