LaboratórioGrafos

Prática de Grafos

Dez programas completos em C++17 para representar redes, percorrer vértices e calcular caminhos. Cada atividade treina diretamente uma técnica, sem depender de plataformas de competição.

10exercícios progressivos

C++17soluções comentadas

5grupos de técnicas

Seu progresso0 de 10 concluídos

Antes de programar

Modele, desenhe e teste

Modele

Defina vértices e arestas.

Represente

Escolha matriz ou lista.

Percorra

Controle os visitados.

Teste

Inclua ciclos e desconexões.

Implementações guiadas

Da representação aos algoritmos de caminho

01InicialLista de adjacênciaConcluído

Construa e imprima um grafo não direcionado

Crie um grafo com cinco vértices, adicione conexões nos dois sentidos e imprima os vizinhos de cada vértice.

Ver dica

Use uma lista de listas. Para a aresta u—v, registre v em u e u em v.

Ver resolução comentada

#include <algorithm>
#include <iostream>
#include <vector>

class Grafo {
    std::vector<std::vector<int>> adj;

public:
    explicit Grafo(int vertices) : adj(vertices) {}

    void adicionar_aresta(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void remover_aresta(int u, int v) {
        auto remover = [](std::vector<int>& lista, int alvo) {
            lista.erase(std::remove(lista.begin(), lista.end(), alvo), lista.end());
        };
        remover(adj[u], v);
        remover(adj[v], u);
    }

    void mostrar() const {
        for (int u = 0; u < static_cast<int>(adj.size()); ++u) {
            std::cout << u << ":";
            for (int v : adj[u]) std::cout << ' ' << v;
            std::cout << '\n';
        }
    }
};

int main() {
    Grafo grafo(5);
    grafo.adicionar_aresta(0, 1);
    grafo.adicionar_aresta(0, 3);
    grafo.adicionar_aresta(1, 2);
    grafo.remover_aresta(0, 3);
    grafo.mostrar();
}

Técnica: a lista ocupa O(V + E) de memória e é adequada para grafos esparsos.

02InicialMatriz de adjacênciaConcluído

Consulte conexões em tempo constante

Implemente uma matriz que permita adicionar, remover e consultar uma aresta de um grafo não direcionado.

Ver dica

A posição matriz[u][v] responde se a conexão existe. Mantenha a matriz simétrica.

Ver resolução comentada

#include <iostream>
#include <vector>

class GrafoMatriz {
    std::vector<std::vector<bool>> matriz;

public:
    explicit GrafoMatriz(int vertices)
        : matriz(vertices, std::vector<bool>(vertices, false)) {}

    void adicionar_aresta(int u, int v) {
        matriz[u][v] = true;
        matriz[v][u] = true;
    }

    void remover_aresta(int u, int v) {
        matriz[u][v] = false;
        matriz[v][u] = false;
    }

