Ориентированный граф. найти циклы.
найти все циклы или выяснить существование?
алгоритм Флойда Уоршолла. 
for m 1..n
for i 1..n
for j 1..n
if a[i, m] and a[m, j] then a[i, j] := true
после этого если a[i, i] = true то эта вершина в цикле
можно в эту же матрицу m складывать, тогда и цикл можно узнать.
блин, в обоих фамилиях ошибся
for m 1..n
for i 1..n
for j 1..n
if a[i, m] and a[m, j] then a[i, j] := true
после этого если a[i, i] = true то эта вершина в цикле
можно в эту же матрицу m складывать, тогда и цикл можно узнать.
блин, в обоих фамилиях ошибся
после этого если a[i, i] = true то эта вершина в циклеа если a[i, i] == false, то не в цикле.
Красота!
Найти все максимальные циклы.
А что ты найдешь этим перебором? и зачем портить начальную матрицу? что такое вершина в Цикле?
Цикл - из лбой вершины цикла можно попасть в любую другую вершину цикла
Цикл - из лбой вершины цикла можно попасть в любую другую вершину цикла
А что ты найдешь этим перебором? и зачем портить начальную матрицу? что такое вершина в Цикле?A может быть не самой матрицей смежности, а ее дубликатом. После выполнения этого алгоритма она превращается в матрицу достижимости: A[i,j] = "Из i можно попасть в j". Если A[i,i], то, очевидно, вершина i принадлежит какому-то циклу, а то и не одному.
Найти все максимальные циклы.--- таким способом не получится. Имеется в виду простой цикл, т.е. без повторений вершин, кроме первой и последней, я правильно понял?
Я думаю, можно найти их с помощью какой-то модификации поиска в глубину. Что-то подобное, ИМХО, делалось в Кормене, в главе про графы. Если надо, могу попробовать додумать до конца
> Как это сделать помогите
Открыть книжку: алгоритмы на графах, и не изобретать велосипед?
Открыть книжку: алгоритмы на графах, и не изобретать велосипед?
Буду очень Благодарен.
2 DarkGrey
Послать куда нибудь(хоть бы путь указал куда ) всегда легко, а вот дать толковый совет - это уж другое дело
2 DarkGrey
Открыть книжку: алгоритмы на графах, и не изобретать велосипед?Где ее взять, мб ссылку дашь какую-нибудь?
Послать куда нибудь(хоть бы путь указал куда
) всегда легко, а вот дать толковый совет - это уж другое делоПосле некоторых раздумий я понял, что был неправ. Нельзя искать циклы никакой модификацией поиска в глубину, а надо это делать только перебором.
Потому что, если в графе есть гамильтонов цикл, то таким алгоритмом он найдется как самый длинный, а задача поиска гамильтонова цикла - NP-полная.
Так что можно с чистым сердцем писать полный перебор, например, рекурсивный.
Потому что, если в графе есть гамильтонов цикл, то таким алгоритмом он найдется как самый длинный, а задача поиска гамильтонова цикла - NP-полная.
Так что можно с чистым сердцем писать полный перебор, например, рекурсивный.
Могу дать книжку, где про это написано. Не уверен, что хорошая - сам не читал. Нужна?
http://jgrapht.sourceforge.net/
JGraphT is a free Java graph library that provides mathematical graph-theory objects and algorithms. JGraphT supports various types of graphs including:
* directed and undirected graphs.
* graphs with weighted / unweighted / labeled or any user-defined edges.
* various edge multiplicity options, including: simple-graphs, multigraphs, pseudographs.
* unmodifiable graphs - allow modules to provide "read-only" access to internal graphs.
* listenable graphs - allow external listeners to track modification events.
* subgraphs graphs that are auto-updating subgraph views on other graphs.
* all compositions of above graphs.
Пацаны обещают, что будет просто.
JGraphT is a free Java graph library that provides mathematical graph-theory objects and algorithms. JGraphT supports various types of graphs including:
* directed and undirected graphs.
* graphs with weighted / unweighted / labeled or any user-defined edges.
* various edge multiplicity options, including: simple-graphs, multigraphs, pseudographs.
* unmodifiable graphs - allow modules to provide "read-only" access to internal graphs.
* listenable graphs - allow external listeners to track modification events.
* subgraphs graphs that are auto-updating subgraph views on other graphs.
* all compositions of above graphs.
Пацаны обещают, что будет просто.
Попробуй здесь глянуть.
http://www.gtl.kis.ru/content.htm
Это библиотека графов, по типу stl. Там коего-чего есть по циклам. Есть исходники кое-какие описания и ссылки на литератру. Написана на с++.
Правда она не развивается с 98 года.
http://www.gtl.kis.ru/content.htm
Это библиотека графов, по типу stl. Там коего-чего есть по циклам. Есть исходники кое-какие описания и ссылки на литератру. Написана на с++.
Правда она не развивается с 98 года.
Оставить комментарий
grnat
Ориентированный граф Сохранен в виде матрицы, дуги это 1. Нужно найти циклы в этом графе, Как это сделать помогите