| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > найти все циклы в графе определённой длины |
| Автор: mrgloom 8.2.2013, 14:07 |
| найти все простые циклы в неориентированном графе определённой длины http://sovietov.com/txt/triangle/triangle.html тут для циклов размером 3. для размера 4 будет уже 4 цикла for и т.д. может можно как то в общем виде написать? |
| Автор: baldina 8.2.2013, 15:01 |
| используй поиск в глубину с возвратом при достижении заданной длины. |
| Автор: mrgloom 8.2.2013, 17:24 |
| а как избежать повторов? т.е. я из одной вершины могу пойти по часовой и против часовой по циклу. всё равно из какой вершины начинать обход? |
| Автор: baldina 8.2.2013, 17:56 |
| если это поиск в глубину, повторов не будет: пройденные вершины помечаются |
| Автор: mrgloom 11.2.2013, 15:04 |
| мне оказывается надо найти элементарные циклы в графе. http://dl.dropbox.com/u/8841028/panorama/3_.PNG и опять же допустим имеем полный граф 4 вершины мы идем в глубину получаем последовательность 1-2-3-4 и получили 1 цикл и пометили все вершины, а на самом то деле там 5 циклов. |
| Автор: baldina 6.3.2013, 13:04 |
| http://forum.algolist.ru/algorithm-graph/915-nahojdenie-mnojestva-elementarnyh-tsiklov-grafa.html http://www.intuit.ru/department/algorithms/gaa/7/3.html |