Grafos Ponderados

Aprenda sobre grafos ponderados, suas representações e operações básicas (inserção, remoção, busca).

Definição

Um grafo ponderado é uma estrutura de dados que consiste em um conjunto de vértices (nós) conectados por arestas que possuem pesos (valores numéricos). Os pesos podem representar distâncias, custos, capacidades ou qualquer métrica relevante para o problema específico.

Propriedades fundamentais:

Vértices: Nós do grafo que representam entidades
Arestas: Conexões entre vértices com pesos associados
Peso: Valor numérico atribuído a cada aresta
Direcionado/Não-direcionado: Define se as arestas têm direção específica

Abaixo temos um bloco de código em C que implementa um grafo ponderado usando lista de adjacência:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
 
#define MAX_VERTICES 100
#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;
 
// Função para criar um novo grafo
GrafoPonderado* criarGrafo(int numVertices, bool direcionado) {
    GrafoPonderado* grafo = (GrafoPonderado*)malloc(sizeof(GrafoPonderado));
    grafo->numVertices = numVertices;
    grafo->direcionado = direcionado;
    
    // Inicializar todos os vértices
    for (int i = 0; i < numVertices; i++) {
        grafo->vertices[i].valor = i;
        grafo->vertices[i].adjacentes = NULL;
    }
    
    return grafo;
}
 
// Função para criar uma nova aresta
Aresta* criarAresta(int destino, int peso) {
    Aresta* novaAresta = (Aresta*)malloc(sizeof(Aresta));
    novaAresta->destino = destino;
    novaAresta->peso = peso;
    novaAresta->proxima = NULL;
    return novaAresta;
}
 
// Função para adicionar uma aresta ao grafo
void adicionarAresta(GrafoPonderado* grafo, int origem, int destino, int peso) {
    if (origem >= grafo->numVertices || destino >= grafo->numVertices) {
        printf("Erro: Vértice inválido!\n");
        return;
    }
    
    // Criar nova aresta de origem para destino
    Aresta* novaAresta = criarAresta(destino, peso);
    
    // Inserir no início da lista de adjacência
    novaAresta->proxima = grafo->vertices[origem].adjacentes;
    grafo->vertices[origem].adjacentes = novaAresta;
    
    // Se o grafo é não-direcionado, adicionar aresta reversa
    if (!grafo->direcionado) {
        Aresta* arestaReversa = criarAresta(origem, peso);
        arestaReversa->proxima = grafo->vertices[destino].adjacentes;
        grafo->vertices[destino].adjacentes = arestaReversa;
    }
}
 
// Função para remover uma aresta do grafo
void removerAresta(GrafoPonderado* grafo, int origem, int destino) {
    if (origem >= grafo->numVertices || destino >= grafo->numVertices) {
        printf("Erro: Vértice inválido!\n");
        return;
    }
    
    // Remover aresta de origem para destino
    Aresta* atual = grafo->vertices[origem].adjacentes;
    Aresta* anterior = NULL;
    
    while (atual != NULL && atual->destino != destino) {
        anterior = atual;
        atual = atual->proxima;
    }
    
    if (atual != NULL) {
        if (anterior == NULL) {
            grafo->vertices[origem].adjacentes = atual->proxima;
        } else {
            anterior->proxima = atual->proxima;
        }
        free(atual);
    }
    
    // Se o grafo é não-direcionado, remover aresta reversa
    if (!grafo->direcionado) {
        atual = grafo->vertices[destino].adjacentes;
        anterior = NULL;
        
        while (atual != NULL && atual->destino != origem) {
            anterior = atual;
            atual = atual->proxima;
        }
        
        if (atual != NULL) {
            if (anterior == NULL) {
                grafo->vertices[destino].adjacentes = atual->proxima;
            } else {
                anterior->proxima = atual->proxima;
            }
            free(atual);
        }
    }
}
 
