1

隣接行列グラフ表現を使用してCでクラスカルアルゴリズムを実装しました。問題は、セグメンテーション違反エラーがポップアップし続けることです。かなり前から何が問題なのかを突き止めようとしていて、見つけられないようです。問題、他の誰かが見てくださいませんか？ありがとう。

これが私のコードです：

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

の場合j == 0、iは決して< 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と入力し、プログラミング（16進）モードに移行すると、7FFF（またはMAX_SHORT、最大16ビットの符号付き整数値）であることがわかります。それも面白いです。

注：printコマンド（例print node）を使用して変数値を調査し、コマンドを使用してバックトレースを調査できますbt。

これらはwhileループインkruskal（呼び出している唯一の場所find）から来ているので、その値がどこから来ているのかを調査する必要があります。gdbを終了します（「q」を押してEnterキーを押し、次に「y」で確認してEnterキーを押します）。

以下を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 に答える