改造递归DFS函数使其每次返回一个遍历节点？返回值异常求助

我有一个实现图的深度优先搜索（DFS）的递归void函数，原本会打印遍历的节点。现在希望将其改造为每次调用返回新访问的节点，但调用起始节点0时，预期返回遍历顺序中的下一个节点1，实际却返回3。遍历顺序应为：1 2 3 2 4 5 4 6。

尝试的带返回值DFS函数 #

int DFS(struct Graph* graph, int vertex) {
    struct node* adjList = graph->adjLists[vertex];
    struct node* temp = adjList;

    int back = 0;  

    graph->visited[vertex] = 1;

    while (temp != NULL) {
    int connectedVertex = temp->vertex;
    
    if (graph->visited[connectedVertex] == 0) {

        if ( back==1 ) { 
        return vertex;
        printf("node: %d\n", vertex);
        }

        printf("node 1: %d\n", connectedVertex);
        return DFS(graph, connectedVertex);
        back = 1; 
    } 

        temp = temp->next;
    }
  return vertex;
}

原void版本DFS函数 #

void DFS(struct Graph* graph, int vertex) {

    struct node* adjList = graph->adjLists[vertex];
    struct node* temp = adjList;

    int back = 0;  // = "We have already expanded vertex"

    graph->visited[vertex] = 1;

    while (temp != NULL) {
    int connectedVertex = temp->vertex;
    
    if (graph->visited[connectedVertex] == 0) {

        if ( back==1 ) // Report the revisited node 
        printf("node: %d\n", vertex);

        printf("node: %d\n", connectedVertex);
        DFS(graph, connectedVertex);
        back = 1; // Tag this node as having been expanded.
    } 

    temp = temp->next;
    }

}

完整程序代码 #

// DFS algorithm in C

#include <stdio.h>
#include <stdlib.h>

struct node {
  int vertex;
  struct node* next;
};

struct node* createNode(int v);

struct Graph {
  int numVertices;
  int* visited;
  struct node** adjLists;

};


void DFS(struct Graph* graph, int vertex) {

    struct node* adjList = graph->adjLists[vertex];
    struct node* temp = adjList;

    int back = 0;  // = "We have already expanded vertex"

    graph->visited[vertex] = 1;

    while (temp != NULL) {
    int connectedVertex = temp->vertex;
    
    if (graph->visited[connectedVertex] == 0) {

        if ( back==1 ) // Report the revisited node 
        printf("node: %d\n", vertex);

        printf("node: %d\n", connectedVertex);
        DFS(graph, connectedVertex);
        back = 1; // Tag this node as having been expanded.
    } 

    temp = temp->next;
    }

}

// Create a node
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// Create graph
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

  graph->visited = malloc(vertices * sizeof(int));

  int i;
  for (i = 0; i < vertices; i++) {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }
  return graph;
}

void sortedInsert(struct node** head_ref,
                  struct node* new_node)
{
    struct node* current;
    /* Special case for the head end */
    if (*head_ref == NULL
        || (*head_ref)->vertex
               >= new_node->vertex) {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else {
        /* Locate the node before 
the point of insertion */
        current = *head_ref;
        while (current->next != NULL
               && current->next->vertex < new_node->vertex) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
   
  // Add edge from src to dest
   sortedInsert(&graph->adjLists[src], createNode(dest));
  
  // Add edge from dest to src
     sortedInsert(&graph->adjLists[dest], createNode(src));
  
}

// Print the graph
void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v < graph->numVertices; v++) {
    struct node* temp = graph->adjLists[v];
    printf("\n Adjacency list of vertex %d\n ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() {
  struct Graph* graph = createGraph(7);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
          
    addEdge(graph, 1, 2);
              
    addEdge(graph, 2, 3);

    addEdge(graph, 2, 4);
    addEdge(graph, 4, 5);
    addEdge(graph, 4, 6);
    

  printGraph(graph);

  DFS(graph, 0);
  

  return 0;
}

问题分析 #

带返回值的DFS函数存在三个核心问题：

1. 提前终止递归流程：遇到第一个未访问邻接节点时，直接return DFS(...)，导致后续邻接节点的处理逻辑完全被跳过，无法完成完整的DFS回溯。
2. 代码逻辑不可达：back = 1语句在return之后，永远不会被执行，无法标记节点已完成扩展。
3. 回溯返回逻辑错误：return vertex放在printf之前，不仅打印语句无效，还错误地提前返回节点，破坏了遍历顺序。

解决方案：先收集遍历序列，再按需返回节点 #

递归DFS的回溯过程是嵌套执行的，直接让每次递归调用返回下一个节点逻辑复杂。更清晰的方式是先完整收集DFS遍历序列（包括回溯节点），再通过指针逐个返回。

改造步骤： #

1. 修改Graph结构体：添加存储遍历序列的数组、序列长度和当前访问位置变量。

struct Graph {
  int numVertices;
  int* visited;
  struct node** adjLists;
  int* traversalSeq; // 存储完整遍历序列
  int seqIndex;      // 序列已存储的节点数量
  int currentPos;    // 当前要返回的节点索引
};

2. 初始化Graph时创建序列：

struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));
  graph->visited = malloc(vertices * sizeof(int));
  // 初始化遍历序列，预留足够空间（考虑回溯节点）
  graph->traversalSeq = malloc(2 * vertices * sizeof(int));
  graph->seqIndex = 0;
  graph->currentPos = 0;

  int i;
  for (i = 0; i < vertices; i++) {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }
  return graph;
}

3. 改造DFS为序列收集函数：将打印逻辑改为向序列中添加节点。

void DFSCollect(struct Graph* graph, int vertex) {
    struct node* adjList = graph->adjLists[vertex];
    struct node* temp = adjList;

    int back = 0;

    graph->visited[vertex] = 1;

    while (temp != NULL) {
        int connectedVertex = temp->vertex;
        
        if (graph->visited[connectedVertex] == 0) {
            if (back == 1) {
                // 回溯时添加当前节点到序列
                graph->traversalSeq[graph->seqIndex++] = vertex;
            }
            // 添加新访问的节点到序列
            graph->traversalSeq[graph->seqIndex++] = connectedVertex;
            DFSCollect(graph, connectedVertex);
            back = 1;
        }
        temp = temp->next;
    }
}

4. 实现获取下一个节点的函数：

int getNextNode(struct Graph* graph) {
    if (graph->currentPos < graph->seqIndex) {
        return graph->traversalSeq[graph->currentPos++];
    }
    return -1; // 返回-1表示遍历结束
}

5. 修改main函数测试：

int main() {
  struct Graph* graph = createGraph(7);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
          
    addEdge(graph, 1, 2);
              
    addEdge(graph, 2, 3);

    addEdge(graph, 2, 4);
    addEdge(graph, 4, 5);
    addEdge(graph, 4, 6);
    

  printGraph(graph);

  // 先收集遍历序列
  DFSCollect(graph, 0);
  // 逐个获取并打印节点
  printf("遍历序列：");
  int node;
  while ((node = getNextNode(graph)) != -1) {
      printf("%d ", node);
  }
  printf("\n");

  return 0;
}

效果说明 #

运行改造后的代码，会输出预期的遍历序列：1 2 3 2 4 5 4 6，每次调用getNextNode会按顺序返回下一个节点，直到遍历结束返回-1。

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