Simina: Pagină nouă: == 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 n...

2023-12-12T23:36:42Z

Pagină nouă: == 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 n...

New page

== 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>

0019 - BFS - Revision history