// Função para verificar se existe uma aresta entre dois vértices
int obterPesoAresta(GrafoPonderado* grafo, int origem, int destino) {
    if (origem >= grafo->numVertices || destino >= grafo->numVertices) {
        return -1; // Vértice inválido
    }
    
    Aresta* atual = grafo->vertices[origem].adjacentes;
    while (atual != NULL) {
        if (atual->destino == destino) {
            return atual->peso;
        }
        atual = atual->proxima;
    }
    
    return -1; // Aresta não encontrada
}
 
// Função para imprimir o grafo
void imprimirGrafo(GrafoPonderado* grafo) {
    printf("=== Grafo %s ===\n", grafo->direcionado ? "Direcionado" : "Não-direcionado");
    
    for (int i = 0; i < grafo->numVertices; i++) {
        printf("Vértice %d: ", i);
        
        Aresta* atual = grafo->vertices[i].adjacentes;
        while (atual != NULL) {
            printf("(%d, peso=%d) ", atual->destino, atual->peso);
            atual = atual->proxima;
        }
        printf("\n");
    }
    printf("\n");
}
 
// Função para imprimir a matriz de adjacência (útil para visualização)
void imprimirMatrizAdjacencia(GrafoPonderado* grafo) {
    printf("=== Matriz de Adjacência ===\n");
    printf("   ");
    
    // Imprimir cabeçalho
    for (int i = 0; i < grafo->numVertices; i++) {
        printf("%4d", i);
    }
    printf("\n");
    
    // Imprimir linhas da matriz
    for (int i = 0; i < grafo->numVertices; i++) {
        printf("%2d ", i);
        
        for (int j = 0; j < grafo->numVertices; j++) {
            int peso = obterPesoAresta(grafo, i, j);
            if (peso == -1) {
                printf("   -");
            } else {
                printf("%4d", peso);
            }
        }
        printf("\n");
    }
    printf("\n");
}
 
// Função para obter o grau de um vértice
int obterGrau(GrafoPonderado* grafo, int vertice) {
    if (vertice >= grafo->numVertices) {
        return -1;
    }
    
    int grau = 0;
    Aresta* atual = grafo->vertices[vertice].adjacentes;
    
    while (atual != NULL) {
        grau++;
        atual = atual->proxima;
    }
    
    return grau;
}
 
// Função para calcular o número total de arestas
int contarArestas(GrafoPonderado* grafo) {
    int totalArestas = 0;
    
    for (int i = 0; i < grafo->numVertices; i++) {
        Aresta* atual = grafo->vertices[i].adjacentes;
        while (atual != NULL) {
            totalArestas++;
            atual = atual->proxima;
        }
    }
    
    // Se o grafo é não-direcionado, cada aresta foi contada duas vezes
    if (!grafo->direcionado) {
        totalArestas /= 2;
    }
    
    return totalArestas;
}
 
// Função para busca em profundidade (DFS)
void dfsUtil(GrafoPonderado* grafo, int vertice, bool visitados[]) {
    visitados[vertice] = true;
    printf("%d ", vertice);
    
    Aresta* atual = grafo->vertices[vertice].adjacentes;
    while (atual != NULL) {
        if (!visitados[atual->destino]) {
            dfsUtil(grafo, atual->destino, visitados);
        }
        atual = atual->proxima;
    }
}
 
void dfs(GrafoPonderado* grafo, int verticeInicial) {
    bool visitados[MAX_VERTICES] = {false};
    
    printf("DFS a partir do vértice %d: ", verticeInicial);
    dfsUtil(grafo, verticeInicial, visitados);
    printf("\n");
}
 
// Estrutura para fila (para BFS)
typedef struct {
    int itens[MAX_VERTICES];
    int inicio, fim;
} Fila;
 
void inicializarFila(Fila* fila) {
    fila->inicio = -1;
    fila->fim = -1;
}
 
bool filaVazia(Fila* fila) {
    return fila->inicio == -1;
}
 
