Алгоритмы на матрице смежности

[Квант]

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

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

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

Спасибо.

[Akina]

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

К слову - конвертация представления графа из матрицы смежности в любой другой - это тоже алгоритмы на матрице смежности. И вполне себе практическая задача. И, скажем, в случае ориентированного графа с кратными рёбрами, такая конвертация может быть не самой простой задачей.

[FasterHarder]

все имхо

1. для сильно разреженных графов вроде неоптимально, т е когда много объектов и между ними слабая связь
2. учитывать всякие петли и кратные ребра в мультиграфах может быть проблематично
3. например, в "чистом" Си нет встроенного vector-а С++ого ( в стандарте С89 к примеру ), поэтому, например, список смежности программировать в Си, это создавать динамический массив списков тоже не оч.просто, с тзрения работы с памятью и пр. пр.

зы: матрица смежности оч.удобна, т к это наглядно и легко программируется), но вроде б(!) большинство алгоритмов на графах не используют м.смежности в качестве его ( графа ) способа представления

[Квант]

В php матрица смежности легко задается:

$matrix = [
            [ 0, 8, 4, 11],
            [ 8, 0, 9, 5 ],
            [ 4, 9, 0, 8 ],
            [11, 5, 8, 0 ]
          ];

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

Список смежности компактнее, но он не дает того что выше, пространственного представления

[Akina]

Цитата Квант @ 14.12.23, 04:26

В php матрица смежности легко задается

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

Сообщение отредактировано: Akina - 14.12.23, 05:56

[Квант]

Цитата Akina @ 14.12.23, 05:56

Цитата Квант @ 14.12.23, 04:26

В php матрица смежности легко задается

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

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

[Akina]

Квант
Главное в моём вопросе - с кратными рёбрами.

[Квант]

Цитата Akina @ 15.12.23, 06:00

Квант
Главное в моём вопросе - с кратными рёбрами.

С кратными ребрами - это уж диковинка какая то

[Akina]

Цитата Квант @ 17.12.23, 13:41

С кратными ребрами - это уж диковинка какая то

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

[Квант]

Подумаю над тем как мурашки помогли бы найти минимальное остовное дерево, а то смотрю по этому вопросу вакуум