Árvores de Abrangência Mínima

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
 
#define MAX_VERTICES 100
#define MAX_ARESTAS 1000
#define INFINITO INT_MAX
 
// Estrutura para representar uma aresta
typedef struct Aresta {
    int destino;
    int peso;
    struct Aresta* proxima;
} Aresta;
 
// Estrutura para representar um vértice
typedef struct Vertice {
    int valor;
    Aresta* adjacentes;
} Vertice;
 
// Estrutura do grafo ponderado
typedef struct GrafoPonderado {
    Vertice vertices[MAX_VERTICES];
    int numVertices;
    bool direcionado;
} GrafoPonderado;
 
// Estrutura para aresta na lista de arestas (Kruskal)
typedef struct ArestaLista {
    int origem;
    int destino;
    int peso;
} ArestaLista;
 
// Estrutura para Union-Find (Kruskal)
typedef struct UnionFind {
    int pai[MAX_VERTICES];
    int rank[MAX_VERTICES];
} UnionFind;
 
// Estrutura para heap mínimo (Prim)
typedef struct {
    int vertice;
    int peso;
} ItemHeap;
 
typedef struct {
    ItemHeap itens[MAX_VERTICES];
    int tamanho;
    int posicao[MAX_VERTICES]; // Mapear vértice para posição no heap
} HeapMinimo;
 
// Funções auxiliares do grafo
GrafoPonderado* criarGrafo(int numVertices, bool direcionado) {
    GrafoPonderado* grafo = (GrafoPonderado*)malloc(sizeof(GrafoPonderado));
    grafo->numVertices = numVertices;
    grafo->direcionado = direcionado;
    
    for (int i = 0; i < numVertices; i++) {
        grafo->vertices[i].valor = i;
        grafo->vertices[i].adjacentes = NULL;
    }
    
    return grafo;
}
 
void adicionarAresta(GrafoPonderado* grafo, int origem, int destino, int peso) {
    Aresta* novaAresta = (Aresta*)malloc(sizeof(Aresta));
    novaAresta->destino = destino;
    novaAresta->peso = peso;
    novaAresta->proxima = grafo->vertices[origem].adjacentes;
    grafo->vertices[origem].adjacentes = novaAresta;
    
    if (!grafo->direcionado) {
        Aresta* arestaReversa = (Aresta*)malloc(sizeof(Aresta));
        arestaReversa->destino = origem;
        arestaReversa->peso = peso;
        arestaReversa->proxima = grafo->vertices[destino].adjacentes;
        grafo->vertices[destino].adjacentes = arestaReversa;
    }
}
 
// ==================== FUNÇÕES DO HEAP MÍNIMO ====================
 
void trocarItens(HeapMinimo* heap, int i, int j) {
    ItemHeap temp = heap->itens[i];
    heap->itens[i] = heap->itens[j];
    heap->itens[j] = temp;
    
    // Atualizar posições
    heap->posicao[heap->itens[i].vertice] = i;
    heap->posicao[heap->itens[j].vertice] = j;
}
 
void heapifyUp(HeapMinimo* heap, int indice) {
    while (indice > 0) {
        int pai = (indice - 1) / 2;
        if (heap->itens[indice].peso >= heap->itens[pai].peso) break;
        
        trocarItens(heap, indice, pai);
        indice = pai;
    }
}
 
void heapifyDown(HeapMinimo* heap, int indice) {
    int menor = indice;
    int esquerda = 2 * indice + 1;
    int direita = 2 * indice + 2;
    
    if (esquerda < heap->tamanho && 
        heap->itens[esquerda].peso < heap->itens[menor].peso) {
        menor = esquerda;
    }
    
    if (direita < heap->tamanho && 
        heap->itens[direita].peso < heap->itens[menor].peso) {
        menor = direita;
    }
    
    if (menor != indice) {
        trocarItens(heap, indice, menor);
        heapifyDown(heap, menor);
    }
}
 
void inserirHeap(HeapMinimo* heap, int vertice, int peso) {
    heap->itens[heap->tamanho].vertice = vertice;
    heap->itens[heap->tamanho].peso = peso;
    heap->posicao[vertice] = heap->tamanho;
    
    heapifyUp(heap, heap->tamanho);
    heap->tamanho++;
}
 
