克鲁斯卡尔 C 实现

Question

我已经使用邻接矩阵图表示在 C 中实现了 Kruskal 算法，问题是，它不断弹出分段错误错误，我已经尝试找出问题所在很长一段时间了，但我似乎找不到问题，请问其他人可以看一下吗？ 谢谢。

这是我的代码：

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

#define MAXVERT 10
#define MAXEDGES 20
#define INF 100000

/*graph representation using an Adjacency matrix*/
typedef struct AdjMatrix
{
    int nodes;
    int adjMat[MAXVERT][MAXVERT];
} graph;

/*function prototypes*/
int find(int node, int *trees);
void merge(int i, int j, int *trees);
void printminimal(int min[][3], int n);

/*main algorithm*/
void kruskal(graph *g)
{
    int EDGES[MAXEDGES][3]; /*graph edges*/
    int MINEDGES[MAXVERT-1][3]; /*edges already in the minimal spanning tree*/
    int nextedge=0;
    int numedges=0;
    int trees[MAXVERT]; /*tree subsets*/
    int i, j, k;
    int temp;

    for(i=0;i<g->nodes;i++)
        trees[i]=i;
    k=0;

    for(i=0; i<g->nodes; i++)
        for(j=0; j<g->nodes; j++)
        {
            if(i<j)
            {
                EDGES[k][0]=i;
                EDGES[k][1]=j;
                EDGES[k][2]=g->adjMat[i][j];
                k++;
            }
            else
                break;
        }

    /*Bubblesort*/
    for(i=0; i<g->nodes; i++)
        for(j=0; j<i; j++)
        {
            if(EDGES[j][2] > EDGES[j+1][2])
            {
                temp=EDGES[j][0];
                EDGES[j][0]=EDGES[j+1][0];
                EDGES[j+1][0]=temp;
                temp=EDGES[j][1];
                EDGES[j][1]=EDGES[j+1][1];
                EDGES[j+1][1]=temp;
                temp=EDGES[j][2];
                EDGES[j][2]=EDGES[j+1][2];
                EDGES[j+1][2]=temp;
            }
        }

    while(numedges < (g->nodes-1))
    {
        i=find(EDGES[nextedge][0], trees);
        j=find(EDGES[nextedge][1], trees);
        if((i!=j)&&(EDGES[nextedge][2]!=-1))    /*check if the nodes belong to the same subtree*/
        {
            merge(i,j,trees);
            MINEDGES[numedges][0]=EDGES[nextedge][0];
            MINEDGES[numedges][1]=EDGES[nextedge][1];
            MINEDGES[numedges][2]=EDGES[nextedge][2];
            numedges++;
        }
        nextedge++;
    }
}

int find(int node, int *trees)   
{
    if(trees[node]!=node)
        return trees[node];
    else
        return node;
}
void merge(int i, int j, int *trees)
{
    if(i<j)
        trees[j]=i;
    else
        trees[i]=j;
}
void printminimal(int min[][3], int n)
{
    int i, weight=0;
    printf("Minimal tree:\n(");
    for(i=0;i<n;i++)
    {
        printf("(V%d,V%d), ", min[i][0],min[i][1]);
        weight+=min[i][2];
    }
    printf(")\n Total weight sum of the minimal tree is: %d", weight);
}
int main(void)
{
    int i,j;
    graph *g=(graph *)malloc(sizeof(graph));
    /*int adjMat[8][8] = {0,INF,INF,11,INF,1,7,
                          INF,0,INF,3,INF,4,8,INF,
                          INF,INF,0,INF,INF,INF,12,INF,
                          INF,3,INF,0,15,INF,INF,INF,
                          11,INF,INF,INF,0,20,INF,INF,
                          INF,4,INF,INF,20,0,INF,INF,
                          1,8,12,INF,INF,INF,0,5,
                          7,INF,INF,INF,INF,INF,5,0};*/
    for(i=0;i<4;i++)
        for(j=0;j<i;j++)
        {
            if(i==j)
            {
                g->adjMat[i][j]=0;
                continue;
            }
            printf("%d-%d= ", i, j);
            scanf("%d", &(g->adjMat[i][j]));
            g->adjMat[j][i]=g->adjMat[i][j];
        }
    g->nodes=4;
    kruskal(g);
}

Answer 1

在 kruskal 函数中，您打算填充 EDGES 数组，但您没有：

for(i=0; i<g->nodes; i++)
    for(j=0; j<g->nodes; j++)
    {
        if(i<j)
        {
            EDGES[k][0]=i;
            EDGES[k][1]=j;
            EDGES[k][2]=g->adjMat[i][j];
            k++;
        }
        else
            break;
    }

对于 j == 0, i 永远不会 < j，这样你就立即跳出了内部循环。我怀疑应该是 i > j 条件中的。

由于 EDGES 未初始化，find 尝试访问 trees 中未指定的元素。

Answer 2

我必须添加以下内容才能将其添加到 kruskal 中，以便从 gcc 进行编译：

int *dvra = trees;

然后您可以使用调试信息编译它：

gcc -g -o kruskal kruskal.c

并通过 gdb 运行它：

gdb kruskal

然后您可以输入 run< /code> 并输入以启动程序。当提示输入值时，我输入了 1,2,3,...。

然后给出：

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400a92 in find (node=32767, trees=0x7fffffffe110) at test.c:86
86      if(trees[node]!=node)

嗯，这很奇怪。树仅包含 10 个项目（MAXVERT 定义的值），因此访问节点 32767 会超出范围。如果你在计算器程序中输入32767并进入编程（十六进制）模式，你会发现它是7FFF（或MAX_SHORT，最大16位有符号整数值）。这也很有趣。

注意：您可以使用print 命令（例如print node）调查变量值，并使用bt 命令调查回溯。

这些来自 kruskal 中的 while 循环（唯一调用 find 的地方），因此我们需要调查该值来自哪里。让我们退出 gdb（按“q”并输入，然后用“y”确认并输入）。

将以下内容添加到 while 循环并运行生成的程序：

printf("%d: nextedge=%d EDGES[nextedge][0]=%d EDGES[nextedge][1]=%d\n", numedges, nextedge, EDGES[nextedge][0], EDGES[nextedge][1]);

给出：

0: nextedge=0 EDGES[nextedge][0]=-557487152 EDGES[nextedge][1]=32767

所以看起来 EDGES[0] 没有被初始化，它指向 if(i 冒泡排序上方初始化循环中的条件。好的，让我们通过在 if 循环中添加以下内容来跟踪初始化循环中发生的情况：

printf("EDGES[%d]: 0=%d 1=%d\n", k, i, j);

重新运行此语句，我们看到没有与该语句关联的行，因此它没有被执行。

将 if 条件更改为：

if(i<=j)

会导致执行该语句并且段错误消失。