Способы хранения графов в памяти компьютера их плюсы и минусы
Я знаю, как написать все три, но я не уверен, что думал обо всех достоинствах и недостатках каждого из них.
Каковы преимущества и недостатки каждого из этих способов хранения графа в памяти?
Один из способов проанализировать их с точки зрения сложности памяти и времени (зависит от того, как вы хотите получить доступ к графику).
Хранение узлов как объектов с указателями друг на друга
- Сложность памяти для этого подхода составляет O(n), потому что у вас столько объектов, сколько у вас узлов. Требуемое количество указателей (на узлы) составляет до O (n ^ 2), так как каждый объект узла может содержать указатели максимум для n узлов.
- Временная сложность для этой структуры данных составляет O(n) для доступа к любому данному узлу.
Хранение матрицы весов Edge
- Это будет сложность памяти O (n ^ 2) для матрицы.
- Преимущество этой структуры данных состоит в том, что сложность времени для доступа к любому данному узлу составляет O (1).
В зависимости от того, какой алгоритм вы используете на графике и сколько узлов, вам нужно будет выбрать подходящее представление.
Еще пара вещей, чтобы рассмотреть:
Матричная модель более удобна для графов с взвешенными ребрами, сохраняя веса в матрице. Модель объекта/указателя должна хранить веса Edge в параллельном массиве, что требует синхронизации с массивом указателей.
Модель объект/указатель работает лучше с ориентированными графами, чем с неориентированными графами, потому что указатели должны поддерживаться парами, которые могут стать несинхронизированными.
Как уже отмечали некоторые, метод objects-and-pointers страдает сложностью поиска, но вполне естественен для таких вещей, как построение бинарных деревьев поиска, где много дополнительной структуры.
Лично мне нравятся матрицы смежности, потому что они значительно упрощают все виды задач, используя инструменты из алгебраической теории графов. (Например, k-я степень матрицы смежности дает число путей длины k от вершины i до вершины j. Добавьте единичную матрицу, прежде чем брать k-ую степень, чтобы получить количество путей длины <= k. n-1 несовершеннолетний от лапласиана, чтобы получить количество связующих деревьев . И так далее.)
Но все говорят, что матрицы смежности стоят дорого памяти! Они только наполовину правы: вы можете обойти это, используя разреженные матрицы, когда у вашего графа мало ребер. Структуры данных с разреженной матрицей в точности выполняют работу по поддержанию списка смежности, но при этом имеют полный набор стандартных операций с матрицами, что дает вам лучшее из обоих миров.
Я думаю, что ваш первый пример немного двусмысленный - узлы как объекты и ребра как указатели. Вы можете отслеживать их, сохраняя только указатель на некоторый корневой узел, и в этом случае доступ к данному узлу может быть неэффективным (скажем, вам нужен узел 4 - если объект узла не предоставлен, вам, возможно, придется его искать) , В этом случае вы также потеряете части графика, которые недоступны из корневого узла. Я думаю, что это тот случай, когда f64 полагает, что он говорит, что сложность времени для доступа к данному узлу равна O (n).
В противном случае вы также можете хранить массив (или хэш-карту), полный указателей на каждый узел. Это позволяет O(1) доступ к данному узлу, но немного увеличивает использование памяти. Если n - это число узлов, а e - это количество ребер, пространственная сложность этого подхода будет O (n + e).
Пространственная сложность для матричного подхода была бы вдоль линий O (n ^ 2) (предполагая, что ребра однонаправлены). Если ваш график разрежен, в вашей матрице будет много пустых ячеек. Но если ваш граф полностью связен (e = n ^ 2), это выгодно отличается от первого подхода. Как говорит RG, при таком подходе у вас также может быть меньше пропусков в кеше, если вы выделите матрицу как один кусок памяти, что может ускорить отслеживание множества ребер вокруг графа.
Третий подход, вероятно, является наиболее эффективным с точки зрения пространства в большинстве случаев - O(e) - но он сделает поиск всех ребер заданного узла O(e) рутинной работой. Я не могу вспомнить случай, когда это было бы очень полезно.
Взгляните на сравнительная таблица в Википедии. Это дает довольно хорошее понимание того, когда использовать каждое представление графиков.
Если Вы хоть немного знакомы с теорией графов, Вам наверняка интересно, как же правильно хранить граф в памяти компьютера. В этой статье рассмотрено 4 способа, как это сделать. Также проведён полный их анализ и размышления на эту тему.
Содержание:
Введение
Для начала разберёмся, что же такое граф и какие они бывают.
Граф - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин. Говоря проще, граф - это множество точек (вершин) и соединяющих их путей (дуг или рёбер). Граф может быть ориентированным и неориентированным. В ориентированном графе пути (дуги) имеют направление, а в неориентированном - не имеют. Пути в неориентированном графе называются рёбрами.
Взвешенным называется такой граф, для каждого ребра(дуги) которого определена некоторая функция. А эта функция называется весовой.
Рассмотрим пример ориентированного взвешенного графа:
На рисунке точками обозначены вершины графа, стрелками - дуги, чёрные числа - номера вершин графа, а красные - веса дуг. Вес дуги можно представить также как стоимость. Т.е. например: дан граф, нужно дойти от вершины i до вершины j, заплатив минимальное количество денег/потратив наименьшее количество времени. Пусть в нашем графе, который представлен на рисунке, нам нужно пройти из вершины 5 в вершину 2, а вес дуг - стоимость прохода по данному ребру. В данном примере очевидно, что выгоднее пройти через вершину 1 и только потом прийти в вершину 2, так мы заплатим всего 4 единицы денег, иначе, если пойти напрямую, мы заплатим целых 7 единиц.
Ну вот мы и разобрались, что такое граф. На рисунке всё смотрится красиво, все задачи вроде бы решаются легко… Но! А если граф будет действительно большим, например на 1000 вершин? Да, такой граф на бумажке рисовать очень долго и неприятно… Пускай лучше всё это делает за нас компьютер!
Теперь осталось только научить компьютер работать с графами. Сам я довольно часто участвую в олимпиадах по информатике, а там очень любят давать задачи на графы. От того, как хранить граф в той или иной задаче очень много зависит… После того, как я придумал полное решение, но, написав его, получил только половину баллов, я задумался, а правильно ли я хранил граф?
Проблема правильного хранения графа в памяти компьютера действительно актуальна в сегодняшние дни. Я решил выяснить, так какой же из способов всё-таки лучше.
Матрица смежности
Я намеренно употреблял слово “дуга”, т.к. матрица смежности приспособлена ТОЛЬКО для ориентированных графов. Очень много способов хранения приспособлены только для ориентированных графов. Однако почти во всех задачах ребро можно заменить двумя дугами, т.е. если у нас есть ребро (1,3), то мы можем заменить его на дуги (1,3) и (3,1) - так мы сможем пройти в любом направлении в любое время.
Как вы уже заметили, в матрице смежности нам часто нужно хранить большое количество нулей. Например, в нашей матрице “нужных” значений только 6, а остальные 30 - нули, не представляющие для нас почти никакой нужной информации.
Для представления графа матрицей смежности нужно V в квадрате (где V - количество вершин). Если граф почти полный, т.е. Е почти развно V в квадрате (где Е - количество дуг), этот способ хранения графа наиболее выгоден, т.к. его очень просто реализовывать и память будет заполнена “нужными” значениями.
Кроме большого количества требуемой памяти и медленной работы на разреженных графах у матрицы смежности есть ещё один важный недостаток. Иногда в задачах нужно выводить не номера вершин, а номера дуг(рёбер) на вводе. Хранить эти номера матрица смежности не умеет. Нужно реализовывать восстановление номера дуги(ребра) как-то иначе, а это совсем неудобно.
Описание Бержа
В нулевом столбце хранятся “длины” строк. Однако, вес дуг никак не хранится, а если его хранить отдельно, то нужно заводить ещё один массив размером V в квадрате…
Список дуг
Мы чётко видим, что почти вся таблица заполнена “нужными” значениями, а не нулями. Это уже хорошо, значит, память экономится.
Как видно, этот способ, в отличие от матрицы смежности и описания Бержа, хранит информацию о номере дуги. Также ясно, что этот способ нам выгоден, если чаще всего нам нужно будет узнать что-то (вес, вершины начала или конца) о i-ой дуге. Однако, такие задачи в практическом программировании встречаются довольно редко.
Если в предыдущих представлениях одно ребро мы заменяли двумя дугами, то список дуг может хранить или дуги или рёбра (в зависимости от реализации). Это довольно удобно и может требовать в 2 раза меньше памяти.
Список смежности
И последний способ, про который я вам расскажу - список смежности. Он представляет из себя два массива: vert и adj.
Из каждой вершины может выходить 0, 1 и более дуг, причём вершин будет V или менее. Если из вершины i не выходит дуг (т.е. количество дуг равно нулю), то в массиве vert в i-ой клетке будет храниться значение ПУСТО. Если из вершины i выходит хотя бы одна дуга, то в массиве vert в i-ой клетке будет храниться номер элемента массива adj, в котором хранится конечная вершина дуги. Также в массиве adj хранится вес дуги, и указатель на следующую “конечную” вершину дуги, которая начинается в вершине i. Поначалу может показаться, что этот способ очень запутан, т.к. один массив указывает на другой, другой сам на себя, при чём много раз. Однако это не совсем так, т.к. следует лишь несколько раз самому попробовать реализовать хранение графа таким способом, и он кажется очень мощным, полезным и несложным. Давайте сами попробуем разобраться на примере.
На вход нам подаются следующие данные:
В массиве adj первая строка - конечная вершина дуги, вторая - её вес, а третья - ссылка на следующую.
В этом примере я специально вводил дуги не по порядку, чтобы можно было лучше разобраться, и было видно, что позиции могут быть совершенно различными. Например, первая конечная вершина дуги, начинающейся в вершине 5, лежит в массиве adj на первой позиции, а не на пятой.
Времена у всех операций, вроде бы, такие же, как и у списка рёбер. Однако, большинство из них реально намного меньше. Например, проверка смежности вершин x и y и перечисление всех вершин смежных с x в списке рёбер гарантированно будет выполнятся О(Е) операций, т.к. нам обязательно нужно пробежать весь список, а в списке смежности мы бежим только по вершинам, смежным с х.
Оптимизация к списку смежности
UPD: Данная оптимизация не актуальна. Лучше вместо хранения ссылки на следующий элемент хранить ссылку на предыдущий.
Когда я первый раз пытался разобраться, что такое список смежности, меня очень смутила процедура добавления дуги. Для того, чтобы добавить дугу (i,j) мы должны начать из вершины i и пройти по всем вершинам, смежными с нею. И так каждый раз! А что если вершине х инцидентны E рёбер? Тогда сложность добавления O(E в квадрате) ! Это совсем не годится.
А почему бы нам не добавлять ребро сразу туда, куда надо? Конечно, при считывании, мы сразу записываем данные в нужную нам ячейку (в конец получившегося списка). Но ведь на эти данные нужно сделать указатель. Самое тяжёлое - найти место, где делать указатель. Поиск этого места и занимает основу драгоценного времени. А что, если хранить указатель не только на первую конечную вершину дуги, но и на последнюю? Тогда наша проблема решена! Добавление занимает О(1) времени, но требует дополнительно О(V) памяти…
Здесь в первой строке массива vert хранится указатель на первую конечную вершину, во второй - на последнюю. В данном примере польза от этой оптимизации почти не заметна, т.к. максимальное вершин, исходящих из одной дуги, равно 2, что очень мало. Если дуг, инцидентных одной вершине, будет много, то и ускорение будет довольно большое и “лишняя” выделенная память окупится.
Возможно, о данной оптимизации к списку смежности где-то уже было написано до меня, но ни в интернете, ни в печатных источниках я этого не встречал.
Заключение
Я пытался найти универсальный способ хранения графа в памяти компьютера, который бы хранил максимально много информации о графе, работал с любыми графами и работал бы быстро. Однако, универсального способа нет. Для различных задач и графов оптимальны различные представления. Конечно, наиболее мощным и универсальным способом хранения является список смежности. С моей оптимизацией он работает быстрее и всё ещё требует не так уж и много памяти. Однако, если количество дуг приближается к квадрату количества вершин, то лучше матрицы смежности способа не найти, т.к. тогда скорость работы и количество памяти даже списка смежности приближается к матрице смежности, если не требует больше… Конечно, можно написать и список смежности, однако пишется он дольше матрицы смежности, да и работать с матрицей смежности намного проще.
Конечно, мною были рассмотрены не все способы представления графов в памяти компьютера. Я старался рассмотреть лишь те, которые смогут реально помочь в олимпиадном программировании, т.е. пишутся наиболее быстро, быстро работают, и требуют немного памяти. Я рассмотрел только статические способы представления графа в памяти компьютера. Есть ещё различные динамические способы хранения графов, они занимают меньше памяти, иногда быстрее работают. Однако и пишутся они намного сложнее. Например, элементарная работа с графом, хранящимся в структуре Вирта, еле-еле влазит в 250 строк кода на паскале…
Конечно, в профессиональном программировании лучше использовать динамические методы, однако и старые добрые статические способы от них не так уж и далеко отстают! ;)
Другие Алгоритмы:
2006-01-15 RUSSIAN
russian delphi pascal graph theory algorithm алгоритм
Я знаю как написать все три, но я не уверен, что я подумал обо всех преимуществах и недостатках каждого.
каковы преимущества и недостатки каждого из этих способов хранения график в памяти?
один из способов анализа - это сложность памяти и времени (которая зависит от того, как вы хотите получить доступ к графику).
хранение узлов как объектов с указателями друг на друга
- сложность памяти для этого подхода составляет O (n), потому что у вас есть столько объектов, сколько у вас есть узлов. Количество указателей (на узлы), необходимых до O(n^2), поскольку каждый объект узла может содержать указатели для до n узлов.
- сложность времени для этих данных структура O (n) для доступа к любому заданному узлу.
хранение матрицы весов ребер
- это будет сложность памяти O (n^2) для матрицы.
- преимущество этой структуры данных заключается в том, что сложность доступа к любому заданному узлу равна O(1).
в зависимости от того, какой алгоритм вы запустите на графике и сколько узлов есть, вам придется выбрать подходящее представление.
несколько вещей, чтобы рассмотреть:
матричная модель легче поддается графам с взвешенными ребрами, сохраняя веса в матрице. Модель объекта / указателя должна хранить веса ребер в параллельном массиве, что требует синхронизации с массивом указателей.
модель объекта / указателя лучше работает с направленными графиками, чем неориентированные графики, потому что указатели должны поддерживаться в парах, который может стать несинхронизированным.
метод objects-and-pointers страдает от сложности поиска, как некоторые отметили, но довольно естественны для таких вещей, как создание бинарных деревьев поиска, где есть много дополнительной структуры.
Я лично люблю матрицы смежности, потому что они делают все виды проблем намного проще, используя инструменты из алгебраической теории графов. (Например, K-я степень матрицы смежности дает количество путей длины k от вершины i до вершины j. Добавить тож матрица перед принятием K-й степени, чтобы получить количество путей длины
но все говорят, что матрицы смежности стоят дорого! Они только наполовину правы: вы можете обойти это, используя разреженные матрицы, когда ваш график имеет несколько ребер. Разреженные матричные структуры данных выполняют именно работу по поддержанию списка смежности, но по-прежнему имеют полную гамму стандартных матричных операций доступен, давая вам лучшее из обоих миров.
Я думаю, что ваш первый пример немного неоднозначен-узлы как объекты и ребра как указатели. Вы можете отслеживать их, сохраняя только указатель на некоторый корневой узел, в этом случае доступ к данному узлу может быть неэффективным (скажем, вы хотите узел 4 - если объект узла не предоставлен, вам может потребоваться его поиск). В этом случае вы также потеряете части графика, которые недоступны из корневого узла. Я думаю, что это тот случай, когда F64 rainbow предполагает, когда он говорит о сложности времени для доступа к данному узлу используется O (n).
в противном случае вы также можете сохранить массив (или hashmap), полный указателей на каждый узел. Это позволяет O (1) получить доступ к данному узлу, но немного увеличивает использование памяти. Если n-число узлов, а e-число ребер, то пространственная сложность этого подхода будет равна O(n + e).
сложность пространства для матричного подхода будет вдоль линий O (n^2) (предполагая, что ребра однонаправлены). Если граф разреженный, вы в вашей матрице много пустых ячеек. Но если ваш график полностью связан (e = n^2), это выгодно отличается от первого подхода. Как говорит RG, у вас также может быть меньше пропусков кэша с этим подходом, если вы выделите матрицу как один кусок памяти, что может сделать следующие много ребер вокруг графика быстрее.
третий подход, вероятно, наиболее эффективен для большинства случаев-O(e), но сделал бы поиск всех ребер данного узла o (e) рутиной. Я не могу вспоминаю случай, когда это было бы очень полезно.
посмотри сравнительная таблица на Википедии. Это дает довольно хорошее понимание того, когда использовать каждое представление графиков.
хорошо, поэтому, если ребра не имеют веса, матрица может быть двоичным массивом, и использование двоичных операторов может заставить вещи идти очень, очень быстро в этом случае.
Если график разрежен, метод object / pointer кажется намного более эффективным. Удержание объекта / указателей в структуре данных специально, чтобы уговорить их в один кусок памяти, также может быть хорошим планом или любым другим способом заставить их оставаться вместе.
список смежности - просто список подключенные узлы-кажутся наиболее эффективной памятью, но, вероятно, и самой медленной.
реверсирование направленного графика легко с матричным представлением и легко со списком смежности, но не так здорово с представлением объекта/указателя.
есть еще один вариант: узлы как объекты, ребра как объекты, причем каждое ребро одновременно находится в двух двусвязных списках: список всех ребер, выходящих из одного узла, и список всех ребер, входящих в один узел.
накладные расходы памяти большие (2 указателя на узел и 6 указателей на ребро), но вы получаете
- O (1) вставка узла
- O (1) вставка ребра (заданные указатели на узлы "from" и "to")
- O (1) удаление ребра (с учетом указателя)
- o(deg (n)) удаление узла (учитывая указатель)
- O(deg (n)) поиск соседей узла
структура также может представлять собой довольно общий граф: ориентированный мультиграф с петлями (т. е. вы можете иметь несколько разных ребер между теми же двумя узлами, включая несколько разных петель - ребер, идущих от x до x).
Начнём с выяснения, зачем же нам нужны графы, какие вещи в реальном мире они позволяют изучать. Посмотрим на карту метрополитена города Киева:
Основное, что мы видим на ней — это станции и перегоны между ними.
Теперь взглянем на участок Москвы с автомобильными дорогами (скриншот сделан с сайта Яндекс.Карты).
Можно описывать сеть дорог как набор перекрёстков, некоторые из которых соединены участками дорог.
Далее, обратим внимание на генеалогическое древо славянской языковой группы.
Наконец, посмотрим на пример цепи питания в биологии.
Что общего у всех этих картинок? Главное, что на них изображено — это объекты и связи между ними. В теории графов все такие картинки называются графами. Графы состоят из вершин и рёбер. Так, в графе киевского метрополитена станции считаются вершинами, а перегоны между ними — рёбрами. В графе цепи питания биологические виды являются вершинами, и направленное ребро проведено от одного вида к другому тогда, когда первый вид является пищей для второго.
Итак, графом называется набор вершин и набор рёбер. Каждое ребро соединяет две вершины.
Степенью вершины называется количество рёбер, концом которых она является. Например, в графе метрополитенов большинство станций имеют степень 2, а конечные станции имеют степень 1. В графе славянской языковой группы вершина «западнославянский язык» имеет степень 4.
2. Виды графов и пути в графах
Для представления разных объектов и связей между ними используются разные виды графов. Например, графы бывают ориентированные и неориентированные. Ориентированные графы — это графы, в котором у каждого ребра есть начало и конец. Такие рёбра рисуют стрелками. В наших примерах граф цепи питания ориентированный, а граф метрополитена — неориентированные.Подумаем, нужно ли считать граф дорог ориентированным. Пусть мы пишем программу, которая по графу дорог находит автомобильный маршрут между двумя точками в городе. Поскольку в городе бывают улицы с односторонним движением, то наша программа должна это учитывать. Значит, на каждом ребре нужно хранить направление — возможное направление проезда по ребру. Если по дороге можно проехать в обе стороны, то рисуют два ребра со стрелками в разные стороны.
Путём в графе называется любая последовательность вершин, в которой каждые две соседние вершины соединены ребром. На рисунке выше A → C → B → G — это путь из вершины A в вершину G. Есть и более короткий путь из A в G: путь A → B → G. Длиной путиназывается количество рёбер в нём. Таким образом, кратчайший путь из A в G имеет длину 2.
Циклом в графе называют путь, у которого начальная и конечная вершина совпадают. На рисунке выше путь A → C → B → D → A является циклом.
Если вы внимательно посмотрите на определение пути и цикла, то увидите, что путём так же можно считать последовательность A → D → B → D → B, а последовательность F → E → F удовлетворяет определению цикла. Чтобы исключить такие патологические ситуации из рассмотрения, обычно вводят понятия простого пути и простого цикла. Простой путь — это путь, в котором нет повторяющихся рёбер. Простой цикл это цикл, который является простым путём.(Осторожно, сейчас мы введём очень сложное понятие.) Компонентой связностинеориентированного графа называется любой набор его вершин, который удовлетворяет следующим двум свойствам:
- между любыми двумя вершинами набора существует путь;
- набор нельзя расширить, добавив в него ещё хотя бы одну вершину, чтобы при этом осталось верным свойство 1.
В ориентированном графе путём называется любая последовательность вершин, в которой соседние вершины соединены ребром, и это ребро идёт «слева направо» (в нужную сторону). Например, на рисунке ниже A → B → C → D является путём, а A → D → C → B — не является (потому что в графе нет рёбер A → D и C → B).
В ориентированном графе некоторые понятия, которые мы ввели для неориентированных графов, имеют свои аналоги. Например, наряду с понятием «степень вершины», в ориентированных графах используются понятия полустепень захода (количество рёбер, входящих в вершину) и полустепень исхода (количество рёбер, исходящих из вершины). На рисунке выше вершина D имеет полустепень захода 1 и полустепень исхода 3.
Наконец, отметим, что в некоторых графах допустимы ситуации, изображённые на следующей картинке.
3. Деревья
На практике часто встречаются графы, которые обладают какими-нибудь особенностями строения. Один из часто встречающихся видов графов — это деревья. Дерево — это связный неориентированный граф без петель и кратных рёбер, в котором нет циклов. Типичный пример дерева изображён на рисунке ниже.
Деревья обладают рядом особых свойств. Например, в дереве между любыми двумя вершинами существует единственный простой путь. Действительно, если бы между какими-нибудь двумя вершинами существовало более одного простого пути, то отсюда бы следовало, что в графе есть простой цикл.
Ещё одно удивительное свойство деревьев — это связь между количеством вершин и количеством рёбер. Договоримся обозначать буквой V количество вершин (от англ. vertex «вершина»), а буквой E — количество рёбер (от англ. edge «ребро»). Например, у дерева на рисунке выше V = 11, E = 10. Мы видим, что для графа на рисунке E = V − 1.
Чтобы понять, всегда ли это будет верно, рассмотрим висячие вершины. Висячей вершинойназывается вершина степени 1. На рисунке выше висячими являются вершины A, C, F, G, H, J и K. Заметим, что в дереве, в котором есть хотя бы две вершины, всегда есть хотя бы одна висячая вершина. Действительно, выберем произвольную вершину дерева и пойдём из неё гулять по рёбрам дерева в произвольном направлении, не возвращаясь назад. Поскольку циклов в дереве нет, то с каждым шагом мы будем посещать всё новые и новые вершины и в какой-то момент придём в вершину, из которой никуда пойти нельзя. Эта вершина и будет висячей.
Правда ли, что если в дереве есть хотя бы две вершины, то в нём есть хотя бы две висячие вершины? А правда ли, что если в дереве есть хотя бы три вершины, то в нём есть хотя бы три висячие вершины?Теорема. В любом дереве E = V − 1.
Доказательство. Как мы выяснили, если в дереве хотя бы две вершины, то в нём есть хотя бы одна висячая вершина. Выберем её и удалим из графа её и ребро, за которое она присоединена к графу. При этом количество вершин и рёбер уменьшится на единицу. С новым графом проделаем ту же операцию. В конце концов, когда мы удалим всё, что можно, мы получим граф из одной вершины. Для него V = 1, E = 0, т.е. E = V − 1. Значит, и в исходном дереве выполнялось E = V − 1. ▮
4. Как хранить граф в программах
Для представления графов в памяти компьютера используется несколько способов. Пусть вершины графов, которые мы рассматриваем, занумерованы, начиная с нуля. Рассмотрим следующий граф:
Второй способ, которым можно хранить этот граф, — это структура данных «матрица смежности». Матрица смежности — это квадратная таблица, в которой на пересечении строки i и столбца j стоит 1, если в графе есть ребро из вершины i в вершину j, и стоит 0, если такого ребра нет.
Заметим, что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали. Главная диагональ в матрице идёт из левого верхнего угла в правый нижний.
Наконец, третий способ, который часто используют для представления графов, — это структура данных «списки смежности». В списках смежности для каждой вершины хранится список всех её соседей.
Читайте также: