kruskal 算法中的分段错误核心转储

Question

#include<stdio.h>

int find( int, int parent[10] );

int uni( int, int, int parent[10] );

int main()
{
    int i, j, k, a, b, u, v, n, ne = 1;
    int min, mincost = 0, cost[9][9], parent[9];
    printf( "\n\tImplementation of Kruskal's algorithm\n" );
    printf( "\nEnter the no. of vertices:" );
    scanf( "%d", &n );
    printf( "\nEnter the cost matrix:\n" );

    for ( i = 1; i <= n; i++ )
    {
        for ( j = 1; j <= n; j++ )
        {
            printf( "Enter the cost of the edge(%d,%d)=", i, j );
            scanf( "%d", &cost[i][j] );

            if ( cost[i][j] == 0 )
            {
                cost[i][j] = 999;
            }
        }
    }

    printf( "The edges of Minimum Cost Spanning Tree are\n" );

    while ( ne < n )
    {
        for ( i = 1, min = 999; i <= n; i++ )
        {
            for ( j = 1; j <= n; j++ )
            {
                if ( cost[i][j] < min )
                {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }

        u = find( u, parent );
        v = find( v, parent );

        if ( uni( u, v, parent ) == 1 )
        {
            printf( "%d edge (%d,%d) =%d\n", ne++, a, b, min );
            mincost += min;
        }

        cost[a][b] = cost[b][a] = 999;
    }

    printf( "\n\tMinimum cost = %d\n", mincost );

}

int uni( int i, int j, int parent[10] )
{
    if ( i != j )
    {
        parent[j] = i;
        return 1;
    }

    return 0;
}

int find( int i, int parent[10] )
{
    while ( parent[i] )
    {
        i = parent[i];
    }

    return i;
}

无法计算 u、v、uni...我可以输入值，但出现消息分段错误（核心已转储）。我猜 find 和 uni 函数有问题（可能是在传递父数组时）..

Answer 1

没有试图破译代码的实际内容（单字母变量，零注释，没有 link 到这个 "Kruskal's algorithm" 或任何东西），除了我已经写的我的评论是添加 printf()s 来记录中间值，检查 scanf() return 代码，将用户输入镜像回用户，并在代码中添加 assert()s...

int parent[9] 已声明，但未初始化。 find() 使用（未初始化的）内容。那里有未定义的行为。

各种 "fishy" 细节，例如 main() 声明 parent[9] 和 cost[9][9]，但函数声明 parent[10]。您还让用户输入顶点数，但很高兴假设当您使用该数作为循环上限时它不会超过 9。如果您对提供的存储量的任何假设都不成立，那么您正在寻找越界访问。

在代码审查的这一点上，我会把代码打印输出扔到桌上，给你那些长而严厉的凝视之一...

kruskal 算法中的分段错误核心转储

segmentation fault core dump in kruskal's algorithm

c

segmentation-fault

coredump