Один из моих методов в Java переходит в матрицу смежности сПроверить циклы в матрице смежности?
1 значений в матрице, указывающие на связь, и0 значений что указывает на отсутствие соединения.Моя матрица смежности представляет собой ненаправленный график.
Как проверить, имеет ли моя матрица смежности какие-либо циклы или нет?
Существует два хороших решения:
начинают перемещаться (BFS, поиск в глубину, ...) ваш график, если вы посетили узел дважды есть цикл в вашем графике.
, следовательно, у вас есть матрица смежности, то вы могли бы использовать алгоритм, который Имран упоминается в комментариях, вам просто нужно вычислить п, при п = 1, .... и проверить, если есть ненулевой диагональный или нет, и я думаю, что ваш учитель хочет этот алгоритм.
Просто Google adjacency matrix properties и вы найдете статьи, как this.
Итак, если обход DFS посещает ЛЮБОЙ элемент в матрице смежности дважды, то есть цикл? – Vimzy
@ Vimzy, если он посещает ЛЮБОЙ Узел дважды, есть цикл. но, как я сказал, лучше использовать второй подход – Lrrr
Я не совсем понимаю, что второй подход должен быть честным. Как вычислить A^n и как я могу проверить, нет ли нулевой диагональной записи или нет? – Vimzy
Посмотрите на [Обнаружение цикла] (http://en.wikipedia.org/wiki/Cycle_ (graph_theory) #Cycle_detection). – Th3Cuber
Кто-нибудь знает, как это сделать? Даже pseduocode? Я проделал много поисков и кавычек Google, но ничего не нашел. – Vimzy
Взгляните на этот ответ: http://stackoverflow.com/a/25537032/58866 – Imran