ItemHeap extrairMinimo(HeapMinimo* heap) {
    ItemHeap minimo = heap->itens[0];
    heap->tamanho--;
    
    if (heap->tamanho > 0) {
        heap->itens[0] = heap->itens[heap->tamanho];
        heap->posicao[heap->itens[0].vertice] = 0;
        heapifyDown(heap, 0);
    }
    
    heap->posicao[minimo.vertice] = -1; // Marcar como removido
    return minimo;
}
 
void diminuirChave(HeapMinimo* heap, int vertice, int novoPeso) {
    int pos = heap->posicao[vertice];
    if (pos == -1 || novoPeso >= heap->itens[pos].peso) return;
    
    heap->itens[pos].peso = novoPeso;
    heapifyUp(heap, pos);
}
 
bool heapVazio(HeapMinimo* heap) {
    return heap->tamanho == 0;
}
 
// ==================== ALGORITMO DE PRIM ====================
 
void algoritmoEPrim(GrafoPonderado* grafo, int origem) {
    HeapMinimo heap;
    heap.tamanho = 0;
    
    int chave[MAX_VERTICES]; // Peso mínimo para conectar cada vértice à MST
    int pai[MAX_VERTICES];   // Pai de cada vértice na MST
    bool naMST[MAX_VERTICES]; // Vértices já incluídos na MST
    
    // Inicializar arrays
    for (int i = 0; i < grafo->numVertices; i++) {
        chave[i] = INFINITO;
        pai[i] = -1;
        naMST[i] = false;
        heap.posicao[i] = -1;
    }
    
    // Iniciar com o vértice de origem
    chave[origem] = 0;
    inserirHeap(&heap, origem, 0);
    
    printf("=== Executando Algoritmo de Prim ===\n");
    printf("Vértice inicial: %d\n\n", origem);
    
    ArestaLista mst[MAX_VERTICES - 1]; // Armazenar arestas da MST
    int numArestasMST = 0;
    int pesoTotal = 0;
    
    while (!heapVazio(&heap)) {
        ItemHeap atual = extrairMinimo(&heap);
        int u = atual.vertice;
        
        naMST[u] = true;
        pesoTotal += chave[u];
        
        if (pai[u] != -1) {
            mst[numArestasMST].origem = pai[u];
            mst[numArestasMST].destino = u;
            mst[numArestasMST].peso = chave[u];
            numArestasMST++;
            
            printf("Adicionando aresta (%d, %d) com peso %d à MST\n", 
                   pai[u], u, chave[u]);
        }
        
        // Atualizar chaves dos vértices adjacentes
        Aresta* aresta = grafo->vertices[u].adjacentes;
        while (aresta != NULL) {
            int v = aresta->destino;
            int peso = aresta->peso;
            
            if (!naMST[v] && peso < chave[v]) {
                printf("  Atualizando chave do vértice %d: %d -> %d\n", 
                       v, chave[v], peso);
                
                pai[v] = u;
                chave[v] = peso;
                
                if (heap.posicao[v] == -1) {
                    inserirHeap(&heap, v, peso);
                } else {
                    diminuirChave(&heap, v, peso);
                }
            }
            
            aresta = aresta->proxima;
        }
        printf("\n");
    }
    
    printf("=== Resultado do Algoritmo de Prim ===\n");
    printf("Arestas da MST:\n");
    for (int i = 0; i < numArestasMST; i++) {
        printf("(%d, %d) - peso: %d\n", 
               mst[i].origem, mst[i].destino, mst[i].peso);
    }
    printf("Peso total da MST: %d\n\n", pesoTotal);
}
 
// ==================== UNION-FIND (para Kruskal) ====================
 
void inicializarUnionFind(UnionFind* uf, int n) {
    for (int i = 0; i < n; i++) {
        uf->pai[i] = i;
        uf->rank[i] = 0;
    }
}
 
int encontrar(UnionFind* uf, int x) {
    if (uf->pai[x] != x) {
        uf->pai[x] = encontrar(uf, uf->pai[x]); // Compressão de caminho
    }
    return uf->pai[x];
}
 
