| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Алгоритмы на матрице смежности |
| Автор: Квант 13.12.23, 06:17 |
| Приветствую. Граф задан в виде матрицы смежности. Интересуют какие практические проблемы, алгоритмы вам встречались для таких графов. Именно чтобы желательно из реальной жизни, может для целей разработки игр. Написал свою библиотеку муравьиной колонии, она неплохо решает задачу коммивояжера и задачу поиска кратчайшего пути. Интересно бы проанализировать как с помощью этого подхода решатся другие задачи. В некоторых случаях смотрю не все так ясно, и мало что нагугливается, например задача поиска минимального остовного дерева, с помощью муравьиного алгоритма. Спасибо. |
| Автор: Akina 13.12.23, 09:17 |
| Матрица смежности - всего лишь один из способов представления графа. А потому любой алгоритм на графах может реализовываться и с исходными в виде матрицы смежности. К слову - конвертация представления графа из матрицы смежности в любой другой - это тоже алгоритмы на матрице смежности. И вполне себе практическая задача. И, скажем, в случае ориентированного графа с кратными рёбрами, такая конвертация может быть не самой простой задачей. |
| Автор: FasterHarder 14.12.23, 00:49 |
| все имхо 1. для сильно разреженных графов вроде неоптимально, т е когда много объектов и между ними слабая связь 2. учитывать всякие петли и кратные ребра в мультиграфах может быть проблематично 3. например, в "чистом" Си нет встроенного vector-а С++ого ( в стандарте С89 к примеру ), поэтому, например, список смежности программировать в Си, это создавать динамический массив списков тоже не оч.просто, с тзрения работы с памятью и пр. пр. зы: матрица смежности оч.удобна, т к это наглядно и легко программируется), но вроде б(!) большинство алгоритмов на графах не используют м.смежности в качестве его ( графа ) способа представления |
| Автор: Квант 14.12.23, 04:26 |
| В php матрица смежности легко задается: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> $matrix = [ [ 0, 8, 4, 11], [ 8, 0, 9, 5 ], [ 4, 9, 0, 8 ], [11, 5, 8, 0 ] ]; , тут числа - это расстояния, а индексы массива - узлы графа. Список смежности компактнее, но он не дает того что выше, пространственного представления |
| Автор: Akina 14.12.23, 05:56 |
| Хорошо, когда граф ненаправленный.. А если взвешенный направленный? да ещё с кратными рёбрами.. вот хотел бы я посмотреть на "легко задаётся" в этом случае. |
| Автор: Квант 15.12.23, 04:19 |
| Цитата Akina @ Хорошо, когда граф ненаправленный.. А если взвешенный направленный? да ещё с кратными рёбрами.. вот хотел бы я посмотреть на "легко задаётся" в этом случае. В матрице смежности задаются же оба ребра - от вершины i к вершине j, и также от j к i, соответственно, присвоив какое то большое значение одному, пулучим направленный граф |
| Автор: Akina 15.12.23, 06:00 |
| Квант Главное в моём вопросе - с кратными рёбрами. |
| Автор: Квант 17.12.23, 13:41 |
| С кратными ребрами - это уж диковинка какая то |
| Автор: Akina 18.12.23, 05:04 |
| Да нет никакой диковинки. Два населённых пункта, между которыми есть раздолбанная грунтовка и более-менее приличная дорога, но втрое длиннее - самая что ни на есть банальная обыденность. |
| Автор: Квант 19.12.23, 07:42 |
| Подумаю над тем как мурашки помогли бы найти минимальное остовное дерево, а то смотрю по этому вопросу вакуум |