0019 - BFS

Enunț

Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X.

Cerinţa

Să se afișeze vârfurile vizitate în urma parcurgerii în lățime (Breadth First Search) a grafului, pornind din vârful X.

Date de intrare

Fişierul de intrare BFSIN.txt conţine pe prima linie trei numere naturale n m X, având următoarea semnificație: n este numărul de noduri, m este numărul de muchii din graf, iar X este vârful din care se începe parcurgerea. Următoarele m linii conțin câte două numere x y cu semnificația că există muchie între x și y .

Date de ieşire

Fişierul de ieşire BFSOUT.txt va conţine pe prima linie vârfurile vizitate în urma parcurgerii în lățime a grafului, aceasta începând din vârful X.

Restricţii şi precizări

• 2 ≤ n ≤ 100
• 1 ≤ m ≤ n*(n-1)/2
• Graful poate sa nu fie conex!!!
• dacă în timpul parcurgerii, la un moment dat vârful curent al grafului este Y, vecinii nevizitați ai lui Y se vor analiza în ordine crescătoare.

Exemplul 1

BFSIN.txt

5 7 2
1 2
3 2
1 5
2 4
3 1
4 5
5 3 

BFSOUT.txt

2 1 3 4 5 

Exemplul 2

BFSIN.txt

1 1 1

BFSOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> from collections import deque

def bfs(graf, start):

   vizitate = set()
   rezultat = []

   coada = deque([start])
   vizitate.add(start)

   while coada:
       nod_curent = coada.popleft()
       rezultat.append(nod_curent)

       for vecin in sorted(graf[nod_curent]):
           if vecin not in vizitate:
               coada.append(vecin)
               vizitate.add(vecin)

   return rezultat

def citeste_graf(input_file):

   with open(input_file, 'r') as f:
       n, m, start = map(int, f.readline().split())

       # Verificăm restricțiile
       if not (2 <= n <= 100 and 1 <= m <= n * (n - 1) / 2):
           with open('BFSOUT.txt', 'w') as fout:
               fout.write("Datele nu corespund restrictiilor impuse")
           return None, None

       graf = {i: set() for i in range(1, n + 1)}

       for _ in range(m):
           x, y = map(int, f.readline().split())
           graf[x].add(y)
           graf[y].add(x)

   return graf, start

def main():

   input_file = 'BFSIN.txt'
   output_file = 'BFSOUT.txt'

   graf, start = citeste_graf(input_file)

   # Dacă restricțiile nu sunt respectate, nu continuăm cu parcurgerea și afișăm mesajul în fișierul de ieșire
   if graf is not None and start is not None:
       rezultat = bfs(graf, start)

       with open(output_file, 'w') as f:
           f.write(' '.join(map(str, rezultat)))

if __name__ == "__main__":

   main()

</syntaxhighlight>