bool unir(UnionFind* uf, int x, int y) {
    int raizX = encontrar(uf, x);
    int raizY = encontrar(uf, y);
    
    if (raizX == raizY) {
        return false; // Já estão no mesmo conjunto (criaria ciclo)
    }
    
    // Union by rank
    if (uf->rank[raizX] < uf->rank[raizY]) {
        uf->pai[raizX] = raizY;
    } else if (uf->rank[raizX] > uf->rank[raizY]) {
        uf->pai[raizY] = raizX;
    } else {
        uf->pai[raizY] = raizX;
        uf->rank[raizX]++;
    }
    
    return true;
}
 
// ==================== ALGORITMO DE KRUSKAL ====================
 
int compararArestas(const void* a, const void* b) {
    ArestaLista* arestaA = (ArestaLista*)a;
    ArestaLista* arestaB = (ArestaLista*)b;
    return arestaA->peso - arestaB->peso;
}
 
void obterTodasArestas(GrafoPonderado* grafo, ArestaLista arestas[], int* numArestas) {
    *numArestas = 0;
    
    for (int u = 0; u < grafo->numVertices; u++) {
        Aresta* aresta = grafo->vertices[u].adjacentes;
        while (aresta != NULL) {
            int v = aresta->destino;
            
            // Para grafo não-direcionado, adicionar apenas uma vez (u < v)
            if (grafo->direcionado || u < v) {
                arestas[*numArestas].origem = u;
                arestas[*numArestas].destino = v;
                arestas[*numArestas].peso = aresta->peso;
                (*numArestas)++;
            }
            
            aresta = aresta->proxima;
        }
    }
}
 
void algoritmoKruskal(GrafoPonderado* grafo) {
    ArestaLista arestas[MAX_ARESTAS];
    int numArestas;
    
    // Obter todas as arestas do grafo
    obterTodasArestas(grafo, arestas, &numArestas);
    
    // Ordenar arestas por peso
    qsort(arestas, numArestas, sizeof(ArestaLista), compararArestas);
    
    printf("=== Executando Algoritmo de Kruskal ===\n");
    printf("Arestas ordenadas por peso:\n");
    for (int i = 0; i < numArestas; i++) {
        printf("(%d, %d) - peso: %d\n", 
               arestas[i].origem, arestas[i].destino, arestas[i].peso);
    }
    printf("\n");
    
    // Inicializar Union-Find
    UnionFind uf;
    inicializarUnionFind(&uf, grafo->numVertices);
    
    ArestaLista mst[MAX_VERTICES - 1];
    int numArestasMST = 0;
    int pesoTotal = 0;
    
    printf("Processando arestas:\n");
    
    for (int i = 0; i < numArestas && numArestasMST < grafo->numVertices - 1; i++) {
        int u = arestas[i].origem;
        int v = arestas[i].destino;
        int peso = arestas[i].peso;
        
        printf("Considerando aresta (%d, %d) - peso: %d\n", u, v, peso);
        
        // Verificar se adicionar esta aresta criaria um ciclo
        if (encontrar(&uf, u) != encontrar(&uf, v)) {
            // Não cria ciclo, adicionar à MST
            mst[numArestasMST] = arestas[i];
            numArestasMST++;
            pesoTotal += peso;
            
            unir(&uf, u, v);
            printf("  Aresta ACEITA - Adicionada à MST\n");
        } else {
            printf("  Aresta REJEITADA - Criaria ciclo\n");
        }
        printf("\n");
    }
    
    printf("=== Resultado do Algoritmo de Kruskal ===\n");
    printf("Arestas da MST:\n");
    for (int i = 0; i < numArestasMST; i++) {
        printf("(%d, %d) - peso: %d\n", 
               mst[i].origem, mst[i].destino, mst[i].peso);
    }
    printf("Peso total da MST: %d\n\n", pesoTotal);
}
 
// ==================== COMPARAÇÃO DOS ALGORITMOS ====================
 
void compararAlgoritmosMST(GrafoPonderado* grafo) {
    printf("=== COMPARAÇÃO: PRIM vs KRUSKAL ===\n\n");
    
    printf("ALGORITMO DE PRIM:\n");
    printf("==================\n");
    algoritmoEPrim(grafo, 0);
    
    printf("ALGORITMO DE KRUSKAL:\n");
    printf("=====================\n");
    algoritmoKruskal(grafo);
    
    printf("ANÁLISE COMPARATIVA:\n");
    printf("===================\n");
    printf("Ambos os algoritmos encontram uma MST válida.\n");
    printf("O peso total deve ser o mesmo em ambos os casos.\n");
    printf("As arestas podem ser diferentes se existirem múltiplas MSTs.\n\n");
}
 
