带最小邻接点优先的DFS递归实现遇无限循环问题求助

我需要对给定图进行深度优先搜索（DFS）遍历，但当图中节点存在多个邻接节点时，需优先选择值最小的节点进行访问。为此我实现了如下递归DFS函数：

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

    graph->visited[vertex] = 1;
    printf("Visited %d \n", vertex);
  
    int neighbouring_nodes[graph->numVertices];
  
    while (temp != NULL) {
        int count = 0;
        struct node *temp_cpy = temp;
     
        while (temp_cpy != NULL) {
            neighbouring_nodes[count] = temp_cpy->vertex;
            count++;
            temp_cpy = temp_cpy->next;
        }

        int smallest_node = neighbouring_nodes[0];
        
        for (int i = 0; i < count; i++) {
            if (neighbouring_nodes[i] < smallest_node) {
                smallest_node = neighbouring_nodes[i];
            }
        }
    
        if (graph->visited[smallest_node] == 0) {
            DFS(graph, smallest_node);
        } else if (graph->visited[smallest_node] == 1 && count == 1) {
            //if the node is visited but is it the only neighbour
            DFS(graph, smallest_node);
        }
        temp = temp->next;
    }
}

但运行程序时出现无限循环，我猜测原因可能是没有返回条件导致递归持续执行。

请问这种带邻接点优先级的DFS能否用递归实现？若可以，我的代码存在哪些问题？若不行，该如何通过迭代方式实现？

以下是不含DFS函数的完整程序：

// 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;
};

// 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;
}

// Add edge
void addEdge(struct Graph *graph, int src, int dest) {
    // Add edge from src to dest
    struct node *newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 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(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);

    DFS(graph, 2);

    return 0;
}

1. 带邻接点优先级的DFS可以用递归实现 #

完全可以用递归实现，核心逻辑是先找到当前节点所有未访问邻接点中的最小值，再递归访问该节点，避免重复处理已访问节点即可终止递归。

2. 原代码的核心问题 #

• 邻接表遍历逻辑混乱：外层while(temp != NULL)会逐个遍历邻接表节点，但每次循环又重新遍历整个邻接表找最小值，导致同一个最小节点被多次处理。
• 无意义的重复递归：当邻接点已访问且是唯一邻接点时，仍递归调用该节点，直接触发无限循环（比如节点2和1互相反复调用）。
• 未筛选已访问节点：收集邻接点时没有排除已访问的节点，导致处理无效节点，浪费资源且引发错误。

3. 修正后的递归DFS实现 #

void DFS(struct Graph *graph, int vertex) {
    // 标记当前节点为已访问并输出
    graph->visited[vertex] = 1;
    printf("Visited %d\n", vertex);

    struct node *temp = graph->adjLists[vertex];
    int nextVertex = -1;

    // 遍历所有邻接点，筛选出未访问的最小值
    while (temp != NULL) {
        int v = temp->vertex;
        if (!graph->visited[v]) {
            if (nextVertex == -1 || v < nextVertex) {
                nextVertex = v;
            }
        }
        temp = temp->next;
    }

    // 仅当存在未访问的最小邻接点时，才递归访问
    if (nextVertex != -1) {
        DFS(graph, nextVertex);
    }
}

逻辑说明 #

1. 先标记当前节点为已访问并输出。
2. 遍历当前节点的所有邻接点，只关注未访问的节点，记录其中的最小值。
3. 若找到符合条件的邻接点则递归访问，否则递归自然终止，不会出现无限循环。

4. 迭代方式的实现（基于栈） #

如果偏好迭代实现，可以用栈模拟递归的回溯过程，核心是每次将当前节点的未访问邻接点按从大到小的顺序入栈（保证出栈时优先处理最小值）：

void DFSIterative(struct Graph *graph, int startVertex) {
    // 初始化栈，大小为节点总数
    int *stack = malloc(graph->numVertices * sizeof(int));
    int top = -1;

    // 标记起始节点为已访问并入栈
    graph->visited[startVertex] = 1;
    stack[++top] = startVertex;
    printf("Visited %d\n", startVertex);

    while (top != -1) {
        int currentVertex = stack[top];
        struct node *temp = graph->adjLists[currentVertex];
        int found = 0;
        int minUnvisited = -1;

        // 找到当前节点未访问的最小邻接点
        while (temp != NULL) {
            int v = temp->vertex;
            if (!graph->visited[v]) {
                if (minUnvisited == -1 || v < minUnvisited) {
                    minUnvisited = v;
                }
                found = 1;
            }
            temp = temp->next;
        }

        if (found) {
            // 访问最小邻接点，标记并入栈
            graph->visited[minUnvisited] = 1;
            printf("Visited %d\n", minUnvisited);
            stack[++top] = minUnvisited;
        } else {
            // 没有未访问邻接点，弹出当前节点（回溯）
            top--;
        }
    }

    free(stack);
}

逻辑说明 #

1. 用栈保存待处理的节点，每次取出栈顶节点。
2. 找到该节点未访问的最小邻接点，访问后入栈；若没有未访问邻接点，则弹出栈顶节点完成回溯。
3. 完全模拟递归DFS的执行流程，同时保证优先访问最小邻接点。

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