I have an issue with program to find minimum-spanning-tree it works properly without any issues on my own machine but when I tried to run it on another computers i got segmentation fault (core dumped) error.I cant no find reason why it happens.
#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;
}
The program crash at line 188:
printf("V1 %d V2 %d weight %d\n", MST[i].src, MST[i].dest,MST[i].weight);
and at this line
int e,i,v,ru,rv;
you didn't inizialize vars e and i. To fix:
int e=0,i=0, [..]
and the program will work