Необходимо найти все связные подграфы графа.

как это делается? убирается по 1 ребру и проверяется на связность?

Это сообщение отредактировал(а) mrgloom - 11.2.2013, 15:20

Вы уверены, что нужно найти именно все? А не максимально возможные? А то ведь даже в графе- "треугольнике" из трех попарно связанных вершин искомых подграфов будет 7, а при большем числе вершин для большинства графов рост будет факториальным.

да, это я и имел ввиду, что все максимальные подграфы которые включают все вершины исходного графа.

Это сообщение отредактировал(а) mrgloom - 11.2.2013, 16:23

Тогда схема действий такая.
1) Берем какую-то одну вершину графа и добавляем ее в список.
2) Выясняем, какие вершины связаны с ней, добавляем их в тот же список.
3) Для каждой из добавленных в п.2. вершин повторяем ту же процедуру, начиная с п.1. Если новые вершины не обнаруживаются - мы выделили один максимальный подграф. 
4) Выкидываем все вершины выделенного подграфа из рассмотрения, берем какую-то вершину графа из оставшихся и снова повторяем все, начиная с п.1. Если вершин графа не осталось - работа закончена, все подграфы выделены.

 

вы не поняли, там 1 связный подграф должен быть, просто разное кол-во рёбер.

Т.е. надо найти минимальное охватывающее дерево? М-да, с терминологией у Вас все как-то совсем печально. 

Давайте-ка сделаем так. Перепишите сюда условие задачи, которую Вы пытаетесь решить, дословно. Без сокращений и прочей отсебятины. А там посмотрим, что именно Вам на самом деле нужно.

да, с графами я пока что не работал.


http://forum.vingrad.ru/forum/topic-361629.html
вот тут я пытаюсь сшить панораму.

в начале получается или полный граф (или чтобы облегчить задачу, можно некоторые связи выкинуть обрезав по порогу).

затем я хочу найти подграфы как я описал выше.
и как раз мне надо не минимальное охватывающее дерево, а все варианты подграфов содержащие все вершины и имеющие связность. 
затем я планирую каждый граф проверить на геометрические коллизии и затем посчитать сумму корреляций\ кол-во связей и выбрать лучший вариант.

Прочитал. Ничего не понял (кроме того, что писал Akina). По-видимому, Вам следует прочитать то, что он написал, и реализовать. 

это всё таки называется остов(spanning tree), т.е. задача как найти все остовы в графе.
т.е. должны быть охвачены все вершины и не должно быть циклов.

Это сообщение отредактировал(а) mrgloom - 17.5.2013, 11:09

и (если это будет быстрее) то задачу можно поставить как найти лучшие k остовов в графе.

http://www.boost.org/doc/libs/1_46_1/libs/...nning_tree.html

есть вариант брать несколько раз рэндомно, только непонятно данная реализация будет давать повторы или нет?