Witam,
Mam graf nieskierowany zaimplementowany w postaci listy incydencji. Muszę zrobić tak, że jeżeli da się utworzyć z trzech danych wierzchołków cykl 3 elementowy to go towrzę. Załóżmy, że:
1: 2 3
2: 1 3
3: 1 2 4
4: 3 4
5: 4
No i zauważam, że jedynka sąsiaduje z trójką, a trójka z czwórką lecz jedynka z czwórką nie - dodaje krawędź łączącą 1 z 4 i otrzymuje cykl 3 elementowy. Da się rozwiązać ten problem przynajmniej przy złożoności liniowo/logarytmicznej? Ktoś doradzi jak najlepiej rozwiązać to, aby działało szybko? Myślałem nad algorytmami przeszukiwania grafu wszerz bądź w głąb. Algorytm DFS pozwala na znajdywanie cyklu ale jak go przekształcić, aby tworzył cykl? Mam taki pomysł, że Przechodzę DFS lub BFS i sprawdzam tak: dla przykładu zaczynam w wierzchołku A, sprawdzam jego sąsiada który zwie się B, a następnie sprawdzam sąsiadów wierzchołka B i porównuje z sąsiadami wierzchołka A jeżeli dany sąsiad jest sąsiadem wierzchołka B, ale nie jest sąsiadem wierzchołka A to mogę poprowadzić krawędź i zostanie utworzony cykl trzy elementowy. Nie wiem czy dobrze myślę, ale ogólnie to chyba będzie bardzo duża złożoność, bo mogę mieć n wierzchołków w grafie gdzie n <= 1000000, więc takie kombinacje sprawdzać dla wszystkich wierzchołków to olbrzymia złożoność wyjdzie chyba. Ogólnie to muszę tylko tworzyć takie cykle 3 elementowe, że mogę tworzyć krawędzie jakby "dziadka z wnuczkiem", jeżeli dwóch synów dziadka nie ma krawędzi to między synami nie mogę utworzyć krawędzi.