Обход графа с поиком его "внешних" точек.

[vedro-compota]

Доброе время суток , уважаемые программисты ))
Есть такая вот картинка-

И на этой же картинке, как мы видим есть ответ, вот что-то вроде такой последовательности вершин графа или нескольких последовательностей таких вершин ( на примере их как раз таки две ) и надо получить.
Форма задания графа ( просто , чтобы было понятно какие есть исходные данные) - это два стринггрида - 1) это координаты точек на форме 2) Это матрица связности.
Смысл в том чтобы "обойти" граф по внешним точка, внутренние нас не интересуют.
Если граф состоит из нескольких несвязанных между собой графов - то в ответ идут маршруты "внешнего обхода" всех их по отдельности.
Какие у кого есть по этому поводу идеи?
А именно-
1) как организовать структуру данных.
2) можно ли обойтись здесь без указателей ?


Прикреплю архив. Здесь программа пока просто рисует.

Интересует не программная реализация , а просто идеи того, как лучше решить , какие подзадачи, по-вашему содержит эта задача ))

[pu4koff]

Теория графов не предусматривает координаты вершин. Это не граф и задача не из этой области. Тут скорее задача на построение наибольшего многоугольника из заданных вершин\линий или что-то в этом роде.
Можно посмотреть на алгоритмы закрашивания многоугольников http://algolist.manual.ru/graphics/fill.php может натолкнет на какую-нибудь идею (у меня с математикой плохо я бы смотрел в сторону построчного сканирования)
Так же не ясно, что делать в таких случаях:

[mMAg]

А я бы посмотрел в сторону построения выпуклой оболочки. Ваша задача очень похожа на неё. Можно немного видоизменить Алгоритм Грехэма и использовать его.

P.S. Сначала нужно выделить связные области, а затем для каждой такой области применить алгоритм. Граф разбить на связные подграфы можно за O(n). Видоизменённый алгоритм Грехэма по сложности будет O(nLogn), если использовать быструю сортировку или сортировку слиянием, в итоге получится очень недурно.

[pu4koff]

Сообщение от mMAg

А я бы посмотрел в сторону построения выпуклой оболочки. Ваша задача очень похожа на неё. Можно немного видоизменить Алгоритм Грехэма и использовать его.

Да. Пожалуй более подходящий алгоритм для задачи, нежели то направление, что я предлагал. Хотя допиливать его достаточно серьезно придется.

[mMAg]

Сообщение от pu4koff

Да. Пожалуй более подходящий алгоритм для задачи, нежели то направление, что я предлагал. Хотя допиливать его достаточно серьезно придется.

Ну, на самом деле серьёзно или нет зависит от того, что именно требуется в поставленной задаче, ведь определения внешних точек автор сией темы не дал. Он только лишь привёл пример. А пример, это лишь частный случай. Я как математик не слишком люблю оперирование частными случаями. Если бы автор потрудился немного более широко раскрыть ТЗ своей задачи, я мог бы и алгоритмом помочь, но увы, отрезан, ввиду неопределённости ТЗ.

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

vedro-compota,
Структура данных - матрица смежности, если количество вершин небольшое. Список смежности, если количество вершин велико, а количество рёбер мало (т.е. граф разреженный). Так же обращаю ваше внимание на то, что список смежности нужно будет хранить дублируя рёбра, если граф неориентированный, т.е. каждое ребро необходимо разбить на 2 дуги и хранить дуги (они уже имеют направление). Без указателей можно обойтись, если будете пользоваться матрицей смежности. Во-втором случае без них обойтись не получится.

[pu4koff]

Сообщение от mMAg

Ну, на самом деле серьёзно или нет зависит от того, что именно требуется в поставленной задаче, ведь определения внешних точек автор сией темы не дал. Он только лишь привёл пример. А пример, это лишь частный случай. Я как математик не слишком люблю оперирование частными случаями. Если бы автор потрудился немного более широко раскрыть ТЗ своей задачи, я мог бы и алгоритмом помочь, но увы, отрезан, ввиду неопределённости ТЗ.

Это понятно, что задача не полностью описана, но уже видно, что нужно:
1) Разбить множество точек на группы, из которых можно собрать замкнутую область
2) Соединять не первые подходящие по алгоритму точки, а только те, между которыми есть связь в матрице смежности.
В принципе, это не так всё сложно, но скорость работы алгоритма сильно пострадает.
В зависимости ответа топикстартера по поводу моего рисунка, допиливание может существенно усложниться.

Сообщение от mMAg

А вообще это задание имеет прямое отношение к укладке графа на плоскости.

Разве? У меня с математикой туго, но я не припомню, чтобы такие задачи вписывались в теорию графов. Есть конечно такая штука, как планарный граф, но это несколько из другой оперы вроде как. Координаты вершин там не фигурируют на сколько я помню. Укладка графа на плоскость - это скорее из серии: вот вам матрица смежности, расположите вершины как-нибудь покрасивее (или я не прав?). Тут же позиция вершин уже известна.

