#1 27. 05. 2009 22:08
graf v c#
Ahoj, potreboval by som s tymto pomoct
potrebujem spravit v c# program, ktory najde silne suvisle komponenty v grafe
neviem ako mam presne reprezentovat graf, potrebujem nanho pustit DFS, najlepsie by asi bolo ho reprezentovat pomocou zoznamu susedov, no ale tu je ten problem :)
mohol by mi niekto ukazat, ako naprogramovat graf, aby som s nim neskor mohol lahko pracovat? :)
vopred dakujem
Offline
#2 27. 05. 2009 23:55
Re: graf v c#
↑ Downey:
Programovat ti to nebudu :) ale jestli chceš vědět jak nejjednodušejc udělat graf tak normálně ve dvojrozměrnym poli...
Ve sloupcích budeš mít všechny uzly, v řádcích budeš mít všechny uzly a tam kde jsou ty uzly spojený si do toho pole něco poznačíš. Takže třeba když je mezi uzlama 5 a 3 hrana tak na indexu [5][3] budeš mít nějakou značku. Samozřejmě jí budeš mít i na indexu [3][5] takže z toho vypadne něco jako symetrická matice...
Offline
#3 28. 05. 2009 00:16
- Lukee
- Administrátor
- Místo: Opava
- Příspěvky: 1866
- Škola: UPOL, Informatika
- Pozice: Roznašeč reklamních bannerů
- Web
Re: graf v c#
↑ xxsawer:
Myslíš matici sousednosti? :-) Matice sousednosti má své výhody a své nevýhody. Další způsob reprezentace je třeba dle definice: zapamatuješ si množinu uzlů a množinu hran. Zvaž sám, jaká reprezentace se ti bude více hodit.
2+2=4
Offline
#4 28. 05. 2009 00:26
Re: graf v c#
jj, vdaka za odpovede :), ale mam obmedzenu casovu zlozitost na O(m+n) takze myslim, ze uz pri zostavovani matice susednosti to nebude linearne (ak sa nemylim) a potrebujem cely graf prehladavat pomocou DFS.. lenze neviem si teraz asi ani predstavit, ako by to vyzeralo...nemyslim ciste kod :) asi preto, ze neviem ani ako mam ulozit graf :D
Offline
#5 28. 05. 2009 00:46
- Lukee
- Administrátor
- Místo: Opava
- Příspěvky: 1866
- Škola: UPOL, Informatika
- Pozice: Roznašeč reklamních bannerů
- Web
Re: graf v c#
↑ Downey:
http://kam.mff.cuni.cz/~kuba/ka/ka.pdf Kapitola 4 + 5 Je tam popsaná reprezentace včetně výhod a nevýhod a je tam popsán i algoritmus DFS, včetně pseudokódu. Snad to bude stačit.
2+2=4
Offline