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

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()