В этом параграфе вы узнаете, почему у графов нет единого «правильного» способа хранения и как выбор представления влияет на эффективность алгоритмов. Мы рассмотрим матрицу смежности, матрицу инцидентности, список смежности и список рёбер, сравним их сильные и слабые стороны и разберём, в каких случаях удобно использовать каждый из вариантов.
Ключевые вопросы параграфа
- Какие основные способы хранения графа применяются на практике?
- Как различия в представлениях отражаются на скорости работы алгоритмов и потреблении памяти?
- По каким критериям выбирать подходящее представление графа для конкретной задачи?
Способ хранения графа
В прошлом параграфе мы обсудили основные определения теории графов. Однако, чтобы работать с графами, необходимо их как-то хранить в памяти компьютера. К сожалению, не существует универсального способа хранения графов, потому что каждый имеет свои достоинства и недостатки.
Рассмотрим такой способ хранения графа, как матрица смежности. Матрица смежности представляет собой матрицу, где по строкам и столбцам располагаются номера вершин. Если рёбра между вершинами отсутствует, то на пересечении -ой строки и -ого столбца ставится 0. Если ребро есть, то ставят 1. Пример графа и его матрицы смежности приведён на рисунке ниже.
Остановитесь и подумайте:
Всегда ли матрица смежности для неориентированного графа симметрична?
Рассмотрим пример матрицы смежности для ориентированного графа. В целом, отличий не так много, кроме того, что матрица смежности перестала быть симметричной. Подумайте, почему.
Также при работе с графами применяется и матрица инцидентности. По столбцам располагаются рёбра, а по строкам номера вершин. На пересечении -ой вершины и -ого ребра ставится 1, если одним из концов ребра была вершина . Пример приведён ниже.
В случае ориентированного графа матрица инцидентности не сильно меняется, за исключением того, что на пересечении -ой вершины и -ого ребра ставится 1, когда дуга входит в вершину и -1, когда выходит.
Для экономии памяти может использоваться список смежности, который представляет из себя набор списков по числу вершин в графе. Каждый список представляет из себя перечисление всех смежных данной вершине.
В случае ориентированного графа список смежности выглядит аналогичным образом.
В некоторых случаях удобнее использовать список рёбер. Он представляет собой перечисление всех рёбер графа. Пример приведен ниже.
Упражнение 1
Подумайте, а какой вариант хранения графа в памяти компьютера самый оптимальный. Почему?
Что дальше
Теперь вы умеете представлять граф в памяти с помощью разных структур: матриц и списков. Вы знаете, в каких задачах использовать матрицу смежности, а где лучше подойдёт список смежности или рёбер.
Далее — перейдём к алгоритмам работы с графами. Начнём с базового действия — обхода графа, то есть последовательного просмотра всех его вершин и рёбер.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Граф можно хранить с помощью матрицы смежности, инцидентности, списка смежности или списка рёбер.
- Выбор способа зависит от размера графа, плотности связей и требований к скорости доступа.
- Нет универсального способа — у каждого формата есть свои плюсы и минусы.
- Эффективное представление графа — залог быстрого и надёжного алгоритма.