// ==================== VERIFICAÇÃO DE MST ====================
 
bool verificarMST(GrafoPonderado* grafo, ArestaLista mst[], int numArestas, int pesoEsperado) {
    printf("=== Verificando se é uma MST válida ===\n");
    
    // Verificar se tem exatamente V-1 arestas
    if (numArestas != grafo->numVertices - 1) {
        printf("ERRO: MST deve ter exatamente %d arestas, mas tem %d\n", 
               grafo->numVertices - 1, numArestas);
        return false;
    }
    
    // Verificar se é conectada usando Union-Find
    UnionFind uf;
    inicializarUnionFind(&uf, grafo->numVertices);
    
    int pesoTotal = 0;
    for (int i = 0; i < numArestas; i++) {
        unir(&uf, mst[i].origem, mst[i].destino);
        pesoTotal += mst[i].peso;
    }
    
    // Verificar se todos os vértices estão conectados
    int raizPrincipal = encontrar(&uf, 0);
    for (int i = 1; i < grafo->numVertices; i++) {
        if (encontrar(&uf, i) != raizPrincipal) {
            printf("ERRO: Grafo não está conectado na MST\n");
            return false;
        }
    }
    
    printf("✓ Número correto de arestas: %d\n", numArestas);
    printf("✓ Grafo está conectado\n");
    printf("✓ Peso total: %d\n", pesoTotal);
    
    if (pesoTotal == pesoEsperado) {
        printf("✓ Peso corresponde ao esperado\n");
    } else {
        printf("⚠ Peso difere do esperado (%d)\n", pesoEsperado);
    }
    
    printf("MST é VÁLIDA!\n\n");
    return true;
}
 
// ==================== APLICAÇÕES ESPECIAIS ====================
 
void encontrarMSTComRestricoes(GrafoPonderado* grafo, int pesoMaximo) {
    printf("=== MST com Restrição de Peso Máximo ===\n");
    printf("Peso máximo permitido por aresta: %d\n\n", pesoMaximo);
    
    ArestaLista arestas[MAX_ARESTAS];
    int numArestas;
    
    obterTodasArestas(grafo, arestas, &numArestas);
    qsort(arestas, numArestas, sizeof(ArestaLista), compararArestas);
    
    UnionFind uf;
    inicializarUnionFind(&uf, grafo->numVertices);
    
    ArestaLista mst[MAX_VERTICES - 1];
    int numArestasMST = 0;
    int pesoTotal = 0;
    
    for (int i = 0; i < numArestas && numArestasMST < grafo->numVertices - 1; i++) {
        if (arestas[i].peso <= pesoMaximo) {
            int u = arestas[i].origem;
            int v = arestas[i].destino;
            
            if (encontrar(&uf, u) != encontrar(&uf, v)) {
                mst[numArestasMST] = arestas[i];
                numArestasMST++;
                pesoTotal += arestas[i].peso;
                unir(&uf, u, v);
                
                printf("Adicionada: (%d, %d) - peso: %d\n", 
                       u, v, arestas[i].peso);
            }
        }
    }
    
    if (numArestasMST == grafo->numVertices - 1) {
        printf("\nMST com restrições encontrada!\n");
        printf("Peso total: %d\n\n", pesoTotal);
    } else {
        printf("\nNão é possível formar MST com a restrição dada.\n");
        printf("Arestas encontradas: %d (necessárias: %d)\n\n", 
               numArestasMST, grafo->numVertices - 1);
    }
}
 
