Обход графа

← →
Kerk © (2013-03-06 00:23) [40]

> Rouse_ © (06.03.13 00:19) [39]
> Для этого каждая вершина должна иметь список ребер

Я понял чего упустил в постановке задачи. Граф ориентированный. Вершина не знает о входящих ребрах, только об исходящих. Можно конечно сделать чтоб знала обо всех, но дофига переделывать придется.

← →
Rouse_ © (2013-03-06 00:25) [41]

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

← →
DevilDevil © (2013-03-06 09:37) [42]

так а текущая то сложность в чём ?
я честно говоря не понял )

← →
DevilDevil © (2013-03-06 10:08) [43]

Вообще я не понимаю, почему столько шума вокруг элементарных вещей
Я конечно слабо владею алгоритмикой графов (не сталкивался), но вообще всё просто

Есть вершина - структура, есть ребро - структура
Список рёбер исходящих/входящих - это односвязный список (чтобы не париться с логикой двойного добавления)

Флаг посещённой вершины - boolean
Список посещённых вершин - односвязный список

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

Для выделения памяти под структуры я бы рекомендовал использовать свой пул, а не стандартный GetMem/FreeMem. Так и память будет тратиться эффективней, и производительность выше. По моим тестам профит не столько в выделении памяти, сколько во высвобождении.

← →
Kerk © (2013-03-06 10:16) [44]

Нет никакой проблемы давно уже.

← →
Kerk © (2013-03-06 10:18) [45]

Изначальная проблема была в том, что я забыл, что можно к вершинам флаг прицепить. Такое бывает по запарке, да. Свежий взгляд меня сразу спас.

← →
Inovet © (2013-03-06 11:21) [46]

Так-то флаг, конечно, костыль для производительности.

← →
brother © (2013-03-06 11:44) [47]

чёйто?

← →
Inovet © (2013-03-06 11:48) [48]

> [47] brother © (06.03.13 11:44)
> чёйто?

Ну а какую он смыловую нагрузку несёт? Ну знаем, что прошли по узлу, и что? Откуда пришли, куда пошли, сколько раз - нет информации. Так, для решения одной задачи.

ну и? обсуждаем ведь конкретно...

> [49] brother © (06.03.13 11:49)
> ну и? обсуждаем ведь конкретно...

Я и говорю, что для оптимизации решения конкретной задачи.

> Ну а какую он смыловую нагрузку несёт? Ну знаем, что прошли
> по узлу, и что? Откуда пришли, куда пошли, сколько раз -
> нет информации. Так, для решения одной задачи.

TComponent.Tag
Ровно точно такой же "костыль".

> [51] Ega23 © (06.03.13 11:52)
> TComponent.Tag
> Ровно точно такой же "костыль".

Да я не отговариваю, просто к обсуждению.

Обход графа Найти похожие ветки