Aula prática · DFS com matriz de adjacência

Agora o algoritmo com o exemplo real.

Vamos acompanhar os dois casos de teste, observar a matriz, seguir a recursão e entender exatamente por que as respostas são 30 e 10.

beecrowd 1076 DFS recursiva Matriz lbl[] 30 / 10
01

Resumo do problema e da solução

Pedro quer desenhar um labirinto sem levantar a caneta do papel. Ele escolhe um nodo para começar, precisa passar por todas as linhas disponíveis do desenho e, no final, voltar para o mesmo nodo inicial.

Problema

O que precisamos descobrir?

Para cada caso de teste, recebemos o nodo inicial, a quantidade de vértices e as arestas do labirinto. A pergunta é: qual é o menor número de movimentos de caneta necessário para percorrer o desenho, saindo e terminando no mesmo ponto?

Solução

Por que DFS resolve?

Como o enunciado garante que não haverá ciclos, cada nova ligação descoberta pela DFS funciona como um caminho que Pedro precisa fazer na ida e repetir na volta. Por isso, a resposta é 2 × quantidade de arestas usadas para alcançar novos vértices.

A ideia central é simples: sempre que a DFS encontra um vértice novo, Pedro fez um movimento para entrar nele. Como ele precisa terminar no ponto inicial sem levantar a caneta, esse caminho também precisa ser contado na volta. Então cada descoberta vale 2 movimentos.
Entrada

Origem

O primeiro número de cada caso indica onde Pedro começa e onde deve terminar.

Grafo

Labirinto

Os nodos são os vértices; os segmentos informados são as arestas disponíveis para desenhar.

Resposta

Movimentos

Contamos quantas novas arestas a DFS usa e multiplicamos esse valor por 2.

02

Entrada e saída do exemplo

Entrada

2 0 16 15 0 4 2 3 6 2 8 9 10 9 8 12 14 15 14 10 6 5 10 11 11 7 4 8 0 1 1 2 12 13 1 9 6 1 2 1 4 4 7 7 8 4 1 4 3

Saída esperada

30
10
Caso 1

16 vértices · 15 arestas

Origem = 0. Todos os 16 vértices são alcançados pela DFS.

Caso 2

9 vértices · 6 linhas de aresta

Origem = 1. Apenas seis vértices são alcançados e uma ligação aparece repetida.

03

O algoritmo em uma frase

O programa monta uma matriz de adjacência e usa uma DFS recursiva para descobrir novos vértices a partir da origem.

Ler origem
→
Montar adj[][]
→
lbl = -1
→
pathR(origem)
→
Contar descobertas
→
× 2
lbl

Visitado?

-1 significa “ainda não visitei”. Qualquer outro valor significa visitado.

cnt

Ordem

Numera a ordem em que os vértices são descobertos pela DFS.

movimentos

Descobertas

Incrementa apenas quando a DFS entra em um vértice ainda não visitado.

04

A DFS está aqui: pathR(v)

lbl[v] = cnt
cnt += 1
Marca v como visitado. O valor salvo indica a ordem da visita.
for w in range(V):
Examina a linha v da matriz. Como é matriz, o algoritmo testa todos os possíveis w.
if adj[v][w] == 1:
Existe uma aresta v–w? O valor 1 na matriz confirma a ligação.
if lbl[w] == -1:
w ainda não foi visitado? Este teste evita entrar novamente em vértices conhecidos.
movimentos += 1
pathR(w)
Descobriu um novo vértice. Conta uma ligação e entra recursivamente em w.
A linha pathR(w) é o “vai fundo” da DFS. Quando essa chamada termina, o Python retorna automaticamente para o vértice anterior.
05

Os dois grafos do exemplo

O primeiro caso é praticamente uma árvore: 16 vértices, 15 arestas e todos alcançáveis a partir de 0.

0 1 4 2 3 6 5 8 9 12 10 13 11 14 7 15
16vértices visitados
15novas descobertas
30saída = 15 × 2

