Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3898081 Tue, 19 Dec 2023 07:42:15 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3898081 Квант Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3898005 Mon, 18 Dec 2023 05:04:04 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3898005 Цитата Квант @
С кратными ребрами - это уж диковинка какая то

Да нет никакой диковинки. Два населённых пункта, между которыми есть раздолбанная грунтовка и более-менее приличная дорога, но втрое длиннее - самая что ни на есть банальная обыденность.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3898002 Sun, 17 Dec 2023 13:41:17 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3898002 Цитата Akina @
Квант
Главное в моём вопросе - с кратными рёбрами.

С кратными ребрами - это уж диковинка какая то]]> Квант Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897940 Fri, 15 Dec 2023 06:00:03 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897940 Квант
Главное в моём вопросе - с кратными рёбрами.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897938 Fri, 15 Dec 2023 04:19:42 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897938 Цитата Akina @
Цитата Квант @
В php матрица смежности легко задается

Хорошо, когда граф ненаправленный..
А если взвешенный направленный? да ещё с кратными рёбрами.. вот хотел бы я посмотреть на "легко задаётся" в этом случае.

В матрице смежности задаются же оба ребра - от вершины i к вершине j, и также от j к i, соответственно, присвоив какое то большое значение одному, пулучим направленный граф]]> Квант Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897877 Thu, 14 Dec 2023 05:56:03 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897877 Цитата Квант @
В php матрица смежности легко задается

Хорошо, когда граф ненаправленный..
А если взвешенный направленный? да ещё с кратными рёбрами.. вот хотел бы я посмотреть на "легко задаётся" в этом случае.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897876 Thu, 14 Dec 2023 04:26:05 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897876
    $matrix = [
                [ 0, 8, 4, 11],
                [ 8, 0, 9, 5 ],
                [ 4, 9, 0, 8 ],
                [11, 5, 8, 0 ]
              ];

, тут числа - это расстояния, а индексы массива - узлы графа.

Список смежности компактнее, но он не дает того что выше, пространственного представления]]> Квант Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897875 Thu, 14 Dec 2023 00:49:33 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897875
1. для сильно разреженных графов вроде неоптимально, т е когда много объектов и между ними слабая связь
2. учитывать всякие петли и кратные ребра в мультиграфах может быть проблематично
3. например, в "чистом" Си нет встроенного vector-а С++ого ( в стандарте С89 к примеру ), поэтому, например, список смежности программировать в Си, это создавать динамический массив списков тоже не оч.просто, с тзрения работы с памятью и пр. пр.

зы: матрица смежности оч.удобна, т к это наглядно и легко программируется), но вроде б(!) большинство алгоритмов на графах не используют м.смежности в качестве его ( графа ) способа представления]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897852 Wed, 13 Dec 2023 09:17:41 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897852 любой алгоритм на графах может реализовываться и с исходными в виде матрицы смежности.

К слову - конвертация представления графа из матрицы смежности в любой другой - это тоже алгоритмы на матрице смежности. И вполне себе практическая задача. И, скажем, в случае ориентированного графа с кратными рёбрами, такая конвертация может быть не самой простой задачей.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897824 Wed, 13 Dec 2023 06:17:29 +0000 Алгоритмы на матрице смежности https://forum.sources.ru/index.php?showtopic=440429&view=findpost&p=3897824 Граф задан в виде матрицы смежности.
Интересуют какие практические проблемы, алгоритмы вам встречались для таких графов.
Именно чтобы желательно из реальной жизни, может для целей разработки игр.

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

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

Спасибо.]]> Квант Алгоритмы