深度优先搜索：格式化输出？-Java 学习之路

如果我有以下图表：

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

如果“玛丽”是我的起点，我应该如何实现深度优先搜索功能？

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]);
        }

    }
}

谢谢你的帮助！

2 回答

3
只需将节点及其深度存储在堆栈中：
```
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();
```
知道了 depth ，你只需要适当地缩进输出 .

你的堆栈的当前大小是BTW，不必要地深！我认为对于完整的图，它可能包含O（N * N）个元素（更确切地说，（N-1）*（N-2）） . 问题是你推送了许多可能被访问过的节点 .

假设使用隐式堆栈（即递归）是不可能的（它不适用于大型图形，因为您可能会出现堆栈溢出），实现深度优先搜索的正确方法是：
- 推送堆栈上的当前节点和边缘
- 标记访问的顶级节点并使用堆栈深度作为缩进打印它
- 如果没有节点
- 如果顶部节点包含未访问的节点（增加边缘迭代器直到找到这样的节点），请转到1 .
  否则
- （边缘迭代器到达末尾）删除顶部节点并转到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();
     }
 }
```
回复于 2024-05-22T06:45:40+08:00

设 Rep(Tree) 是树的表示 Tree . 然后， Rep(Tree) 看起来像这样：

Root
  <Rep(Subtree rooted at node 1)>
  <Rep(Subtree rooted at node 2)>
               .
               .
               .

因此，让您的 dfs 函数只返回以该节点为根的子树的表示，并相应地修改该值 . 或者，只需告诉每个 dfs 调用以打印以该节点为根的树的表示，但将其传递给当前深度 . 这是后一种方法的示例实现 .

void PrintRep(const Graph& g, Vertex current, int depth)
{
   cout << std::string(' ', 2*depth) << current.name << endl;
   current.visited = true;
   for(int i = 0; i < current.adjacencyList.size(); i++)
      if(current.adjacencyList[i].visited == false)
         PrintRep(g, current.adjacencyList[i], depth+1);           
}

您可以使用您的原点和深度0调用此函数，如下所示：

PrintRep(g, origin, 0);

回复于 2024-05-22T06:45:40+08:00

深度优先搜索：格式化输出？

2 回答

相关问题