| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Определение частей несвязного графа |
| Автор: Afrodiziac 25.12.2007, 15:45 |
| Приветствую! Имеется граф заданный массивом ребер на плоскости. Граф планарный, т.е. никакие ребра не пересекаются. Граф может быть либо связным и тогда он по форме напоминает кольцо (т.е. вообще говоря из каждой вершины выходит только 2 ребра), либо не связным, тогда состоит из n числа колец, которые разуеемся не пересекаются, но ЧТО ВАЖНО! могут иметь общую точку (т.е. для этой общей точки вобщем соответствовать 2 ребка одного кольца и 2 ребра другого... во всех остальный случаях вершины имеют по 2 ребра). Необходимо разбить массив ребер на n массивов (n - соответствует числу не связных компонент) при условии что если какие-либо из связных компонент имеют общую точку всеравно считались не связными и точки таких компонент разбивались по разным массивам. Начал реализовывать... но что-то шарики за ролики заезжают... Возможно кто-то знает красивое решение. Спасибо. |
| Автор: Earnest 26.12.2007, 09:07 |
| Ты бы сначала с постановкой задачи и терминами определился. Связная компонента графа - это набор вершин (и ребер), взаимно доступных. Ищется элементарно - обходом и пометкой компонент. Далее, есть ребра-мостики (точного термина не помню): убери такое ребро и граф развалится на 2 компоненты. Тоже есть алгоритм для поиска. А ты про что говоришь? Какая-такая общая точка? Вершина? Тогда у нее как минимум 2 ребра и чем она отличается от остальных? Или ты говоришь о вершине, общей для 2 циклов, и тебе надо циклы найти, причем минимальные, а граф - евклидов (т.е. имеют смысл точек на плоскости а ребра - это соединяющие их отрезки)? |