मुझे नहीं पता कि ऐसा क्यों हो रहा है लेकिन मुझे यह समझने में मदद चाहिए कि प्रोग्राम क्रैश क्यों हो रहा है। मेरा कार्यक्रम शहरों (हवाई अड्डों और सड़कों) के बीच सबसे हल्के रास्ते खोजने के लिए क्रुस्कल एल्गोरिदम का उपयोग करने का इरादा रखता है। इसके लिए, यह एक अप्रत्यक्ष ग्राफ बनाता है जो कोने को निर्दिष्ट चापों से जोड़ता है। हालांकि, जब मैं शहरों, हवाई अड्डों और सड़कों की संख्या का परिचय देता हूं, तो कार्यक्रम दुर्घटनाग्रस्त हो जाता है।

पूरा कोड:

#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;
}
c
0
João Moço 25 जिंदा 2021, 21:23
नहीं, यह वास्तव में किस पते की ओर इशारा करता है? आप इसे कोई पता निर्दिष्ट नहीं करते हैं। आपके कंपाइलर को कुछ चेतावनी "अप्रारंभीकृत चर ग्राफ का उपयोग" उठाना चाहिए। यदि नहीं, तो आपको चेतावनी का स्तर बढ़ाना चाहिए। जीसीसी के लिए आप -Wall -Wextra का उपयोग कर सकते हैं
 – 
Gerhardh
25 जिंदा 2021, 21:59

1 उत्तर

सबसे बढ़िया उत्तर
struct Graph* graph;
graph->V = V;

यह एक गैर-आरंभिक सूचक घोषित करता है जो कहीं भी इंगित नहीं करता है, और graph->V अगली पंक्ति पर इसे संदर्भित करता है। आपको पहले malloc ग्राफ बनाना होगा।

struct Graph* graph = malloc(sizeof *graph);
graph->V = V;

मैं (struct Graph*)malloc(sizeof(struct Graph)) के बजाय malloc लिखने की सलाह देता हूं। इसमें शामिल होने के लिए दो अच्छी आदतें:

  1. malloc का परिणाम न डालें। सी ++ में आपको करना है लेकिन सी में आपको नहीं करना चाहिए। यह अनावश्यक है और यदि आप #include <stdlib.h> को भूल जाते हैं तो यह एक चेतावनी को दबा देगा।
  2. sizeof *variable sizeof(Type)< से बेहतर है /a> क्योंकि यह वेरिएबल के प्रकार को दोहराता नहीं है। अगर आप sizeof *variable लिखते हैं और बाद में वेरिएबल नाम बदलते हैं तो आपको कंपाइल-टाइम एरर मिलेगा। यदि आप sizeof(Type) लिखते हैं और बाद में वेरिएबल के प्रकार को बदलते हैं तो आपको कोई त्रुटि नहीं मिलेगी और यह केवल गलत मात्रा में मेमोरी आवंटित करेगा।
0
John Kugelman 25 जिंदा 2021, 22:02
कृपया इसे एक अलग प्रश्न के रूप में पोस्ट करें। धन्यवाद।
 – 
John Kugelman
26 जिंदा 2021, 02:25