ma ktoś jakiś prosty program do znajdowania mostów w grafie znalazłem już parę takich programów ale ich nie rozumiem a jeśli ktoś poda taki kod to proszę od razu zaznaczyć funkcje low bo chciałbym ja wykorzystać do znajdowania punktu artykulacji
0
0
A można ciut składniej? Jakie mosty? Jaka funkcja low? Jaki punkt artykulacji? Nie wszyscy słyszeli o takich pojęciach...
0
Mosty krawędzie które po usunięciu dzielą graf na dwie silnie spójne grafowe a punkt artykulacji to to samo tylko dotyczy wierzchołka. Funkcja low to funkcja która znajduje mosty itp.
ten artykuł jest dla mnie za trudny i jeszcze ten pseudo kod
czy umie ktoś to prościej wytłumaczyć
Bardzo ważną i przydatną rzeczą w poniższych algorytmach jest funkcja (tablica) Low. Właściwie to "wyliczenie" jej załatwia natychmiastowo problem znajdowania mostów i punktów artykulacji (z dwuspójnymi składowymi trza się będzie jeszcze trochę pomęczyć).
Znajdowanie Low opiera się na przeszukiwaniu w głąb. Niezbędna będzie numeracja pre-order, więc przyjmijmy, że D[v] będzie oznaczać numerek w tej numeracji wierzchołka v.
Zatem konkretniej. Przypuśćmy, że zapuściliśmy DFSa i doszliśmy do wierzchołka v. Żeby obliczyć Low dla niego to musimy rozpatrzyć pewne wartości dla sąsiadujących z nim wierzchołków w: Low[w] jeżeli wierzchołka w jeszcze nie odwiedziliśmy naszym DFSem, D[w] jeżeli wierzchołek w już odwiedziliśmy, ale (!!!) nie przeszliśmy bezpośrednio z niego w DFSie do v (czyli w nie jest ojcem v w drzewie przeszukiwania w głąb). Teraz jedynie bierzemy najmniejszą z powyższych wartości i z samego D[v] i to właśnie ona jest szukaną wartością Low[v].
Ta w miarę formalna definicja może nie być do końca jasna, więc już tłumaczę. Jeżeli od wierzchołka v jesteśmy w stanie dojść do już odwiedzonego wierzchołka u inną drogą niż tą którą doszliśmy z u do v w naszym DFSie, to bierzemy pod uwagę wartość D[u]. I najmniejsza z tych wartości to właśnie Low[v]. Chyba, że z v nie można dojść do żadnego odwiedzonego wcześniej wierzchołka, to wtedy Low[v]=D[v].
0
To w takim razie obejrzyj to:
http://was.zaa.mimuw.edu.pl/?q=node/39