No segundo caso, 0, 5 e 6 ficam isolados. Além disso, a aresta 1–4 aparece duas vezes na entrada.

1 2 4 3 7 8 0 5 6 vértices não alcançados a partir da origem 1
ligação normal 1–4 aparece novamente como 4–1
6vértices visitados
5novas descobertas
10saída = 5 × 2
06

Execução animada dos dois casos

Escolha o caso e acompanhe a ordem exata produzida pelo laço for w in range(V).

0 1 4 2 3 6 5 8 9 12 10 13 11 14 7 15
atual visitado não visitado
1
lbl[v] = cnt
2
cnt += 1
3
for w in range(V):
4
if adj[v][w] == 1:
5
if lbl[w] == -1:
6
movimentos += 1
7
pathR(w)
Execução passo 0
Clique em “Próximo” ou “Executar”.
ordem de visita—
cnt0
movimentos0
lbl—
07

O detalhe que explica o segundo resultado

No segundo caso aparecem estas duas linhas:

Entrada 
1 4
...
4 1
Na matriz 
adj[1][4] = 1
adj[4][1] = 1
Como o grafo é não direcionado, 1 4 já cria os dois sentidos. Quando aparece 4 1, o programa apenas escreve 1 nas mesmas células novamente. Não nasce uma nova ligação.
DadoValorInterpretação
A informado6Foram fornecidas 6 linhas de arestas.
Ligações distintas alcançáveis51–2, 1–4, 4–3, 4–7 e 7–8.
Vértices alcançados61, 2, 4, 3, 7 e 8.
movimentos5Uma descoberta para cada novo vértice após a origem.
Saída105 × 2.
08

Por que as respostas são 30 e 10?

Caso 1

15 descobertas

A origem é 0. Existem 16 vértices alcançáveis. Depois do primeiro, cada novo vértice exige uma nova aresta da árvore DFS: 16 − 1 = 15.

15 × 2 = 30
Caso 2

5 descobertas

A partir de 1, somente 6 vértices são alcançados. Portanto a árvore DFS possui 6 − 1 = 5 arestas.

5 × 2 = 10
A ideia mais importante é esta: o contador aumenta quando descobrimos um vértice novo, não simplesmente para cada linha da entrada.
09

Código completo comentado

cnt = 0
movimentos = 0
V = 0

adj = []
lbl = []


def pathR(v):
    global cnt, movimentos

    # Marca v como visitado.
    # cnt também registra a ordem da descoberta.
    lbl[v] = cnt
    cnt += 1

    # Como a representação é uma matriz,
    # testamos todos os possíveis vértices w.
    for w in range(V):

        # Há uma aresta entre v e w?
        if adj[v][w] == 1:

            # w ainda não foi visitado?
            if lbl[w] == -1:

                # Descobrimos um novo vértice pela aresta v-w.
                movimentos += 1

                # Aprofunda a DFS.
                pathR(w)


def DIGRAPHpath(origem):
    global lbl, cnt

    # Todos começam como não visitados.
    lbl = [-1] * V
    cnt = 0

    # Começa a busca a partir da origem.
    pathR(origem)


# Quantidade de casos de teste.
casos = int(input())

for _ in range(casos):

    origem = int(input())

    # V = vértices | A = linhas de arestas da entrada.
    V, A = map(int, input().split())

    # Matriz V × V inicialmente zerada.
    adj = [
        [0 for _ in range(V)]
        for _ in range(V)
    ]

    movimentos = 0

    for _ in range(A):
        orig, dest = map(int, input().split())

        # Grafo não direcionado:
        # a mesma ligação é registrada nos dois sentidos.
        adj[orig][dest] = 1
        adj[dest][orig] = 1

    DIGRAPHpath(origem)

    # Cada aresta da árvore DFS é considerada na ida e na volta.
    print(movimentos * 2)