Mam problem z wymyśleniem fajnego (== szybkiego) algorytmu badającego spójność w grafie.
Ale nie chodzi tu o to, żeby po prostu dla danego grafu sprawdzić, czy jest spójny...
Mam jakiś algorytm, który z jednego grafu ma utworzyć inny, nieważne w jaki sposób. Algorytm, który tworzy graf, mam już wymyślony i jest ok. Ale muszę go przerwać, gdy utworzony graf będzie spójny (ale nie musi być drzewem - mogą być cykle, krawędzie wielokrotne itd., w sumie nieważne). Potrzebuję więc jakiegoś sposobu na sprawdzenie, czy powstały graf jest już spójny - ale muszę to sprawdzać po dodaniu każdej kolejnej krawędzi do niego. Dane wejściowe to lista krawędzi.
Pewnie dobrym pomysłem jest utworzenie macierzy sąsiedztwa (czy raczej nie sąsiedztwa, ale "istnienia ścieżek" między wierzchołkami) i sprawdzanie, czy z któregośtam wierzchołka da się jakoś dojść do wszystkich innych. Ale takie rozwiązanie niestety nie jest możliwe przez ograniczenia pamięciowe.
Jedyne, co do tej pory wymyśliłam, to utworzenie grup wierzchołków (w sensie - spójnych składowych). Tzn. mam jakąś tablicę g[n] z numerami grup, tzn. g[i] to numer grupy, do której należy i-ty wierzchołek. I gdy dodaję krawędź (v1, v2) do grafu, to wszystkim wierzchołkom z numerem grupy g[v1] zmieniam ten numer na g[v2], tzn. łączę te grupy. Następnie sprawdzam, czy już wszystkie wierzchołki mają taki sam numer grupy. To oczywiście działające, ale bardzo słabe rozwiązanie, przede wszystkim zbyt wolne...
Ma ktoś może pomysł na zrobienie tego jakoś sprytniej?
Z góry dziękuję za pomoc. :)