Aula prática · Percurso em grafos

DFS vai fundo. BFS espalha.

Vamos percorrer o mesmo grafo da aula anterior de duas maneiras diferentes e observar, passo a passo, o que acontece com os vértices e com a estrutura auxiliar.

DFS BFS Recursão / Pilha Fila Matriz Lista de adjacência

Uma árvore para enxergar DFS e BFS

Nesta aula, usaremos uma árvore com 8 vértices e 7 arestas. Ela facilita a comparação: a DFS desce por um ramo; a BFS visita nível por nível.

Lista de adjacência

A: B, C
B: A, D, E
C: A, F, G
D: B, H
E: B
F: C
G: C
H: D

Regra da animação

Sempre que houver dois filhos, visitaremos da esquerda para a direita. É por isso que B vem antes de C, D antes de E, e F antes de G.

DFS — Busca em Profundidade

A DFS escolhe um caminho e vai o mais fundo possível. Quando não existe novo vizinho, ela retorna para a chamada anterior.

Estrutura mental: marcar → escolher vizinho → entrar nele → continuar → voltar quando necessário.

atual na pilha / caminho visitado

Execução da DFS passo 0/8

Clique em “Próximo” ou “Executar”.

Visitados []

Pilha de chamadas []

Ordem de visita —

Velocidade

Ordem desta DFS: A → B → D → H → E → C → F → G. Ela não visita “por nível”; ela segue uma ramificação antes de voltar.

DFS nas duas representações

A ideia da DFS é a mesma. O que muda é como encontramos os vizinhos.

#include <array>
#include <iostream>

constexpr int quantidade = 8;
std::array<char, quantidade> vertices{'A','B','C','D','E','F','G','H'};
std::array<std::array<int, quantidade>, quantidade> adj{};

void adicionar_aresta(int a, int b) {
    adj[a][b] = 1;
    adj[b][a] = 1;
}

std::array<bool, quantidade> visitado{};

void dfs(int v) {
    visitado[v] = true;
    std::cout << vertices[v] << ' ';

    for (int w = 0; w < quantidade; ++w)
        if (adj[v][w] && !visitado[w])
            dfs(w);
}

#include <iostream>
#include <vector>

std::vector<char> vertices{'A','B','C','D','E','F','G','H'};
std::vector<std::vector<int>> grafo{
    {1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 7},
    {1}, {2}, {2}, {3}
};

std::vector<bool> visitado(vertices.size(), false);

void dfs(int v) {
    visitado[v] = true;
    std::cout << vertices[v] << ' ';

    for (int w : grafo[v])
        if (!visitado[w])
            dfs(w);
}

Matriz

Procura vizinhos

Examina a linha inteira adj[v], mesmo onde não existe aresta.

Lista

Já conhece os vizinhos

O laço percorre diretamente grafo[v].

BFS — Busca em Largura

A BFS explora o grafo por camadas. Primeiro os vizinhos do início, depois os vizinhos deles, e assim por diante.

Estrutura mental: marcar → colocar na fila → retirar da frente → adicionar novos vizinhos ao final.

retirado da fila aguardando na fila processado

Execução da BFS passo 0/8

Clique em “Próximo” ou “Executar”.

Processados []

Fila []

Ordem de visita —

Velocidade

Ordem desta BFS: A → B → C → D → E → F → G → H. Repare que os vértices mais próximos de A aparecem antes.

Pela árvore usada nesta aula, a BFS fica bem visual: primeiro vem o nível de A; depois B e C; depois D, E, F e G; por último H. É como ler a árvore linha por linha, de cima para baixo.

BFS nas duas representações

A BFS precisa de uma fila. Novamente, matriz e lista mudam apenas a forma de encontrar vizinhos.

#include <array>
#include <iostream>
#include <queue>

constexpr int quantidade = 8;
std::array<char, quantidade> vertices{'A','B','C','D','E','F','G','H'};
std::array<std::array<int, quantidade>, quantidade> adj{};

void bfs(int origem) {
    std::array<bool, quantidade> visitado{};
    std::queue<int> fila;

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

    while (!fila.empty()) {
        int v = fila.front();
        fila.pop();
        std::cout << vertices[v] << ' ';

        for (int w = 0; w < quantidade; ++w) {
            if (adj[v][w] && !visitado[w]) {
                visitado[w] = true;
                fila.push(w);
            }
        }
    }
}

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

std::vector<char> vertices{'A','B','C','D','E','F','G','H'};
std::vector<std::vector<int>> grafo{
    {1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 7},
    {1}, {2}, {2}, {3}
};

void bfs(int origem) {
    std::vector<bool> visitado(vertices.size(), false);
    std::queue<int> fila;

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

    while (!fila.empty()) {
        int v = fila.front();
        fila.pop();
        std::cout << vertices[v] << ' ';

        for (int w : grafo[v]) {
            if (!visitado[w]) {
                visitado[w] = true;
                fila.push(w);
            }
        }
    }
}

Na BFS, normalmente marcamos o vértice como visitado quando ele entra na fila. Assim evitamos colocar o mesmo vértice várias vezes.

DFS × BFS — lado a lado

DFS

Vai fundo

A→ B→ C→ E→ D→ G→ H→ F

BFS

Vai por camadas

A→ B→ C→ D→ E→ F→ G→ H

Característica	DFS	BFS
Estrutura típica	Recursão ou pilha	Fila
Comportamento	Aprofunda um caminho	Explora por níveis
Menor nº de arestas em grafo sem peso	Não garante	Sim
Componentes / exploração	Excelente	Excelente
Detecção e exploração de estruturas	Muito comum	Também possível

Complexidade: o algoritmo é igual, a representação pesa

Matriz

DFS e BFS: O(V²)

Para cada vértice processado, examinamos V posições da matriz para descobrir os vizinhos.

Lista

DFS e BFS: O(V + E)

Cada vértice é visitado e as arestas armazenadas são percorridas diretamente.

Para estruturas de dados, lista de adjacência + DFS/BFS é uma combinação extremamente comum.

✓

Resumo da Aula 2

DFS

Recursão/pilha. Segue uma ramificação até não conseguir avançar.

BFS

Fila. Visita primeiro os vértices mais próximos do ponto inicial.

Representação

Matriz funciona, mas a lista costuma ser mais eficiente para grafos esparsos.