1

我已经使用邻接矩阵图表示在 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);
}
4

2 回答 2

2

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

For j == 0, iis never < j，所以你立即跳出内循环。我怀疑它应该i > j处于这种状态。

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

于 2011-12-27T18:17:37.220 回答
0

我必须添加以下内容才能kruskal让它从 gcc 编译：

int *dvra = trees;

然后，您可以使用调试信息对其进行编译：

gcc -g -o kruskal kruskal.c

并通过 gdb 运行它：

gdb kruskal

然后，您可以键入run并输入以启动程序。当提示输入值时，我输入了 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。

这些来自 while 循环kruskal（唯一调用 的地方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<j)了冒泡排序上面的初始化循环中的条件。好的，让我们通过在 if 循环中添加以下内容来跟踪初始化循环中发生了什么：

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

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

将 if 条件更改为：

if(i<=j)

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

于 2011-12-27T18:55:06.110 回答