void analisarCentralidade(GrafoPonderado* grafo) {
    printf("=== Análise de Centralidade na MST ===\n");
    
    // Executar Kruskal para obter MST
    ArestaLista arestas[MAX_ARESTAS];
    int numArestas;
    
    obterTodasArestas(grafo, arestas, &numArestas);
    qsort(arestas, numArestas, sizeof(ArestaLista), compararArestas);
    
    UnionFind uf;
    inicializarUnionFind(&uf, grafo->numVertices);
    
    int grauMST[MAX_VERTICES] = {0}; // Grau de cada vértice na MST
    
    for (int i = 0; i < numArestas && numArestas < grafo->numVertices - 1; i++) {
        int u = arestas[i].origem;
        int v = arestas[i].destino;
        
        if (encontrar(&uf, u) != encontrar(&uf, v)) {
            grauMST[u]++;
            grauMST[v]++;
            unir(&uf, u, v);
        }
    }
    
    printf("Grau dos vértices na MST:\n");
    for (int i = 0; i < grafo->numVertices; i++) {
        printf("Vértice %d: grau %d", i, grauMST[i]);
        if (grauMST[i] == 1) {
            printf(" (folha)");
        } else if (grauMST[i] > 2) {
            printf(" (hub)");
        }
        printf("\n");
    }
    printf("\n");
}
 
// Função para liberar memória do grafo
void liberarGrafo(GrafoPonderado* grafo) {
    for (int i = 0; i < grafo->numVertices; i++) {
        Aresta* atual = grafo->vertices[i].adjacentes;
        while (atual != NULL) {
            Aresta* temp = atual;
            atual = atual->proxima;
            free(temp);
        }
    }
    free(grafo);
}
 
// ==================== FUNÇÃO PRINCIPAL ====================
 
int main() {
    printf("=== DEMONSTRAÇÃO DE ÁRVORES DE ABRANGÊNCIA MÍNIMA ===\n\n");
    
    // Exemplo 1: Grafo básico
    printf("EXEMPLO 1: Grafo básico\n");
    printf("=======================\n");
    
    GrafoPonderado* grafo1 = criarGrafo(6, false);
    
    // Adicionar arestas (grafo conectado)
    adicionarAresta(grafo1, 0, 1, 4);
    adicionarAresta(grafo1, 0, 2, 2);
    adicionarAresta(grafo1, 1, 2, 1);
    adicionarAresta(grafo1, 1, 3, 5);
    adicionarAresta(grafo1, 2, 3, 8);
    adicionarAresta(grafo1, 2, 4, 10);
    adicionarAresta(grafo1, 3, 4, 2);
    adicionarAresta(grafo1, 3, 5, 6);
    adicionarAresta(grafo1, 4, 5, 3);
    
    printf("Arestas do grafo:\n");
    printf("(0,1):4, (0,2):2, (1,2):1, (1,3):5, (2,3):8\n");
    printf("(2,4):10, (3,4):2, (3,5):6, (4,5):3\n\n");
    
    compararAlgoritmosMST(grafo1);
    
    // Exemplo 2: Análises especiais
    printf("EXEMPLO 2: Análises Especiais\n");
    printf("==============================\n");
    
    encontrarMSTComRestricoes(grafo1, 5);
    analisarCentralidade(grafo1);
    
    // Exemplo 3: Grafo com pesos iguais
    printf("EXEMPLO 3: Grafo com múltiplas MSTs possíveis\n");
    printf("==============================================\n");
    
    GrafoPonderado* grafo2 = criarGrafo(4, false);
    adicionarAresta(grafo2, 0, 1, 1);
    adicionarAresta(grafo2, 0, 2, 1);
    adicionarAresta(grafo2, 1, 2, 1);
    adicionarAresta(grafo2, 1, 3, 1);
    adicionarAresta(grafo2, 2, 3, 1);
    
    printf("Todas as arestas têm peso 1 - múltiplas MSTs possíveis\n\n");
    compararAlgoritmosMST(grafo2);
    
    // Exemplo 4: Demonstração de eficiência
    printf("EXEMPLO 4: Análise de Complexidade\n");
    printf("===================================\n");
    printf("Complexidades dos algoritmos:\n");
    printf("• Prim com heap binário: O(E log V)\n");
    printf("• Prim com heap de Fibonacci: O(E + V log V)\n");
    printf("• Kruskal: O(E log E) = O(E log V)\n\n");
    
    printf("Escolha do algoritmo:\n");
    printf("• Grafo denso (E ≈ V²): Prefira Prim\n");
    printf("• Grafo esparso (E ≈ V): Ambos são eficientes\n");
    printf("• Arestas já ordenadas: Kruskal pode ser mais rápido\n\n");
    
    liberarGrafo(grafo1);
    liberarGrafo(grafo2);
    
    return 0;
}