| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > найти все связные подграфы |
| Автор: mrgloom 11.2.2013, 15:14 |
| Необходимо найти все связные подграфы графа. как это делается? убирается по 1 ребру и проверяется на связность? |
| Автор: Фантом 11.2.2013, 16:11 |
| Вы уверены, что нужно найти именно все? А не максимально возможные? А то ведь даже в графе- "треугольнике" из трех попарно связанных вершин искомых подграфов будет 7, а при большем числе вершин для большинства графов рост будет факториальным. |
| Автор: mrgloom 11.2.2013, 16:23 |
| да, это я и имел ввиду, что все максимальные подграфы которые включают все вершины исходного графа. |
| Автор: Фантом 11.2.2013, 16:31 |
| Тогда схема действий такая. 1) Берем какую-то одну вершину графа и добавляем ее в список. 2) Выясняем, какие вершины связаны с ней, добавляем их в тот же список. 3) Для каждой из добавленных в п.2. вершин повторяем ту же процедуру, начиная с п.1. Если новые вершины не обнаруживаются - мы выделили один максимальный подграф. 4) Выкидываем все вершины выделенного подграфа из рассмотрения, берем какую-то вершину графа из оставшихся и снова повторяем все, начиная с п.1. Если вершин графа не осталось - работа закончена, все подграфы выделены. |
| Автор: mrgloom 11.2.2013, 17:32 |
| вы не поняли, там 1 связный подграф должен быть, просто разное кол-во рёбер. |
| Автор: Фантом 11.2.2013, 18:18 | ||
Т.е. надо найти минимальное охватывающее дерево? М-да, с терминологией у Вас все как-то совсем печально. Давайте-ка сделаем так. Перепишите сюда условие задачи, которую Вы пытаетесь решить, дословно. Без сокращений и прочей отсебятины. А там посмотрим, что именно Вам на самом деле нужно. |
| Автор: mrgloom 12.2.2013, 09:02 |
| да, с графами я пока что не работал. http://forum.vingrad.ru/forum/topic-361629.html вот тут я пытаюсь сшить панораму. в начале получается или полный граф (или чтобы облегчить задачу, можно некоторые связи выкинуть обрезав по порогу). затем я хочу найти подграфы как я описал выше. и как раз мне надо не минимальное охватывающее дерево, а все варианты подграфов содержащие все вершины и имеющие связность. затем я планирую каждый граф проверить на геометрические коллизии и затем посчитать сумму корреляций\ кол-во связей и выбрать лучший вариант. |
| Автор: Фантом 12.2.2013, 09:49 | ||
Прочитал. Ничего не понял (кроме того, что писал Akina). По-видимому, Вам следует прочитать то, что он написал, и реализовать. |
| Автор: mrgloom 12.2.2013, 10:40 |
| это всё таки называется остов(http://en.wikipedia.org/wiki/Spanning_tree), т.е. задача как найти все остовы в графе. т.е. должны быть охвачены все вершины и не должно быть циклов. |
| Автор: mrgloom 17.5.2013, 11:09 |
| и (если это будет быстрее) то задачу можно поставить как найти лучшие k остовов в графе. |
| Автор: mrgloom 17.5.2013, 12:13 |
| http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/random_spanning_tree.html есть вариант брать несколько раз рэндомно, только непонятно данная реализация будет давать повторы или нет? |
