Module: BFS - Caminhada em Largura


Problem

2/6

BFS: Começo (Python)

Theory Click to read/hide

BFS (breadth-first search) é um método de travessia de grafos, muito usado em algoritmos simples e avançados. A busca em largura funciona percorrendo os níveis individuais do gráfico, começando no nó de origem e gradualmente se afastando dele. Isso fica claro na animação.

Para escrever um BFS simples, você precisa ser capaz de trabalhar com uma fila, uma estrutura de dados que permite pegar do início e colocá-la no final, e também ser capaz de armazenar um gráfico no formulário de uma lista de adjacências.
 
Descrição formal do algoritmo
1) Coloque o número do vértice a partir do qual a busca começa na fila inicialmente vazia.
2) Extraia o vértice U do início da fila e marque-o como usado em um array separado.
3) No final da fila, adicione todos os vértices que podemos alcançar usando a aresta do vértice U e que ainda não estão marcados.
4) Se a fila estiver vazia, todos os nós do grafo conectado foram verificados, caso contrário, retorne ao passo 2.
 
Dificuldade de trabalho
Como, no pior caso, o algoritmo visita todos os nós do grafo, ao armazenar o grafo na forma de listas de adjacências, a complexidade de tempo do algoritmo é O(|V| + |E|), onde V é o conjunto de vértices do grafo, e E é o conjunto de arestas.  ;
Em outras palavras, o algoritmo funciona no pior caso para o número de arestas + o número de vértices.

 

Problem

Algumas aldeias são conectadas por estradas, que podem ser representadas como um gráfico não direcionado. Os vértices deste grafo são aldeias e as arestas são estradas entre aldeias (o grafo pode conter ciclos). Sabe-se que na aldeia S um artel Vagadistas. Todas as manhãs, para venderem os seus pequenos armarinhos, os mascates dirigem-se a aldeias que ainda não visitaram, e para as quais existe uma estrada a partir da atual. O artel dos mascates está sempre dividido em grupos para que possam percorrer num dia todas as aldeias que têm estradas a partir da actual.
Em quantos dias os mascates visitarão todas as aldeias? Escreva uma função \(bfs()\) que retornará a resposta para o problema.


Entrada
A primeira linha contém 3 inteiros n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - o número de aldeias, o número de estradas entre elas e o número da aldeia em que se baseia a quadrilha do mascate.  ;Nos seguintes m< /code> as linhas contêm 2 números cada u, v(\(1 < = u, v <= n\ )) - números de duas aldeias entre as quais existe uma estrada. As aldeias são indexadas com 1.

Impressão
Imprima um único número - quantos dias os mascates levarão para visitar todas as aldeias.
 
 
Exemplos
# Entrada Saída
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
def bfs():            
n, m, s = map(int, input().split())
s -= 1
used = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())

     

Program check result

To check the solution of the problem, you need to register or log in!