Análise de Algoritmo

#include <limits.h> // Para usar INT_MAX (infinito)
#include <stdbool.h> // Para usar o tipo bool (true/false)

// Defina o número de vértices (V) do seu grafo.
#define V 5

/**
* @brief Calcula o custo total da MST de um grafo usando Prim.
* @param graph Matriz de adjacência V x V representando o grafo.
* @return O custo total (soma dos pesos das arestas) da MST.
*/
int calcularCustoPrim(int graph[V][V]) {
    
    // key[i] armazena o menor peso da aresta que conecta
    // o vértice 'i' (que está fora da árvore) a qualquer
    // vértice que já está dentro da árvore.
    int key[V];
    
    // mstSet[i] marca 'true' se o vértice 'i' já foi
    // incluído na árvore (MST).
    bool mstSet[V];

    // 1. Inicialização
    // Define todos os custos como Infinito e ninguém na árvore.
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    // 2. Começa pelo primeiro vértice (pode ser qualquer um)
    // O custo para "chegar" no primeiro vértice é 0.
    key[0] = 0;

    // O loop principal roda V vezes (uma para cada vértice)
    for (int count = 0; count < V; count++) {
        
        // --- 3. Encontra o vértice mais próximo ---
        // (Esta parte substitui a função auxiliar 'minKey')
        
        int min = INT_MAX; // Custo mínimo encontrado nesta rodada
        int u = -1;        // O índice do vértice com o custo mínimo

        // Procura em TODOS os vértices...
        for (int v = 0; v < V; v++) {
            // ...um vértice 'v' que ainda NÃO esteja na árvore
            // e que tenha um custo (key[v]) menor do que o mínimo
            // que encontramos até agora.
            if (mstSet[v] == false && key[v] < min) {
                min = key[v];
                u = v; // 'u' é o nosso candidato para adicionar à árvore
            }
        }
        
        // (Se 'u' for -1, o grafo é desconexo, mas vamos ignorar por simplicidade)
        
        // 4. Adiciona o vértice encontrado 'u' à árvore
        mstSet[u] = true;

        // 5. Atualiza os custos dos vizinhos de 'u'
        // Agora que 'u' está na árvore, vemos se ele oferece um
        // caminho mais barato para algum de seus vizinhos.
        for (int v = 0; v < V; v++) {
            
            // Condições:
            // 1. graph[u][v] != 0 : Existe uma aresta entre 'u' e 'v'.
            // 2. mstSet[v] == false : O vizinho 'v' ainda NÃO está na árvore.
            // 3. graph[u][v] < key[v] : A aresta (u,v) é mais barata
            //                       do que o custo atual para chegar em 'v'.
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                
                // Se sim, atualiza o custo de 'v'
                key[v] = graph[u][v];
            }
        }
    }

    // 6. Calcula o custo total
    // O custo total do MST é a soma de todos os valores no array 'key',
    // pois cada key[i] representa o peso da aresta que o conectou à árvore.
    int custoTotal = 0;
    for (int i = 0; i < V; i++) {
        if (key[i] != INT_MAX) { // Evita somar infinito
          custoTotal += key[i];
        }
    }

    return custoTotal;
}