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

Pomoc oko funcije u C++ da li u grafu postoje ciklusi???!!!!

[es] :: C/C++ programiranje :: C/C++ za početnike :: Pomoc oko funcije u C++ da li u grafu postoje ciklusi???!!!!

[ Pregleda: 2226 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

m_antic87
student
Nis

Član broj: 198581
Poruke: 16
*.sc.ni.ac.yu.



Profil

icon Pomoc oko funcije u C++ da li u grafu postoje ciklusi???!!!!23.10.2008. u 15:40 - pre 188 meseci
Da,znam da je ovo za nekog maciji kasalj,ali meni ovo predstavlja veliki ptoblem.Zato bih zamolio ljude koji poznaju ovu materiju da mi pomognu oko sledeceg zadatka: naime,potrebna mi je f-ja 'bool is Cyclic' koja proverava da li graf koji je predstavljen a) preko matrice susedstva, b) preko lancane liste,tj. liste susedstva ima cikluse u sebi!Hitnije mi je b),jer sa a) sam nesto smuckao!Unapred zahvalan
 
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: Pomoc oko funcije u C++ da li u grafu postoje ciklusi???!!!!09.11.2008. u 11:10 - pre 188 meseci
Opšte rešenje ti je obilazak grafa dubinski ili po širini (dakle tako da kreneš od jednog čvora pa nikad ne prođeš dvaput kroz istu granu). Ako se ovim postupkom ne desi da dođeš do čvora kroz koga si već prošao, onda nema ciklusa. U suprotnom možeš reći da graf ima (najmanje jedan) ciklus čim dva puta do pronađeš jedan te isti čvor.

A sad, šta mu dođe lista susedstva: Lista koja za svaki čvor sadrži listu susednih čvorova? Ništa lakše, milina za pretraživanje po širini (BFS).
Ipak se ++uje.
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Pomoc oko funcije u C++ da li u grafu postoje ciklusi???!!!!

[ Pregleda: 2226 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

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