[ m_antic87 @ 23.10.2008. 15:40 ] @
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
[ Mali Misha @ 09.11.2008. 11:10 ] @
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).