Kruskal 的最小生成树程序 (C) 当我尝试在我自己以外的机器上运行时出现分段错误（核心转储）错误

Question

我发现最小生成树的程序有问题，它在我自己的机器上正常工作，没有任何问题，但是当我尝试运行它在另一台计算机上时，我遇到了分段错误（核心转储） error.I 找不到它发生的原因。

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

// struktura wierzcholka

struct Edge

{

    int src;
    int dest;
    int weight;

};

// struktura wazonego grafu nieskierowanego

struct Graph
{

    int V; //liczba wierzcholkow
    int E; //liczba krawedzi

    struct Edge* edge; //tablica wierzcholkow

};

struct Graph* createGraph(int V, int E)

{

    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));

    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

    return graph;

}

struct subset //struktura podzbioru wierzcholka

{

    int p; //parent
    int rank;

};

int FindSet(struct subset array[], int i) //znajdz zbioru elemntu i korzystajac z kompresji sciezek
{

    //  znajdz korzen i uczyn go ojcem i  

    if (array[i].p != i)
    {

        array[i].p = FindSet(array, array[i].p);

    }

    return array[i].p;

}

void Union(struct subset arrayofsubsets[], int x, int y)

{

    int x1 = FindSet(arrayofsubsets, x);
    int y1 = FindSet(arrayofsubsets, y);

    //przylacz drzewo mniejszej randze do pod korzen drzewa o wyzszej randze

    if (arrayofsubsets[x1].rank < arrayofsubsets[y1].rank)
    {

        arrayofsubsets[x1].p = y1;

    }
    else if (arrayofsubsets[x1].rank > arrayofsubsets[y1].rank)
    {

        arrayofsubsets[y1].p = x1;
    }

    //jesli rangi takie same jedno staje się korzeniem i zwieksza //range  

    else
    {

        arrayofsubsets[y1].p = x1;
        arrayofsubsets[x1].rank++;

    }

}

int Compare(const void* a, const void* b)

{
    struct Edge* Edge1 = (struct Edge*) a;
    struct Edge* Edge2 = (struct Edge*) b;
    return Edge1->weight > Edge2->weight;
}

struct Graph* AddEdge(struct Graph* graph, int index, int src, int dest, int weight)
{

    graph->edge[index].src = src;
    graph->edge[index].dest = dest;
    graph->edge[index].weight = weight;

    return graph;
}

void Kruskal(struct Graph* graph)

{

    int V = graph->V;

    struct Edge MST[V];  // minimalne dzewo rozpinajace

    int e, i, v;

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), Compare);

    struct subset *arrayofsubsets = (struct subset*) malloc(V * sizeof(struct subset));

    //  stworz podzbiory jednoelementowe (podzbior wskazuje sam siebie )

    for (v = 0; v < V; ++v)
    {

        arrayofsubsets[v].p = v;
        arrayofsubsets[v].rank = 0;

    }
e=0;
    while (e < (V - 1))
    {

        //wybierz najmniejszy wierzcholek

        struct Edge nextedge = graph->edge[i++];

        int ru = FindSet(arrayofsubsets, nextedge.src);

        int rv = FindSet(arrayofsubsets, nextedge.dest);

        if (ru != rv)
        {

            MST[e++] = nextedge;
            Union(arrayofsubsets, ru, rv);

        }
    }



    printf("MST edges\n");

    for (i = 0; i < e; ++i)
    {

        printf("V1 %d V2 %d weight %d\n", MST[i].src, MST[i].dest, MST[i].weight);
    }

    return;

}

int main()

{

    int V = 6;
    int E = 9;

    struct Graph* graph = createGraph(V, E);

    //boki kwadratu
    graph = AddEdge(graph, 0, 0, 1, 5);
    graph = AddEdge(graph, 1, 0, 2, 3);
    graph = AddEdge(graph, 2, 1, 3, 2);
    graph = AddEdge(graph, 3, 2, 3, 8);

    //przekątne kwadratu
    graph = AddEdge(graph, 4, 0, 3, 4);
    graph = AddEdge(graph, 5, 1, 2, 20);

    //boki kwadratu przyleglego do pierwszego kwadratu  
    //graph=AddEdge(graph,2,1,3,2);
    graph = AddEdge(graph, 6, 1, 4, 1);
    graph = AddEdge(graph, 7, 4, 5, 0);
    graph = AddEdge(graph, 8, 5, 3, 21);

    Kruskal(graph);

    return 0;

}

Answer 1

程序在第 188 行崩溃：

printf("V1 %d V2 %d weight %d\n", MST[i].src, MST[i].dest,MST[i].weight);

并在这一行

int e,i,v,ru,rv;

您没有初始化变量 e 和 i。修复：

int e=0,i=0, [..]

程序将运行

Answer 2

编译器给你两个严重警告

test.c:129:9: warning: ‘i’ is used uninitialized in this function [-Wuninitialized]
  int e, i, v, ru, rv;
         ^
test.c:159:9: warning: ‘e’ may be used uninitialized in this function [-Wmaybe-uninitialized]
    MST[e++] = nextedge;

在函数 Kruskal 中你有

while (e < (V - 1))
{
    //wybierz najmniejszy wierzcholek

    struct Edge nextedge = graph->edge[i++]; <<------

其中 i 未初始化使用。具有本地 scope/automatic 存储持续时间的变量未初始化，因此我可以有任何值。

初始化所有局部变量

int e = 0;
int i = 0;
[...]

或者就在他们第一次使用之前，例如

i = 0;
e = 0;
while (e < (V - 1))
{
    //wybierz najmniejszy wierzcholek

    struct Edge nextedge = graph->edge[i++];

Kruskal 的最小生成树程序 (C) 当我尝试在我自己以外的机器上运行时出现分段错误（核心转储）错误

Kruskal’s Minimum Spanning Tree programm(C) getting segmentation fault (core dumped) error when i try to run it on machine other than my own

c

minimum-spanning-tree

Kruskal 的最小生成树程序 (C) 当我尝试在我自己以外的机器上 运行 时出现分段错误（核心转储）错误

Kruskal’s Minimum Spanning Tree programm(C) getting segmentation fault (core dumped) error when i try to run it on machine other than my own

c

minimum-spanning-tree

Kruskal 的最小生成树程序 (C) 当我尝试在我自己以外的机器上运行时出现分段错误（核心转储）错误