Algoritmo de Depth First Search (DFS)

Imagine que está a controlar um robô colocado em algum ponto de um grafo com n vértices e e arestas. O objetivo é partir de um vértice inicial e ir percorrendo gradualmente todo o grafo ao visitar todos os vértices que sejam alcançáveis a partir desse ponto de partida. O algoritmo DFS permite fazer exatamente isso ao começar por um vértice específico, explorar um caminho até não haver mais vértices nesse trajeto e depois recuar para os nós anteriores, continuando a exploração a partir daí.

Uma forma muito útil de pensar no algoritmo DFS é considerar a ideia de um robô que começa a explorar o grafo só conseguindo ver os vizinhos do nó atual e todos os nós por onde já passou (ou seja, o robô guarda a informação de todo o caminho). É um processo recursivo em que, a cada passo, o robô se desloca para algum vértice ainda não explorado e repete esse esquema até esgotar as possibilidades nesse percurso. Ter em mente a analogia de um pequeno robô que explora o grafo ajuda bastante na implementação.

A implementação do algoritmo DFS pode ser feita de forma recursiva, onde se acompanha o vértice atual (que iremos chamar de v) e todos os vértices visitados até ao momento (marcados em used):

import sys

sys.setrecursionlimit(10 ** 6)          # Aumenta o limite de recursão para que o DFS seja executado corretamente

n, e = map(int, input().split())        # n: vértices, e: arestas
g = [[] for _ in range(n)]              # grafo - lista de adjacências
used = [False] * n                      # vértices usados (visitados)

for _ in range(e):                      # lê as arestas
    a, b = map(int, input().split())    # a -> b e b -> a
    g[a].append(b)
    g[b].append(a)


def dfs(v):                             # pesquisa em profundidade
    used[v] = True                      # marca o vértice como visitado
    print(v, end=' ')                   # imprime o vértice
    for to in g[v]:                     # para cada vértice ligado a v
        if not used[to]:                # se o vértice ainda não foi visitado
            dfs(to)                     # chama dfs nesse vértice


start = int(input())                    # vértice inicial
dfs(start)                              # chama dfs a partir do vértice inicial

Aqui, inicializamos primeiro o grafo e começamos a travessia a partir do vértice start. Inicialmente, todos os valores em used estão a False. Depois de visitar cada vértice, marcamo-lo como used[v] = True e prosseguimos para todos os vizinhos do vértice atual v.

Repare em como a recursão representa bem a exploração de um caminho e o retorno ao local anterior, para continuar a explorar os vizinhos do vértice anterior. Ao recuarmos na recursão, basicamente voltamos ao vértice anterior.

Vejamos grandes linhas do funcionamento do algoritmo com alguns exemplos de entrada:

Desafio: Calcular o Número de Componentes Conexas num Grafo

Dado um grafo não direcionado com v vértices e e arestas, o seu objetivo é calcular quantas componentes conexas existem. Um conjunto de vértices é considerado uma componente conexa se for possível viajar entre todos os vértices desse conjunto.

Entrada

A primeira linha da entrada contém dois inteiros v (1 ≤ v ≤ 100 000) e e (1 ≤ e ≤ 100 000).

As seguintes e linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v) indicando que o vértice v1 está ligado ao vértice v2 e vice-versa.

Saída

O programa deve imprimir o número de componentes conexas no grafo.

Exemplos