Сообщение от mMAg

На первый взгляд эта задача к ним отношения не имеет. Но это лишь на первый взгляд.

Для не математиков можно разъяснить как это все связано, а то я не улавливаю что-то?

[mMAg]

Сообщение от pu4koff

Это понятно, что задача не полностью описана, но уже видно, что нужно:
1) Разбить множество точек на группы, из которых можно собрать замкнутую область
2) Соединять не первые подходящие по алгоритму точки, а только те, между которыми есть связь в матрице смежности.
В принципе, это не так всё сложно, но скорость работы алгоритма сильно пострадает.

Множество точек на связные группы разбивается за O(n)... Полагаю, здесь я немного поспешил с выводом и приврал немножко. Пока в голову ничего не приходит, но, может что-нибудь прийдёт. Заранее прошу прощения у автора темы, если не вспомню ничего более толкового, чем O(m), что в худшем случае приводит к O(n^2). Поскольку завтра на военные сборы отъезжаю, вставать рано нужно.
По сути, задача сводится к сортировке на каждом шаге точек, с которыми есть связь (вместо предварительной сортировки всех точек, как в Алгоритме Грехема). Что-то мне подсказывает, что сложность алгоритма увеличится на константу (в отдельных случаях может и упасть). Пока нет идей, как это обосновать. Опять же, здесь предпочтительнее хранение списком смежности (в таком случае сложность будет в среднем O(mlog(m/n))). И опять же имеем зависимость от количества рёбер, в худшем случае будет O((n^2)Logn), что отбивает всякое желание оптимайзить первый шаг. Причём, от этой сложности мы здесь не избавимся. Загвоздка в том, что при этом худшем случае лучше не сканировать всё, а просто использовать стандартный Алгоритм Грехэма. Опять же, нужно думать, и думать не о птичках, возможно, есть способ как-то решить задачу оригинально. Пока в голову ничего не лезет.

Сообщение от pu4koff

В зависимости ответа топикстартера по поводу моего рисунка, допиливание может существенно усложниться.

Да, вы правы.

Сообщение от pu4koff

Разве? У меня с математикой туго, но я не припомню, чтобы такие задачи вписывались в теорию графов. Есть конечно такая штука, как планарный граф, но это несколько из другой оперы вроде как. Координаты вершин там не фигурируют на сколько я помню. Укладка графа на плоскость - это скорее из серии: вот вам матрица смежности, расположите вершины как-нибудь покрасивее (или я не прав?). Тут же позиция вершин уже известна.

Нет. Укладка графа на плоскости имее очень большое техническое значение. Конечно, планарные графы здесь преобладают, поскольку фактически во многие задачи сводятся к тому, чтобы узнать, планарен ли граф и как его уложить на плоскости. Напомню, планарный, это который без самопересечений на плоскости можно уложить. Но это не значит, что все задачи сводятся к задачам на планарных графах. Вообще, когда говорят укладка графа, то подразумевают укладку без самопересечений и именно планарного графа. Это я там уже немного в ином смысле употребил. Но фактически, автор в своём примере не привёл пересечений рёбер, поэтому я так и сказал.
А то, что позиция вершин известна, эт даже хорошо. Это значит, что граф уже уложен и не нужно решать достаточно сложную для понимания задачу.

Сообщение от pu4koff

Для не математиков можно разъяснить как это все связано, а то я не улавливаю что-то?

Мм, не понимаю, что можно разъяснить... Посмотрите, что такое NP-полная или NP-сложная задачи. Посмотрите несколько примеров задач таких.

[vedro-compota]

mMAg и pu4koff, благодарю за ценные советы! )) начинаю применять их ))

Можно немного видоизменить Алгоритм Грехэма и использовать его.

сначала попробую немного видоизменить и использовать )))

Если бы автор потрудился немного более широко раскрыть ТЗ своей задачи, я мог бы и алгоритмом помочь,

автор попытается сам этот алгоритм создать , ибо всё-таки видел пару алгоритмов ))

[Utkin]

По-моему задача решения не имеет. Например первый граф можно представить так, что точка 4 окажется вместо точки 1. Что тогда?

автор попытается сам этот алгоритм создать , ибо всё-таки видел пару алгоритмов ))

Это как так? Уверен эти алгоритмы работают не с графами, а со структурами данных похожими на графы .
Более того, если посмотреть на задание внимательно, то совершено ясно что ТС пытается привязать графы к координатам. Но тогда в первом графе все точки внешние, ибо в трехмерном измерении цифра 4 приближена к наблюдателю, по сравнении с другими .
Задача явно не доформулирована.

[vedro-compota]

хм. разве структура данных для графа определена однозначно? ))