I don't know why this is happening but I need help to understand why the program is crashing. My program intends to use the Kruskal algorithm to find the lightest paths between cities (airports and roads). For this, it creates an undirected graph that links the vertices with the assigned arcs. However, after I introduce the number of cities, airports and roads, the program crashes.
Full code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Uma estrutura para representar um arco pesado no grafo.
struct Edge {
int src, dest, weight;
};
// Uma estrutura para representar um grafo ligado, não dirigido e pesado.
struct Graph {
// V -> Número de vértices (Número de cidades), E -> Número de arcos (Número de estradas + conecções por aeroportos).
int V;
int E;
// O grafo é representado como um array de arcos.
// Visto o grafo ser não dirigido, o arco
// da origem (src) ao destino (dest) é igual
// ao arco de dest a src. Ambos são contados como 1 arco.
struct Edge* edge;
};
// Cria um grafo com V vértices e E arcos.
struct Graph* createGraph(int V, int E)
{
struct Graph* graph;
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
};
// Uma estrutura para representar um subconjunto para as funções "find" e "Union".
struct subset {
int parent;
int rank;
};
// Função que procura pelo nº de vezes que o elemento i aparece.
int find(struct subset subsets[], int i)
{
// Encontra a raíz e torna a raíz o predecessor de i.
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// Função que une os conjuntos x e y.
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Agrega a árvore com rank pequeno sob a raíz da árvore com rank maior (Union by Rank).
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// Se os ranks forem os mesmos, tornar um deles na raíz e incrementar a sua rank por 1.
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Compara 2 arcos de acordo com os pesos.
// Usado na função "qsort" para ordenar o array de arcos.
int myComp(const void* a, const void* b)
{
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
}
// Função principal para construir a MST usando o algoritmo de Kruskal.
void KruskalMST(struct Graph* graph)
{
int V = graph->V;
struct Edge
result[V]; // Guarda a MST resultante.
int e = 0; // Variável de índice, usada para o result[].
int i = 0; // Variável de índice, usada para arcos ordenados.
// 1º pass: Ordenar todos os arcos por ordem crescente dos pesos.
// Se não podemos alterar o grafo dado, copiamos o array de arcos original.
qsort(graph->edge, graph->E, sizeof(graph->edge[0]),
myComp);
// Alocar memória para criar V subconjuntos.
struct subset* subsets
= (struct subset*)malloc(V * sizeof(struct subset));
// Criar V subconjuntos com 1 só elemento.
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Número total de arcos possível = V-1.
while (e < V - 1 && i < graph->E) {
// 2º passo: Escolher o arco mais leve.Pick the smallest edge.
// Incrementar o índice para a próxima iteração.
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// Se a inclusão do arco não causa um ciclo, incluí-lo no result [] e,
// incrementar o índice do result[] para o arco seguinte.
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
// Senão, descartar o arco.
}
printf("Arcos da MST:\n");
printf("V1 V2 Custo\n");
int minimumCost = 0;
int nRoads = 0;
int nAirports = 0;
for (i = 0; i < e; ++i)
{
printf("%d -- %d == %d\n", result[i].src,
result[i].dest, result[i].weight);
if (result[i].src == 0 || result[i].dest == 0) {
nAirports++;
}
else {
nRoads++;
}
minimumCost += result[i].weight;
}
printf("Minimum Spanning Tree com custo minimo: %d\n",minimumCost);
printf("Numero de aeroportos: %d\n",nAirports);
printf("Numero de estradas: %d",nRoads);
return;
}
int main()
{
int V = 0; // Number of cities(vertices) in the graph.
int A = 0; // Number of airports.
int e = 0; // Number of roads.
int E = 0; // Total number of edges in the graph.
int city, airport, city1, city2, cost = 0;
printf("Choose the number of cities: \n");
scanf("%d", &V);
printf("Choose the number of airports: \n");
scanf("%d", &A);
printf("Choose the number of roads: \n");
scanf("%d", &e);
E = A + e;
struct Graph* graph = createGraph(V, E);
for (int i = 0; i < A; i++) {
printf("Input the cost of the airport: \n");
scanf("%d %d", &city, &airport);
graph->edge[i].src = city;
graph->edge[i].dest = 0; // "sky" vertex
graph->edge[i].weight = airport;
}
for (int j = A; j < A + E; j++) {
printf("Pick the path and building cost of the road: \n");
scanf("%d %d %d", &city1, &city2, &cost);
graph->edge[j].src = city1;
graph->edge[j].dest = city2;
graph->edge[j].weight = cost;
}
KruskalMST(graph);
return 0;
}