void enfileirar(Fila* fila, int item) {
    if (fila->fim == MAX_VERTICES - 1) {
        return; // Fila cheia
    }
    
    if (fila->inicio == -1) {
        fila->inicio = 0;
    }
    
    fila->fim++;
    fila->itens[fila->fim] = item;
}
 
int desenfileirar(Fila* fila) {
    if (filaVazia(fila)) {
        return -1;
    }
    
    int item = fila->itens[fila->inicio];
    fila->inicio++;
    
    if (fila->inicio > fila->fim) {
        fila->inicio = fila->fim = -1;
    }
    
    return item;
}
 
// Função para busca em largura (BFS)
void bfs(GrafoPonderado* grafo, int verticeInicial) {
    bool visitados[MAX_VERTICES] = {false};
    Fila fila;
    inicializarFila(&fila);
    
    printf("BFS a partir do vértice %d: ", verticeInicial);
    
    visitados[verticeInicial] = true;
    enfileirar(&fila, verticeInicial);
    
    while (!filaVazia(&fila)) {
        int verticeAtual = desenfileirar(&fila);
        printf("%d ", verticeAtual);
        
        Aresta* atual = grafo->vertices[verticeAtual].adjacentes;
        while (atual != NULL) {
            if (!visitados[atual->destino]) {
                visitados[atual->destino] = true;
                enfileirar(&fila, atual->destino);
            }
            atual = atual->proxima;
        }
    }
    printf("\n");
}
 
// Função para verificar se o grafo é conectado
bool ehConectado(GrafoPonderado* grafo) {
    if (grafo->numVertices <= 1) {
        return true;
    }
    
    bool visitados[MAX_VERTICES] = {false};
    dfsUtil(grafo, 0, visitados);
    
    // Verificar se todos os vértices foram visitados
    for (int i = 0; i < grafo->numVertices; i++) {
        if (!visitados[i]) {
            return false;
        }
    }
    
    return true;
}
 
// 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);
}

Agora, vamos criar uma função main para demonstrar o funcionamento do grafo ponderado:

// Função principal para demonstrar o grafo ponderado
int main() {
    printf("=== Demonstração de Grafo Ponderado ===\n\n");
    
    // Criar um grafo não-direcionado com 6 vértices
    GrafoPonderado* grafo = criarGrafo(6, false);
    
    // Adicionar arestas com pesos
    printf("Adicionando arestas com pesos:\n");
    adicionarAresta(grafo, 0, 1, 4);
    adicionarAresta(grafo, 0, 2, 2);
    adicionarAresta(grafo, 1, 2, 1);
    adicionarAresta(grafo, 1, 3, 5);
    adicionarAresta(grafo, 2, 3, 8);
    adicionarAresta(grafo, 2, 4, 10);
    adicionarAresta(grafo, 3, 4, 2);
    adicionarAresta(grafo, 3, 5, 6);
    adicionarAresta(grafo, 4, 5, 3);
    
    printf("(0-1, peso=4), (0-2, peso=2), (1-2, peso=1)\n");
    printf("(1-3, peso=5), (2-3, peso=8), (2-4, peso=10)\n");
    printf("(3-4, peso=2), (3-5, peso=6), (4-5, peso=3)\n\n");
    
    // Imprimir o grafo
    imprimirGrafo(grafo);
    
    // Imprimir matriz de adjacência
    imprimirMatrizAdjacencia(grafo);
    
    // Informações do grafo
    printf("=== Informações do Grafo ===\n");
    printf("Número de vértices: %d\n", grafo->numVertices);
    printf("Número de arestas: %d\n", contarArestas(grafo));
    printf("Grafo é conectado: %s\n\n", ehConectado(grafo) ? "Sim" : "Não");
    
    // Grau de cada vértice
    printf("Grau dos vértices:\n");
    for (int i = 0; i < grafo->numVertices; i++) {
        printf("Vértice %d: grau %d\n", i, obterGrau(grafo, i));
    }
    printf("\n");
    
    // Demonstrar buscas
    printf("=== Algoritmos de Busca ===\n");
    dfs(grafo, 0);
    bfs(grafo, 0);
    printf("\n");
    
    // Testar busca de aresta específica
    printf("=== Testes de Aresta ===\n");
    int peso = obterPesoAresta(grafo, 1, 3);
    if (peso != -1) {
        printf("Peso da aresta (1-3): %d\n", peso);
    } else {
        printf("Aresta (1-3) não existe\n");
    }
    
    peso = obterPesoAresta(grafo, 0, 5);
    if (peso != -1) {
        printf("Peso da aresta (0-5): %d\n", peso);
    } else {
        printf("Aresta (0-5) não existe\n");
    }
    
    // Demonstrar remoção de aresta
    printf("\nRemovendo aresta (2-4):\n");
    removerAresta(grafo, 2, 4);
    imprimirGrafo(grafo);
    
    // Criar um grafo direcionado para comparação
    printf("=== Grafo Direcionado ===\n");
    GrafoPonderado* grafoDirecionado = criarGrafo(4, true);
    
    adicionarAresta(grafoDirecionado, 0, 1, 3);
    adicionarAresta(grafoDirecionado, 1, 2, 4);
    adicionarAresta(grafoDirecionado, 2, 3, 2);
    adicionarAresta(grafoDirecionado, 3, 0, 5);
    adicionarAresta(grafoDirecionado, 1, 3, 7);
    
    imprimirGrafo(grafoDirecionado);
    imprimirMatrizAdjacencia(grafoDirecionado);
    
    // Liberar memória
    liberarGrafo(grafo);
    liberarGrafo(grafoDirecionado);
    
    return 0;
}

