Le programme Minimum Spanning Tree (C) de Kruskal obtient une erreur de segmentation (core dumped) lorsque j'essaie de l'exécuter sur une machine autre que la mienne

Question

J'ai un problème avec le programme pour trouver le minimum-spanning-tree il fonctionne correctement sans aucun problème sur ma propre machine, mais quand j'ai essayé de l'exécuter sur un autre ordinateur, j'ai eu erreur de segmentation (core dumped) erreur.Je ne peux pas trouver de raison pourquoi cela arrive.

#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

Le plantage du programme à la ligne 188:

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

et à cette ligne

int e,i,v,ru,rv; 

vous n'avez pas vars inizialize e et i. Pour corriger:

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

et le programme fonctionnera

Answer 2

compilateur vous donne deux avertissements sévères

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; 

En fonction Kruskal vous avez

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

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

où i est utilisé un -initialisé variable avec portée locale/durée de stockage automatique n'est pas initialisée, donc je peux avoir n'importe quelle valeur.

Init tous Variable locale

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

ou juste avant la première utilisation, comme

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

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