Топологическая сортировка с использованием DFS без рекурсии
Я знаю, что обычный метод топологической сортировки — это использование DFS с рекурсией. Но как бы вы сделали это, используя stack<int> вместо рекурсии? Мне нужно получить обратный пост-заказ, но я застрял:
График является vector<vector<int> > список смежности
Ниже приводится DFS, которую я хочу использовать для топологической сортировки.
bool visited[MAX]={0};
stack<int> dfs, postOrder;
vector<int> newVec;
vector<int>::iterator it;
for(int i=0;i<MAX;i++){
if(visited[i]==false){
dfs.push(i);
}
while(!dfs.empty()){
int node=dfs.top();
dfs.pop();
visited[node]=true;
newVec=graph[node]; //vector of neighboors
for(it=newVec.begin();it!=newVec.end();it++){
int son=*it;
if(visited[son]==false){
dfs.push(son);
}
}
}
}
Решение
Для того, чтобы построить postOrder список, вам нужно знать время, когда ваш алгоритм завершил обработку последнего дочернего узла k,
Один из способов выяснить, когда вы вытолкнули последнего дочернего элемента из стека, — это поместить специальные отметки в стек, чтобы указать места, где начинаются дочерние элементы определенного узла. Вы можете изменить тип вашего dfs укладывать в vector<pair<bool,int> >, Когда bool установлен в true, это указывает на родителя; false указывает на ребенка.
Когда вы выдвигаете «дочернюю пару» (то есть одну с первым членом пары, установленным в false) из стека вы запускаете код, который у вас есть на данный момент, т.е. for петля. Прежде чем войти в for цикл, однако, вы должны нажать make_pair(true, node) в стек, чтобы отметить начало всех потомков этого node,
Когда вы вытаскиваете «родительскую пару» из стека, вы помещаете родительский индекс в postOrderи двигаться дальше:
vector<bool> visited(MAX);
stack<pair<bool,int> > dfs;
stack<int> postOrder;
vector<int> newVec;
vector<int>::iterator it;
vector<vector<int> > graph;
for(int i=0;i<MAX;i++){
if(visited[i]==false){
dfs.push(make_pair(false,i));
}
while(!dfs.empty()){
pair<bool,int> node=dfs.top();
dfs.pop();
if (node.first) {
postOrder.push(node.second);
continue;
}
visited[node.second]=true;
dfs.push(make_pair(true, node.second));
newVec=graph[node.second]; //vector of neighboors
for(it=newVec.begin();it!=newVec.end();it++){
int son=*it;
if(visited[son]==false){
dfs.push(make_pair(false, son));
}
}
}
}
Другие решения
Я думаю, что ваш код — хорошая нерекурсивная DFS. Ключевым моментом топологической сортировки является то, что:
Когда вы выбираете узел для вставки в стек. Этот узел не должен иметь прецессора (имеет степень 0). Это означает, что вы делаете основание DFS в градусах вместо того, чтобы помещать все соседние узлы в стек, вы всегда выбираете тот, у которого 0 градусов
Таким образом, вы толкаете каждый узел, у которого нет прецессора в стеке. Вставьте один, распечатайте его и удалите из списка прецессоров всех соседних узлов (или уменьшите степень смежных узлов на 1). Вам нужно отредактировать соседний список. Чем подтолкнуть все смежные узлы, которые имеют степень 0 сейчас в стек (эта фаза может завершиться неудачно, но без проблем, у вас все еще есть несколько узлов в стеке). Тогда поп следующий. Повторяйте, пока стек не станет пустым. Печатная последовательность узлов является результатом топологической сортировки графа.
Ниже мой итерационный код для топологической сортировки DAG.
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
using namespace std;
unordered_map<int, unordered_set<int>> g; // this is the simplest graph representation I was able to implement. Map the vertices to their set of children
void addEdge(int x, int y) { // Add edges to the graph
g[x].insert(y);
}
void topSort() {
unordered_set<int> visited; // Keep track of visited nodes
stack<int> mainStack; // The stack that will have the resulting vertices in topologically sorted order
for(auto it = g.begin(); it != g.end(); it++) {
if(visited.count(it->first) == 0) { // If the vertex was not already visited do the following
visited.insert(it->first); // visit the vertex
stack<int> locStack;
locStack.push(it->first); // push it to local stack
while(!locStack.empty()) { // This part is similar to basic DFS algorithm
int curr = locStack.top();
bool unVisCh = false; // Keep a boolean to check whether there is any unvisited child
for(auto it2 = g[curr].begin(); it2 != g[curr].end(); it2++) {
int child = *it2;
if(visited.count(child) == 0) {
unVisCh = true;
visited.insert(child);
locStack.push(child);
}
}
if(!unVisCh) { // if there is no unvisited child then we can push the vertex to the resulting stack
locStack.pop();
mainStack.push(curr);
}
}
}
}
while(!mainStack.empty()) {
cout<<mainStack.top()<<" ";
mainStack.pop(); // print them in order
}
cout<<endl;
}
int main() {
addEdge(1,2);
addEdge(4,5);
addEdge(5,6);
addEdge(3,2);
addEdge(2,6);
addEdge(1,3);
addEdge(4,3); // add adges to the graph
topSort();
return 0;
}
Для тестирования: ideone
Надеюсь, это поможет!
Узел посещен 1-ым и все еще находится в процессе, он добавлен в стек как ложный. Эти узлы затем обрабатываются из стека как LIFO и изменяются на true (обработано означает, что посещенные дети). После того, как все дочерние элементы обработаны, при трассировке пути назад этот узел отброшен из стека.
Для тех, кто пытается реализовать этот код, visited[node.second]=true; должен быть перемещен в 2 места, где 1-й узел добавлен в стек как ложный. Это так, что задние ребра, ведущие к уже прослеженным вершинам, не пересматриваются.
Это снова мы. 🙂 Я отправляю ответ, потому что мне не хватает очков, чтобы комментировать. 🙁
Хорошо, позвольте мне сказать, что мне очень нравится этот алгоритм. Если график определен правильно, то ошибки нет. Но возьмите этот график:
vector<vector<int>> graph
{
{ 2, 1 }
,{ 2 }
,{ }
};
Это будет отображать:
2
1
2
0
Чтобы защитить себя от графиков, определенных таким образом, или от случайных ребер, вы можете сделать это:
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
stack<pair<bool, int>> dfs;
stack<int> postorder;
vector<int> newvector;
vector<int>::iterator it;
vector<vector<int>> graph
{
{ 2, 1 }
,{ 2 }
,{ }
};
vector<bool> visited(graph.size());
vector<bool> finallyvisited(graph.size());
for (int i = 0;i < graph.size();i++)
{
if (!visited[i])
{
dfs.push(make_pair(false, i));
}
while (!dfs.empty())
{
pair<bool, int> node = dfs.top();
dfs.pop();
if (node.first)
{
if (!finallyvisited[node.second])
{
finallyvisited[node.second] = true;
postorder.push(node.second);
cout << node.second << endl;
}
continue;
}
visited[node.second] = true;
dfs.push(make_pair(true, node.second));
newvector = graph[node.second];
for (it = newvector.begin();it != newvector.end();it++)
{
int son = *it;
if (!visited[son])
{
dfs.push(make_pair(false, son));
}
}
}
}
return 0;
}
Или вы можете предварительно заказать график, может быть, кто-то может показать это решение. Как предварительно упорядочить случайно заданные ребра, чтобы не было необходимости во второй проверке. 🙂
И я сделал, хотя по поводу комментария Атифа Хуссейна, и он ошибочен. Это никогда не сработает. Вы всегда хотите сдвинуть в стек узел как можно позже, чтобы он выскочил как можно раньше.