    bool existe(int u, int v) const {
        return matriz[u][v];
    }
};

int main() {
    GrafoMatriz grafo(4);
    grafo.adicionar_aresta(0, 3);
    std::cout << std::boolalpha << grafo.existe(0, 3) << '\n';
    grafo.remover_aresta(0, 3);
    std::cout << grafo.existe(0, 3) << '\n';
}

Escolha: a consulta é O(1), mas a memória é O(V²).

03IntermediárioBFSConcluído

Percorra o grafo em largura

A partir do vértice zero, visite primeiro seus vizinhos e depois os vizinhos deles.

Ver dica

Marque o vértice como visitado quando ele entra na fila. Assim ele nunca é enfileirado duas vezes.

Ver resolução comentada

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> bfs(const std::vector<std::vector<int>>& adj, int origem) {
    std::vector<bool> visitado(adj.size(), false);
    std::queue<int> fila;
    std::vector<int> ordem;

    visitado[origem] = true;
    fila.push(origem);

    while (!fila.empty()) {
        int atual = fila.front();
        fila.pop();
        ordem.push_back(atual);

        for (int vizinho : adj[atual]) {
            if (!visitado[vizinho]) {
                visitado[vizinho] = true;
                fila.push(vizinho);
            }
        }
    }

    return ordem;
}

int main() {
    std::vector<std::vector<int>> grafo{
        {1, 2}, {0, 3}, {0, 4}, {1}, {2}
    };

    for (int vertice : bfs(grafo, 0))
        std::cout << vertice << ' ';
}

Complexidade: cada vértice e aresta é processado poucas vezes: O(V + E).

04IntermediárioDFSConcluído

Percorra o grafo em profundidade

Implemente uma DFS recursiva que avance por um caminho até não encontrar vizinhos novos.

Ver dica

O vetor de visitados deve ser compartilhado por todas as chamadas recursivas.

Ver resolução comentada

#include <iostream>
#include <vector>

void dfs_recursiva(
    const std::vector<std::vector<int>>& adj,
    int atual,
    std::vector<bool>& visitado
) {
    visitado[atual] = true;
    std::cout << atual << ' ';

    for (int vizinho : adj[atual])
        if (!visitado[vizinho])
            dfs_recursiva(adj, vizinho, visitado);
}

int main() {
    std::vector<std::vector<int>> grafo{
        {1, 2}, {0, 3}, {0, 4}, {1}, {2}
    };
    std::vector<bool> visitado(grafo.size(), false);
    dfs_recursiva(grafo, 0, visitado);
}

Estado: a pilha de chamadas guarda o caminho atual da busca.

05IntermediárioComponentesConcluído

Conte componentes conectados

Determine quantos grupos isolados existem em um grafo não direcionado.

Ver dica

Cada DFS iniciada em um vértice ainda não visitado descobre um componente inteiro.

Ver resolução comentada

#include <iostream>
#include <vector>

void marcar(
    const std::vector<std::vector<int>>& adj,
    int atual,
    std::vector<bool>& visitado
) {
    visitado[atual] = true;
    for (int vizinho : adj[atual])
        if (!visitado[vizinho])
            marcar(adj, vizinho, visitado);
}

int contar_componentes(const std::vector<std::vector<int>>& adj) {
    std::vector<bool> visitado(adj.size(), false);
    int componentes = 0;

    for (int vertice = 0; vertice < static_cast<int>(adj.size()); ++vertice) {
        if (!visitado[vertice]) {
            marcar(adj, vertice, visitado);
            ++componentes;
        }
    }

    return componentes;
}

int main() {
    std::vector<std::vector<int>> grafo{{1}, {0}, {3}, {2}, {}};
    std::cout << contar_componentes(grafo) << '\n';
}

Leitura: há os grupos {0,1,2}, {3,4} e {5}.

06IntermediárioExistência de caminhoConcluído

Verifique se dois vértices estão conectados

Retorne verdadeiro se for possível sair de uma origem e alcançar um destino.

Ver dica

Interrompa a busca assim que o destino for retirado da fila.

Ver resolução comentada

#include <iostream>
#include <queue>
#include <vector>

bool existe_caminho(
    const std::vector<std::vector<int>>& adj,
    int origem,
    int destino
) {
    std::vector<bool> visitado(adj.size(), false);
    std::queue<int> fila;
    fila.push(origem);
    visitado[origem] = true;

    while (!fila.empty()) {
        int atual = fila.front();
        fila.pop();

        if (atual == destino) return true;

        for (int vizinho : adj[atual]) {
            if (!visitado[vizinho]) {
                visitado[vizinho] = true;
                fila.push(vizinho);
            }
        }
    }

    return false;
}

int main() {
    std::vector<std::vector<int>> grafo{{1}, {0, 2}, {1}, {4}, {3}};
    std::cout << std::boolalpha;
    std::cout << existe_caminho(grafo, 0, 2) << '\n';
    std::cout << existe_caminho(grafo, 0, 4) << '\n';
}

Aplicação: a mesma ideia responde se duas pessoas, computadores ou cidades pertencem à mesma rede alcançável.

07AvançadoDetecção de cicloConcluído

Detecte ciclos em um grafo não direcionado

Use DFS e diferencie o vértice pai de uma aresta que retorna a um vértice já visitado.

Ver dica

Encontrar um vizinho visitado só caracteriza ciclo quando esse vizinho não é o pai do vértice atual.

Ver resolução comentada

#include <iostream>
#include <vector>

bool dfs_ciclo(
    const std::vector<std::vector<int>>& adj,
    int atual,
    int pai,
    std::vector<bool>& visitado
) {
    visitado[atual] = true;

    for (int vizinho : adj[atual]) {
        if (!visitado[vizinho]) {
            if (dfs_ciclo(adj, vizinho, atual, visitado)) return true;
        } else if (vizinho != pai) {
            return true;
        }
    }

    return false;
}

bool possui_ciclo(const std::vector<std::vector<int>>& adj) {
    std::vector<bool> visitado(adj.size(), false);

    for (int v = 0; v < static_cast<int>(adj.size()); ++v)
        if (!visitado[v] && dfs_ciclo(adj, v, -1, visitado))
            return true;

    return false;
}

int main() {
    std::vector<std::vector<int>> grafo{{1, 2}, {0, 2}, {0, 1}};
    std::cout << std::boolalpha << possui_ciclo(grafo) << '\n';
}

Detalhe: o laço externo também verifica componentes desconectados.

08IntermediárioMenor distância sem pesosConcluído

Calcule distâncias com BFS

Calcule o menor número de arestas da origem até cada vértice de um grafo sem pesos.

Ver dica

Ao descobrir v a partir de u, sua distância é dist[u] + 1.

Ver resolução comentada

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> distancias_bfs(
    const std::vector<std::vector<int>>& adj,
    int origem
) {
    std::vector<int> distancia(adj.size(), -1);
    std::queue<int> fila;

    distancia[origem] = 0;
    fila.push(origem);

    while (!fila.empty()) {
        int atual = fila.front();
        fila.pop();

        for (int vizinho : adj[atual]) {
            if (distancia[vizinho] == -1) {
                distancia[vizinho] = distancia[atual] + 1;
                fila.push(vizinho);
            }
        }
    }

    return distancia;
}

int main() {
    std::vector<std::vector<int>> grafo{{1, 2}, {0, 3}, {0, 3}, {1, 2}};
    for (int distancia : distancias_bfs(grafo, 0))
        std::cout << distancia << ' ';
}

Por que funciona: a fila processa os vértices em camadas crescentes de distância.

09AvançadoDijkstraConcluído

Encontre caminhos mínimos com pesos

Implemente Dijkstra com uma fila de prioridade para arestas de peso não negativo.

Ver dica

Relaxe a aresta quando dist[u] + peso < dist[v]. Ignore entradas antigas da fila.

Ver resolução comentada

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

using Aresta = std::pair<int, int>; // vizinho, peso

std::vector<int> dijkstra(
    const std::vector<std::vector<Aresta>>& adj,
    int origem
) {
    const int infinito = std::numeric_limits<int>::max();
    std::vector<int> distancia(adj.size(), infinito);

    using Estado = std::pair<int, int>; // distância, vértice
    std::priority_queue<Estado, std::vector<Estado>, std::greater<Estado>> fila;

    distancia[origem] = 0;
    fila.push({0, origem});

    while (!fila.empty()) {
        auto [dist_atual, atual] = fila.top();
        fila.pop();

        if (dist_atual != distancia[atual]) continue;

        for (auto [vizinho, peso] : adj[atual]) {
            int nova = dist_atual + peso;
            if (nova < distancia[vizinho]) {
                distancia[vizinho] = nova;
                fila.push({nova, vizinho});
            }
        }
    }

    return distancia;
}

int main() {
    std::vector<std::vector<Aresta>> grafo{
        {{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}
    };

    for (int distancia : dijkstra(grafo, 0))
        std::cout << distancia << ' ';
}

Restrição: Dijkstra não é correto quando existem pesos negativos.

10AvançadoOrdenação topológicaConcluído

Organize tarefas com dependências

Dado um grafo direcionado acíclico, produza uma ordem na qual toda dependência apareça antes da tarefa que depende dela.

Ver dica

Use o algoritmo de Kahn: comece pelos vértices de grau de entrada zero e reduza o grau dos seus vizinhos.

Ver resolução comentada

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> ordenacao_topologica(
    const std::vector<std::vector<int>>& adj
) {
    std::vector<int> grau_entrada(adj.size(), 0);

    for (const auto& vizinhos : adj)
        for (int v : vizinhos)
            ++grau_entrada[v];

    std::queue<int> fila;
    for (int v = 0; v < static_cast<int>(adj.size()); ++v)
        if (grau_entrada[v] == 0)
            fila.push(v);

    std::vector<int> ordem;

    while (!fila.empty()) {
        int atual = fila.front();
        fila.pop();
        ordem.push_back(atual);

        for (int vizinho : adj[atual])
            if (--grau_entrada[vizinho] == 0)
                fila.push(vizinho);
    }

    if (ordem.size() != adj.size()) return {};
    return ordem;
}

int main() {
    std::vector<std::vector<int>> grafo{{1, 2}, {3}, {3}, {}};

    for (int vertice : ordenacao_topologica(grafo))
        std::cout << vertice << ' ';
}

Aplicação: dependências de disciplinas, tarefas, pacotes e etapas de compilação formam grafos direcionados.