Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

BFS - obilazak grafa po sirini

[es] :: Art of Programming :: BFS - obilazak grafa po sirini

[ Pregleda: 4870 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

rizbo_sl
rizbo_sl
student
Republika Srpska

Član broj: 209322
Poruke: 7
*.team.ba.



+1 Profil

icon BFS - obilazak grafa po sirini27.01.2009. u 20:55 - pre 185 meseci
Da li neko zna kako se ovaj graf obilazi po sirini?
Pa da mi napise redoslijed posjecenih cvorova ako se podje od cvora 2.


.................( 2 )<------( 4 )----->( 5 )
.................../\ \............|........../|.|
...................|....\..........|........./...|
...................|......\........|......./.....|
...................|........\......|...../.......|
...................|..........\....|.../.........|
...................|...........\|.\/./..........\/
................ ( 1 )..........( 3 ).........( 6 )
So close no matter how far...
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
78.90.101.*

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: BFS - obilazak grafa po sirini27.01.2009. u 21:11 - pre 185 meseci
Umesto da ti dam rešenje, zašto da ne probaš da ga sam napišeš? Evo malo pomoći:

Obilazak po širini će prvo obići sve čvorove na dubini 1 u odnosu na polazni čvor. To je (2).
Potom će obići sve čvorove na dubini 2 u odnosu na polazni čvor. To je samo (3) u ovom slučaju.
Potom sve čvorove na dubini 1 u odnosu na sve čvorove prisutne u prethodnom koraku. U ovom slučaju je to samo (5), na dubini 1 u odnosu na (3).

Treba li da se pominje da ponavljanja ne treba da bude?

Graf nije predobar primer za dubinsku pretragu, jer je usmeren. Da nije usmeren, bilo bi više dostupnih čvorova po prolazu. Npr. na dubini 1 od (2) bi to bili: (1), (3) i (4).
Ipak se ++uje.
 
Odgovor na temu

rizbo_sl
rizbo_sl
student
Republika Srpska

Član broj: 209322
Poruke: 7
*.team.ba.



+1 Profil

icon Re: BFS - obilazak grafa po sirini27.01.2009. u 21:32 - pre 185 meseci
Kada se krene od cvora 2 prvo bi se posjetio cvor 2 pa cvor 3, 5 pa 6.

Je li ovako?

Cini mi se da ovo bas i nije dobar primjer ni za bfs.
So close no matter how far...
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
78.90.101.*

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: BFS - obilazak grafa po sirini27.01.2009. u 21:45 - pre 185 meseci
Citat:
rizbo_sl: Kada se krene od cvora 2 prvo bi se posjetio cvor 2 pa cvor 3, 5 pa 6.

To je već obilazak po dubini. Ali da, to je kompletno rešenje za tu varijantu, ukoliko se poštuje usmerenost grafa.
Ipak se ++uje.
 
Odgovor na temu

[es] :: Art of Programming :: BFS - obilazak grafa po sirini

[ Pregleda: 4870 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.