Pripreme za algoritme(15)

Danas ćemo proći BFS i još nešto vezano uz grafove što vrijedi napomenuti.

BFS

Ovaj način obilaska obično koristimo kod širenja po nekom prostoru npr. labirintu.

1. Obiđemo sve čvorove koji su povezani s početnim
2. U drugom krugu krećemo od posjećenih čvorova i posjećujemo one koji su ispod njih.

Redoslijed obilaska za graf prikazan slikom:
1 do 2, 1 do 3, 3 do 5, 3 do 6, 5 do 4, 6 do 7, 7 do 8

BFS - kod

 

Prikaz grafa matricom

Obično graf prikazujemo matricom u kojoj element[x,y] i element[y,x] ima vrijednost 1 ili True ako su čvorovi x i y povezani.

Za gornji primjer matrica susjedstva je:

 Evo toliko od nas za danas. I u sljedećoj lekciji se bavimo grafovima.