Algoritmos e Estruturas de Dados

Algoritmo Breadth First Search (BFS)

Imagine que, dado um grafo com n vértices e e arestas, você queira começar a partir de um vértice e gradualmente percorrer todo o grafo, visitando todos os vértices que podem ser alcançados a partir desse ponto inicial. Existem várias maneiras de fazer isso, e uma das abordagens mais conhecidas é o algoritmo BFS (Breadth-First Search). Pela sua natureza, o BFS permite calcular o caminho mais curto entre o vértice de origem e todos os demais vértices do grafo, o que o torna extremamente útil em diversas situações.
Video preview
Uma forma intuitiva de entender o funcionamento do algoritmo BFS é imaginar o grafo pegando fogo e observar como as chamas se espalham. Suponha que cada vértice demore 1 minuto para queimar; ao final desse minuto, o fogo passa para os vizinhos imediatos. Em seguida, os vizinhos também queimam durante 1 minuto e, então, propagam o fogo para os seus próprios vizinhos, e assim sucessivamente.
Então, você “queima” o vértice inicial, e logo o fogo se espalha para todos os vizinhos. Passado um minuto, os vizinhos desses vértices começam a queimar também, e o fogo alcança os vizinhos deles. Esse processo continua até que já não haja mais vértices novos para queimar. Visualizar o grafo dessa forma ajuda bastante na hora de implementar o BFS.
A implementação do algoritmo BFS pode ser feita usando uma queue (fila) e uma lista de vértices que registra aqueles que já foram used (os que estão “queimando”):
from collections import deque

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

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)

start = int(input())                    # vértice inicial
used = [False] * n                      # vértices visitados
q = deque([start])                      # fila de vértices
used[start] = True                      # marca o vértice inicial como visitado

while q:                                # enquanto a fila não estiver vazia
    v = q.popleft()                     # obtém um vértice da fila
    print(v, end=' ')                   # imprime o vértice
    for to in g[v]:                     # para cada vértice conectado a v
        if not used[to]:                # se o vértice ainda não foi visitado
            q.append(to)                # adiciona o vértice à fila
            used[to] = True             # marca o vértice como visitado
Primeiro, inicializamos o grafo e começamos a varredura a partir do vértice start. Inicialmente, todos os valores em used estão como False. Ao visitar cada vértice, adicionamos esse vértice na fila e marcamos como visitado. Isso simula a “queima” do grafo. A cada passo, inserimos na fila todos os vértices vizinhos de v que ainda não foram visitados, marcando-os como visitados.
Vamos simular o algoritmo em alguns casos:
n = 4, e = 4
Os pares de entrada a, b são: [(0, 1), (0, 2), (1, 2), (3, 2)]
O vértice inicial é 3
  1. used = [False, False, False, True], q = [3]
  1. v = 3, q = [] → adicionar todos os vizinhos não visitados à fila
  1. used = [False, False, True, True], q = [2]
  1. v = 2, q = [] → adicionar todos os vizinhos não visitados à fila
  1. used = [True, True, True, True], q = [0, 1]
  1. v = 0, q = [1] → adicionar todos os vizinhos não visitados à fila
  1. v = 1, q = [] → adicionar todos os vizinhos não visitados à fila
  1. Fim
n = 5, e = 4
Os pares de entrada a, b são: [(0, 1), (0, 2), (1, 2), (3, 4)]
O vértice inicial é 0
  1. used = [True, False, False, False, False], q = [0]
  1. v = 0, q = [] → adicionar todos os vizinhos não visitados à fila
  1. used = [True, True, True, False, False], q = [1, 2]
  1. v = 1, q = [2] → adicionar todos os vizinhos não visitados à fila
  1. v = 2, q = [] → adicionar todos os vizinhos não visitados à fila
  1. Fim
      2. Notice how nodes 3 and 4 were never visited.
      They were not connected to the initial node 0.

Desafio: Contar o Número de Componentes Conectados em um Grafo

Dado um grafo não direcionado com v vértices e e arestas, você precisa calcular o número de componentes conectados nesse grafo. Um conjunto de vértices é considerado uma componente conectada se for possível viajar entre qualquer par de 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 e linhas seguintes contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está conectado ao vértice v2 e vice-versa.

Saída

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

Exemplos

Input
Input
7 6 1 2 2 3 1 3 4 5 5 6 4 6
3
2 1 1 2
1
2 0
2
 

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue