c++ - 深度优先搜索 : Formatting output?

Question

如果我有下图:

  Marisa  Mariah
       \  / 
Mary---Maria---Marian---Maryanne
         |
Marley--Marla

应该如何实现深度优先搜索功能，以便在“Mary”是我的起点时得到输出？

Mary
   Maria
       Marisa
       Mariah
       Marian
            Maryanne
       Marla
            Merley

我确实意识到空间的数量等于顶点的深度(名称)，但我不知道如何编码。以下是我的功能:

void DFS(Graph g, Vertex origin)
{
    stack<Vertex> vertexStack;
    vertexStack.push(origin);
    Vertex currentVertex;
    int currentDepth = 0;

    while( ! vertexStack.empty() )
    {
        currentVertex = vertexStack.top();
        vertexStack.pop();

        if(currentVertex.visited == false)
        {
            cout << currentVertex.name << endl;

            currentVertex.visited = true;
            for(int i = 0; i < currentVertex.adjacencyList.size(); i++)
                vertexStack.push(currentVertex.adjacencyList[i]);
        }

    }
}

感谢您的帮助!

Answer 1

只需将节点及其深度存储在您的堆栈中:

std::stack<std::pair<Vertex, int>> vertexStack;
vertexStack.push(std::make_pair(origin, 0));
// ...
std::pair<Vertex, int> current = vertexStack.top();
Vertex currentVertex = current.first;
int     depth        = current.second;

如果你想花哨一点，你可以使用 std::tie() 来增加这两个值:

Vertex currentVertex;
int    depth;
std::tie(currentVertex, depth) = vertexStack.top();

了解深度后，您只需适本地缩进输出即可。

顺便说一句，您当前的筹码量太深了!我认为对于一个完整的图，它可能包含 O(N * N) 个元素(更准确地说，是 (N-1) * (N-2))。问题是您推送了许多可能会被访问​​的节点。

假设使用隐式堆栈(即递归)是不可能的(它不适用于大图，因为您可能会出现堆栈溢出)，实现深度优先搜索的正确方法是:

1. 将当前节点和边压入栈中
2. 标记访问过的顶部节点并打印它，使用堆栈深度作为缩进
3. 如果没有节点
4. 如果顶部节点包含未访问的节点(递增边迭代器直到找到这样的节点)转到 1。
5. 否则(边缘迭代器到达终点)移除顶部节点并转到3。

在代码中，这看起来像这样:

std::stack<std::pair<Node, int> > stack;

stack.push(std::make_pair(origin, 0));
while (!stack.empty()) {
    std::pair<Node, int>& top = stack.top();
    for (; top.second < top.first.adjacencyList.size(); ++top.second) {
         Node& adjacent = top.first.adjacencyList[top.second];
         if (!adjacent.visited) {
              adjacent.visted = true;
              stack.push(std::make_pair(adjacent, 0));
              print(adjacent, stack.size());
              break;
         }
     }
     if (stack.top().first.adjacencyList.size() == stack.top().second) {
          stack.pop();
     }
 }