Я написал рекурсивный алгоритм DFS для перемещения графика:
void Graph<E, N>::DFS(Node n)
{
std::cout << ReadNode(n) << " ";
MarkVisited(n);
NodeList adjnodes = Adjacent(n);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
Node adj = adjnodes.ReadList(pos);
if(!IsMarked(adj))
DFS(adj);
pos = adjnodes.NextPosition(pos);
}
}
Затем я написал итеративный алгоритм DFS, используя стек:
template <typename E, typename N>
void Graph<E, N>::IterativeDFS(Node n)
{
Stack<Node> stack;
stack.Push(n);
while(!stack.IsEmpty())
{
Node u = stack.Read();
stack.Pop();
if(!IsMarked(u))
{
std::cout << ReadNode(u) << " ";
MarkVisited(u);
NodeList adjnodes = Adjacent(u);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
stack.Push(adjnodes.ReadList(pos));
pos = adjnodes.NextPosition(pos);
}
}
}
Моя проблема заключается в том, что в графе, в котором, например, я ввожу три узла "a", "b", "c" с дугами ('a', 'b') и ('a', ' c ') мой вывод:
'a', 'b', 'c' с рекурсивной версией DFS и:
'a', 'c', 'b' с итеративным DFS.
Как я могу получить тот же порядок? Я что-то делаю неправильно?
Спасибо!