二维数组递归问题求助：连通顶点最小值查找代码死循环

我来帮你梳理代码里的核心问题，然后给出能正常运行的修正版本：

主要问题分析 #

你的代码出现无限循环和逻辑错误，主要源于这几个关键点：

• 节点编号与数组索引不匹配：你的g数组中，索引i对应节点i+1（比如g[11]是节点12的邻接表），但代码里直接用节点编号作为数组行索引（比如节点12直接访问link[12]），这会错误访问到节点13的邻接表，完全打乱了数据对应关系。
• 访问标记逻辑错误：你在递归之后才标记当前节点为已访问，而且标记的索引是节点编号（超出visitedLabelCheck的合理范围），导致同一个节点被反复访问，触发无限递归。
• 递归逻辑混乱：while(1)的循环控制不当，递归传递的初始最小值错误，返回逻辑也不符合找最小值的需求（比如已访问节点直接返回当前邻接值的逻辑完全错误）。
• 未处理内存泄漏：malloc的visitedLabelCheck没有释放，会导致内存泄漏。
• 函数存在无返回路径：lowest_label函数在某些分支下没有返回值，会导致未定义行为。

修正后的代码 #

#include <stdio.h>
#include <stdlib.h>
#define HEIGHT 21
#define WIDTH 5

// 递归查找连通分量的最小值
int lowest_label(int link[HEIGHT][WIDTH], int currentLabel, int *visitedLabelCheck, int labelCount) {
    // 标记当前节点为已访问（节点编号转索引：currentLabel-1）
    visitedLabelCheck[currentLabel - 1] = 1;
    // 初始化当前最小值为当前节点的编号
    int min_val = currentLabel;
    
    // 遍历当前节点的所有邻接节点（从索引1开始，因为索引0是节点自身编号）
    for (int i = 1; i < WIDTH; i++) {
        int neighbor = link[currentLabel - 1][i];
        if (neighbor == 0) {
            // 邻接列表结束，跳出循环
            break;
        }
        // 如果邻接节点未被访问
        if (!visitedLabelCheck[neighbor - 1]) {
            // 递归查找邻接节点连通分量的最小值
            int neighbor_min = lowest_label(link, neighbor, visitedLabelCheck, labelCount);
            // 更新当前最小值
            if (neighbor_min < min_val) {
                min_val = neighbor_min;
            }
        }
    }
    
    return min_val;
}

int getLowestVertex(int graph[HEIGHT][WIDTH], int currLabel, int labelCount){
    int *visitedLabelCheck = (int *)malloc(labelCount * sizeof(int));
    if (visitedLabelCheck == NULL) {
        printf("内存分配失败！");
        return -1;
    }
    // 初始化所有节点为未访问（0表示未访问，1表示已访问）
    for(int i = 0; i < labelCount; i++){
        visitedLabelCheck[i] = 0;
    }
    
    int low_label = lowest_label(graph, currLabel, visitedLabelCheck, labelCount);
    
    // 释放内存，避免泄漏
    free(visitedLabelCheck);
    return low_label;
}

int main(int argc, char *argv[]) {
    int testThisVertex;
    int lowestVertex;
    int labelCount = 21;
    int g[HEIGHT][WIDTH] = {
        {1, 21, 0, 0, 0},
        {2, 0, 0, 0, 0},
        {3, 0, 0, 0, 0},
        {4, 5, 0, 0, 0},
        {5, 4, 0, 0, 0},
        {6, 21, 0, 0, 0},
        {7, 8,2, 14, 0},
        {8, 7, 9, 0, 0},
        {9, 8,10, 0, 0},
        {10, 9,11, 0, 0},
        {11,10, 0, 0, 0},
        {12,13, 0, 0, 0},
        {13,12,14, 0, 0},
        {14,13,15, 7, 0},
        {15,14, 0, 0, 0},
        {16, 0, 0, 0, 0},
        {17, 0, 0, 0, 0},
        {18, 0, 0, 0, 0},
        {19,20, 0, 0, 0},
        {20,19, 0, 0, 0},
        {21,17,18, 6, 1}
    };
    
    testThisVertex=12;
    lowestVertex = getLowestVertex(g, testThisVertex, labelCount);
    printf("\nThe lowest value that is connected to %d vertex is %d", testThisVertex, lowestVertex);
    getchar();
    return 0;
}

关键修改说明 #

1. 节点与索引的正确映射：所有节点编号转数组索引时都用currentLabel-1，确保访问到正确的邻接表行。
2. 访问标记的正确使用：进入节点时立即标记为已访问，避免重复访问导致无限递归；标记的索引是currentLabel-1，匹配visitedLabelCheck的数组范围。
3. 递归逻辑简化：用for循环遍历邻接节点（从索引1开始，因为索引0是节点自身编号），遇到0就停止遍历；递归时传递当前节点的邻接节点，每次递归返回该分支的最小值，然后更新全局最小值。
4. 内存泄漏修复：在getLowestVertex中释放malloc的内存。
5. 明确的返回值：确保lowest_label函数在所有路径下都有返回值，避免未定义行为。

测试输入12时，代码会正确遍历连通路径12→13→14→7→2，找到最小值2，不会再陷入无限循环。

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