Комментарии 19
Отличная статья, спасибо!
Если кого-то (как и меня когда-то) заинтересует вопрос, "а есть ли что-то более эффективное?" рекомендую почитать вот эту статью: Log(Graph): A Near-Optimal High-Performance Graph Representation (ethz.ch)
Матрица смежности: Для хранения рёбер используется двумерная матрица размерности [V, V], каждый [a, b] элемент которой равен 1, если вершины a и b являются смежными и 0 в противном случае.
Не учтены кратные рёбра.
Векторы смежности, Массивы смежности:
А куда делись сведения о ребре "c" для вершины 2?
Благодарю, исправлено.
Для кратных ребер значение увеличивается +1
Количество кратных рёбер в общем случае - не ограничено. Так что +1 может быть недостаточно.
Тогда должно быть не "каждый [a, b] элемент которой равен 1", а что-то типа "каждый [a, b] элемент которой равен количеству кратных рёбер между этими вершинами, и соответственно для смежных вершин больше нуля, а для не-смежных вершин равен нулю".
Спасибо огромное за труд! Как раз собирался искать эту информацию, а тут и вы подоспели =)
В качестве приглашения на курс статья выглядит следующим образом: Вы хотите разобраться в алгоритмах на графах — приходите — мы Вам всё подробно расскажем. Если не сможете, то, всё-равно, приходите.
А на самом деле, графы — это слишком обширная тема. Имеются, даже, довольно толстенные книжки, вроде нашего Евстигнеева или (у них) Сэджвика...
Крайне интересно было бы сравнить различные способы представления графов. Здесь, даже, крайне интересно покрутить самые расточительные по расходу памяти способы (вроде "списка рёбер и вершин"). Посмотреть, как это делается на различных языках программирования. И привести какие-нибудь любопытные и познавательные примеры применения.
Ну и, конечно, вопрос визуализации графов.
Да, поддерживаю, Сэджвик - очень хорошая книжка (все 2-е), AlgoList - очень хороший сайт, я б еще в список добавил "Теория графов. Алгоритмический подход (1978)" Никоса Кристофидеса, почему-то только там я нормально прочитал и понял "Венгерский алгоритм" (Задача о назначениях), и, возможно, "Задачу о максимальном потоке минимальной стоимости" (в точности не помню)
Лично мне ни разу не доводилось видеть алгоритм обработки графа, который бы использовал такой способ хранения вершин и рёбер.
На самом деле, в dot/graphviz именно такой способ используется. Сырые данные запихиваются как множества, причём в свободном стиле можно сперва перечислить вершины, потом рёбра, или запихнуть вперемешку.
Конечный результат - единственная картинка; цели оптимизировать её отрисовку по скорости практически нет.
А генерить в связи с простотой очень удобно программно, иногда прямо в url - выплюнул структуру в лог, там ткнул, и в браузере открылась вполне сносная визуализация.
Матрица смежности
Это самый популярный и расточительный способ представления графа в памяти
Если использовать разреженную матрицу (sparse matrix), то не расточительный.
Что-то вы немного странной инфы накрутили.
Векторы смежности и массивы смежности кмк идиоматически должны быть наоборот: чаще всего в языках программирования массивы статического размера, тогда как векторы динамического.
Вообще векторы смежности и списки смежности почти всегда (на самом деле по опыту всегда, ни разу не слышал разделения на массивы/векторы/списки смежности) называются списками смежности. А как вы их реализуете (через векторы, массивы или списки) уже детали. Структура с оглавлением по факту тот же список смежности, только опять же реализованный неким другим образом.
Кажется, во всех алгоритмических вопросах достаточно понять концепцию, а реализовывать исходя из нужд задачи. Тут же получается, что новичок, прочтя вашу статью, станет пытаться вникнуть во все описанные подходы, что может только запутать из-за их большого количества. Хотя по факту, описав лишь концепции, можно было бы сократить статью вдвое. И это позволило бы накинуть больше информации о том, когда те или иные подходы оказываются полезными, а когда нет.
И тут вспомнился коммерческий Neo4j, который тупо (и вполне успешно) хранит всю информацию о рёбрах и вершинах с произвольным количеством тегов и атрибутов тупо в JSON
А в приведённых примерах вектора смежности и массива смежности, во вторых строчках нет ли ошибки?
Способы хранения графа в памяти компьютера