Comprimento do Caminho Mais Curto com BFS
O algoritmo BFS começa em um nó e expande-se gradualmente para os seus vizinhos, permitindo encontrar o caminho mais curto desde o nó inicial até todos os outros nós do grafo. Para isso, precisamos fazer uma pequena modificação no algoritmo original. Usaremos um array de distâncias
d, onde todos os valores são inicialmente -1. Se o valor de um vértice for -1, isso significa que o vértice ainda não foi visitado. Se o valor for positivo, esse valor representa a distância do vértice atual em relação ao ponto de partida:from collections import deque
n, e = map(int, input().split()) # n: vértices, e: arestas
g = [[] for _ in range(n)] # grafo - lista de adjacência
for _ in range(e): # ler 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 de início
d = [-1] * n # distância a partir do vértice inicial
q = deque([start]) # fila de vértices
d[start] = 0 # a distância do vértice inicial para si próprio é 0
while q: # enquanto a fila não estiver vazia
v = q.popleft() # retirar vértice da fila
print(v, end=' ') # imprimir vértice
for to in g[v]: # para cada vértice ligado a v
if d[to] == -1: # se o vértice ainda não foi visitado
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
q.append(to) # adicionar o vértice à fila
print(d)Primeiro, inicializamos o array de distâncias
d definindo todos os valores como -1, sinalizando que nenhum dos vértices foi usado ainda. Em seguida, definimos d[start] como 0, o que indica que a distância do vértice start até ele mesmo é 0.À medida que o algoritmo processa mais vértices, seus valores correspondentes são atualizados no array de distâncias
d, resultando em todas as distâncias calculadas a partir do vértice start até os demais vértices.Vamos simular o algoritmo com algumas entradas:
n = 4, e = 4
Os pares
a, b de entrada são: [(0, 1), (0, 2), (1, 2), (3, 2)]O vértice inicial é 3
d = [-1, -1, -1, 0],q = [3]
v = 3,q = []→ adicione todos os vizinhos que ainda não foram usados à fila
d = [-1, -1, 1, 0],q = [2]
v = 2,q = []→ adicione todos os vizinhos que ainda não foram usados à fila
d = [2, 2, 1, 0],q = [0, 1]
v = 0,q = [1]→ adicione todos os vizinhos que ainda não foram usados à fila
v = 1,q = []→ adicione todos os vizinhos que ainda não foram usados à fila
- Concluído
n = 5, e = 4
Os pares
a, b de entrada são: [(0, 1), (0, 2), (1, 2), (3, 4)]O vértice inicial é 0
d = [0, -1, -1, -1, -1],q = [0]
v = 0,q = []→ adicione todos os vizinhos que ainda não foram usados à fila
d = [0, 1, 1, -1, -1],q = [1, 2]
v = 1,q = [2]→ adicione todos os vizinhos que ainda não foram usados à fila
v = 2,q = []→ adicione todos os vizinhos que ainda não foram usados à fila
- Concluído
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Desafio: Encontrar o Comprimento do Caminho Mais Curto
Dado um grafo não direcionado com
v vértices e e arestas, você deve calcular o caminho mais curto entre o vértice 1 e o vértice v. Caso não exista conexão entre eles, o programa deve imprimir Impossible.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 comprimento do caminho mais curto entre
1 e v.Exemplos
Entrada | Saída |
5 6
1 2
2 3
1 3
3 4
4 3
3 5 | 2 |
2 1
1 2 | 1 |
2 0 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB