@whatever73

Как найти все циклы в неориентированном графе по матрице смежности?

Здравствуйте. Есть произвольная матрица смежности для неориентированного графа.
Как найти кол-во циклов в этом графе?
  • Вопрос задан
  • 8728 просмотров
Пригласить эксперта
Ответы на вопрос 1
starius
@starius
программист, аспирант МГУ
Обходите граф в глубину. Стеком вершин назовем маршрут от начальной вершины до текущей вершины, по которому мы до неё добрались. Заведите множество вершин V, которые вы уже посетили. Для каждой вершины помните, из какой вершины вы в неё пришли (словарь P) при обходе. Если при обходе вы видите в числе соседей вершины уже посещённую вершину K, которая не входит в текущий стек вершин, то "разматывайте" путь от K до изначальной вершины, используя информацию из словаря P, это в совокупности со стеком вершин даст цикл. А если K входит в стек вершин, то циклом будет часть стека от K до вершины стека.

Дополнение не совсем в тему. Есть элегантный алгоритм, который для числа n определяет, входит ли вершина в цикл с повторами длины n. Но так как цикл с повторами, а граф неориентированный, то циклы вида A-B-A-B-A-... тожу будут учитываться. Видимо, можно придумать способ вычесть их количество из полученного числа циклов. Так я и собирался делать, но потом понял, что ничего этого не нужно и задача решается простым обходом в глубину.

UPD. Оказалось, что мой ответ неправильный. Правильные мысли описаны в научной статье.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы