ilość składowych spójnych grafu (program w C++)

neshenti · Post autor: **neshenti** » 7 cze 2006, o 14:19

Czy ktoś może umie napisac program w C++ liczący ilość składowych spójnych grafu?
Chodzi o to aby program wyświetlał na wyjściu, z ilu "części" składa się graf, tzn takich które nie są połączone ze sobą, taki prosty przykład to:
// , / , /, /// to są grafy spójne (jednospójne) a to np: / / , / , /// / są grafy dwuspójne, to: / // , / / / 3-spójne itd ... I na podstawie wpisanej macierzy sąsiedztwa (wpisuje 1 gdy wierzchołki łączą się ze sobą, a 0 gdy się nie łączą) program ma podawać mi ilość tych składowych spoójnych danego grafu ...
Czy ktoś wie jak to napisać w C++???

marshal · Post autor: **marshal** » 7 cze 2006, o 23:53

algorytm w skrocie...
lecisz kolejno po wierzcholkach i zapodajesz dla kazdego odwiedzanie wierzcholkow po grafie
jak odwiedzisz jakis wezel to dajesz mu status odwiedzony
jezli juz jakis wezel odwiedziles to go olewasz i przechodzisz do nastepnego. w ten sposob wykminisz wszystkie spojne grafy

teraze clue programu
graf sobie implementujesz np za pomoca listy (wezly i sciezki)
do tego sobie robisz liste wezlow (nie oddajaca grafu)

i lecisz po tej liscie wezlow - jezeli przy pierwszym wezle odwiedzisz wszystkie to graf jest jednospojny - jezeli bedziesz musial zapoda przegladanie dla dwoch wezlow to dwuspojny itd.

matkow865 · Post autor: **matkow865** » 14 sty 2008, o 11:36

Czy ktoś może napisac i przesłać mi program w C++ lub javie program liczący liczbę spójnych składowych grafu?
A może chociaż link do stronki z gotowcem. PLIS bardzo potrzebuję tego małego programiku a jestem totalnie niezorientowany jeśli chodzi o sprawy informatyczne a dokładnie programowanie.

Mój adres e-mail to matkow865@wp.pl.

Z góry Dziękuję za poświęcony czas.

Pozdrawiam