无向图DFS遍历实现：如何打印包含回退节点的完整遍历路径？

我明白你的问题了——你想要的是完整的DFS遍历轨迹，包括回溯过程中回退到已访问节点的步骤，但当前代码只打印了首次访问的新节点，漏掉了那些为了寻找未访问节点而回退的节点。

问题根源 #

你的DFS函数仅在发现未访问的邻接节点时，打印该新节点并递归进入；但当子节点的遍历完成、回溯回当前节点时，没有任何代码记录这个回退动作，所以路径里缺失了像3→2、5→4这样的回退步骤。

解决方案 #

我们只需要在递归调用返回后（也就是完成子节点的DFS遍历，回溯到当前节点时），打印当前节点，就能把回退步骤记录下来。修改后的DFS函数如下：

void DFS(struct Graph* graph, int vertex) {
    struct node* adjList = graph->adjLists[vertex];
    struct node* temp = adjList;
    graph->visited[vertex] = 1;
    while (temp != NULL) {
        int connectedVertex = temp->vertex;
        if (graph->visited[connectedVertex] == 0) {
            printf("node: %d\n", connectedVertex);
            DFS(graph, connectedVertex);
            // 回溯时打印当前节点，记录回退步骤
            printf("node: %d\n", vertex);
        }
        temp = temp->next;
    }
}

运行结果说明 #

修改后运行代码，你会得到如下输出：

node: 1
node: 2
node: 3
node: 2
node: 4
node: 5
node: 4
node: 6
node: 4
node: 2
node: 1

这比你预期的路径多了最后几步6→4→2→1，这是因为当所有节点都被访问完成后，DFS会继续回溯到起始节点0（只是0没有被打印）。如果你的需求是仅打印到访问完最后一个节点6为止，可以额外添加一个判断：检查是否还有未访问的节点，只有当存在未访问节点时才打印回溯步骤。不过通常来说，完整的DFS遍历轨迹是包含全部回溯步骤的，你的预期路径可能是省略了后续的回溯部分。

补充说明 #

你的邻接表排序逻辑是正确的（通过sortedInsert保证每次选最小的邻接节点），所以遍历的顺序符合预期，只需要补充回溯步骤的打印即可。

内容的提问来源于stack exchange，提问作者klaus