PozwolićA być macierzą sąsiedztwa dla wykresuG = (V,E). A(i,j) = 1 jeśli węzłyi ij są połączone krawędzią,A(i,j) = 0 Inaczej.

Moim celem jest zrozumienie, czyG jest acykliczny lub nie. Cykl definiuje się w następujący sposób:

i ij są połączone:A(i,j) = 1j ik są połączone:A(j,k) = 1k ii są połączone:A(k,i) = 1

Zaimplementowałem rozwiązanie, które nawiguje po macierzy w następujący sposób:

Zacznij od krawędzi(i,j)Wybierz zestawO krawędzi wychodzących zj, tj. wszystkie 1s wj-ty rządANawigowaćO w sposób DFSJeśli jedna ze ścieżek wygenerowanych z tej nawigacji prowadzi do węzłai, a następnie wykrywany jest cykl

Oczywiście to rozwiązanie jest bardzo powolne, ponieważ muszę ocenić wszystkie ścieżki w macierzy. JeśliA jest bardzo duży, wymagany nakład jest bardzo duży. Zastanawiałem się, czy istnieje sposób nawigowania po macierzy sąsiedztwa, aby znaleźć cykle bez użycia drogiego algorytmu, takiego jak DFS.

Chciałbym wdrożyć moje rozwiązanie w MATLAB.

Z góry dziękuję,

Eleanore.