Vizualizare sursă pentru „0019 - BFS”

== Enunț ==
Se consideră un graf neorientat cu <code>n</code> vârfuri și <code>m</code> muchii și de asemenea un vârf <code>X</code>.

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

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

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

= Restricţii şi precizări =

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

= Exemplul 1 =
<code>BFSIN.txt</code>
 5 7 2
 1 2
 3 2
 1 5
 2 4
 3 1
 4 5
 5 3 
<code>BFSOUT.txt</code>
 2 1 3 4 5 

= Exemplul 2 =
<code>BFSIN.txt</code>
 1 1 1
<code>BFSOUT.txt</code>
 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>