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.

vertices = ["A", "B", "C", "D", "E", "F", "G", "H"]
arestas = [
    ("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"),
    ("C", "F"), ("C", "G"), ("D", "H"),
]

# A matriz usa índices; este dicionário converte a letra em posição.
indice = {vertice: i for i, vertice in enumerate(vertices)}
quantidade = len(vertices)
adj = [[0] * quantidade for _ in range(quantidade)]

for a, b in arestas:
    i, j = indice[a], indice[b]
    adj[i][j] = 1
    adj[j][i] = 1  # A árvore não é direcionada.


def dfs(v):
    # Marcar antes de aprofundar evita visitar o mesmo vértice novamente.
    visitado[v] = True
    print(vertices[v])

    # Na matriz, examinamos todas as colunas da linha de v.
    for w in range(quantidade):
        if adj[v][w] == 1 and not visitado[w]:
            dfs(w)


visitado = [False] * quantidade
dfs(indice["A"])

grafo = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B", "H"],
    "E": ["B"],
    "F": ["C"],
    "G": ["C"],
    "H": ["D"],
}


def dfs(v):
    # O conjunto registra os vértices já descobertos.
    visitado.add(v)
    print(v)

    # A lista grafo[v] contém somente os vizinhos de v.
    for vizinho in grafo[v]:
        if vizinho not in visitado:
            dfs(vizinho)


visitado = set()
dfs("A")

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.

from collections import deque

vertices = ["A", "B", "C", "D", "E", "F", "G", "H"]
arestas = [
    ("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"),
    ("C", "F"), ("C", "G"), ("D", "H"),
]
indice = {vertice: i for i, vertice in enumerate(vertices)}
quantidade = len(vertices)
adj = [[0] * quantidade for _ in range(quantidade)]

for a, b in arestas:
    i, j = indice[a], indice[b]
    adj[i][j] = adj[j][i] = 1


def bfs(origem):
    fila = deque([origem])
    visitado = [False] * quantidade
    visitado[origem] = True  # Marcar na entrada evita duplicatas na fila.

    while fila:
        v = fila.popleft()  # Sempre processamos o mais antigo da fila.
        print(vertices[v])

        # Na matriz, examinamos todas as possíveis posições vizinhas.
        for w in range(quantidade):
            if adj[v][w] == 1 and not visitado[w]:
                visitado[w] = True
                fila.append(w)


bfs(indice["A"])

from collections import deque

grafo = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B", "H"],
    "E": ["B"], "F": ["C"], "G": ["C"], "H": ["D"],
}


def bfs(origem):
    fila = deque([origem])
    visitado = {origem}  # A origem já entrou na fila.

    while fila:
        v = fila.popleft()
        print(v)

        # A lista fornece diretamente os vizinhos do vértice atual.
        for vizinho in grafo[v]:
            if vizinho not in visitado:
                visitado.add(vizinho)
                fila.append(vizinho)


bfs("A")

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 programação competitiva, 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.