Representações de Grafos Ponderados

1. Lista de Adjacência (Implementada acima)

Vantagens: Eficiente em espaço para grafos esparsos, rápida para iterar sobre adjacentes
Desvantagens: Busca por aresta específica pode ser O(V) no pior caso
Complexidade de espaço: O(V + E)

2. Matriz de Adjacência

typedef struct {
    int matriz[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
    bool direcionado;
} GrafoMatriz;
 
// Implementação usando matriz
void adicionarArestaMatriz(GrafoMatriz* grafo, int origem, int destino, int peso) {
    grafo->matriz[origem][destino] = peso;
    if (!grafo->direcionado) {
        grafo->matriz[destino][origem] = peso;
    }
}

3. Lista de Arestas

typedef struct {
    int origem;
    int destino;
    int peso;
} ArestaLista;
 
typedef struct {
    ArestaLista arestas[MAX_ARESTAS];
    int numArestas;
    int numVertices;
} GrafoArestas;

Operações Fundamentais

Complexidades das Operações:

Operação	Lista de Adjacência	Matriz de Adjacência
Adicionar vértice	O(1)	O(V²)
Adicionar aresta	O(1)	O(1)
Remover aresta	O(V)	O(1)
Verificar adjacência	O(V)	O(1)
DFS/BFS	O(V + E)	O(V²)

Exemplos de contexto de uso:

Em que situações os grafos ponderados são utilizados?

Sistemas de navegação GPS:
- Vértices representam interseções, arestas representam ruas com pesos sendo distâncias ou tempos de viagem.
Redes de computadores:
- Vértices são roteadores/servidores, arestas são conexões com pesos representando latência, largura de banda ou custo.
Redes sociais:
- Vértices são usuários, arestas representam conexões com pesos indicando força da relação ou frequência de interação.
Logística e supply chain:
- Vértices são centros de distribuição, arestas são rotas de transporte com custos ou tempos associados.
Análise financeira:
- Vértices representam ativos financeiros, arestas representam correlações com pesos indicando força da correlação.
Bioinformática:
- Grafos de proteínas onde vértices são aminoácidos e pesos representam energia de ligação.

A escolha da representação (lista de adjacência vs matriz) depende da densidade do grafo e das operações mais frequentes na aplicação específica.