My program keeps going down

Question

I don’t know why this is happening, but I need help figuring out why the program is crashing. My program aims to use Kruskal’s algorithm to find the lightest paths between cities (airports and roads). For this, it creates an undirected graph that connects the vertices with the assigned arcs.

Complete 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; // Número de vértices(cidades) no grafo.
    int A = 0; // Número de aeroportos.
    int e = 0; // Número de estradas no grafo.
    int E = 0; //Númeto total de arcos no grafo.
    int cidade, aeroporto, cidade1, cidade2, custo = 0;

    printf("Introduza o numero de cidades: \n");
    scanf("%d", &V);
    printf("Introduza o numero de aeroportos: \n");
    scanf("%d", &A);
    printf("Introduza o numero de estradas: \n");
    scanf("%d", &e);

    E = A + e;

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

    for (int i = 0; i < A; i++) {
        printf("Introduza o custo do aeroporto: \n");
        scanf("%d %d", &cidade, &aeroporto);

        graph->edge[i].src = cidade;
        graph->edge[i].dest = 0; // vértice "céu"
        graph->edge[i].weight = aeroporto;
    }

    for (int j = A; j < A + E; j++) {
        printf("Introduza o custo da estrada: \n");
        scanf("%d %d %d", &cidade1, &cidade2, &custo);

        graph->edge[j].src = cidade1;
        graph->edge[j].dest = cidade2;
        graph->edge[j].weight = custo;
    }

    KruskalMST(graph);

    return 0;
}

Answer 1

John see this passage here

struct Graph* createGraph(int V, int E)
{
    struct Graph* graph;[[(struct Edge*)malloc(E*sizeof(struct Edge))]aqui também]
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
};

struct Graph * is also a pointer, if you don’t allot with malloc here at the beginning too, the porgram doesn’t know where to aramazenar grapho->V and ->E... and any other value below.

If you use linux, Compile with the gcc flag -g ... and after gdb . /file.out to debug. b numeor_da_line (break point) Disp variable_name - to see the variable n (to follow for next instruction) run (to start) quit (to quit) help (manual)

Are the most commonly used instructions.

If you are on another system and need to test fast have this site below:
https://www.onlinegdb.com/
there Click on the line, set the break points runs with debug mode, run and go testing line by line. On the right side are the variables, for shorter codes it is very convenient to test there and a hand on the wheel.