Список смежности

Список смежности

представляет граф в виде массива связанного списка.

  • Представление списка смежности
  • Структура списка смежности
  • Список смежности C ++
  • Список смежности Java
  • Список смежности Python
  • Код списка смежности в C
  • Код списка смежности в C++
  • Код списка смежности Java

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

Структура данных графа

представляет собой набор узлов, которые имеют данные и связаны с другими узлами.

  • Способы представления графа1. Матрица смежности2. Список смежности
  • 1. Матрица смежности
  • 2. Список смежности
  • Операции над графами

Каждое отношение — это ребро от одного узла к другому. Публикуете ли вы фотографию, присоединяетесь ли к группе, например, к странице и т. Для этих отношений создается новое ребро.

Список смежности

Точнее,

граф

— это структура данных (V, E), которая состоит из:

  • Коллекция вершин V.
  • Набор ребер E, представленный в виде упорядоченных пар вершин (u, v).

Список смежности

Матрица (таблица) смежности

Это представление позволяет легко проверять наличие ребер
между заданными парами вершин. Для поиска всех соседей, в которые ведут ребра
из вершины vi, необходимо
просмотреть соответствующую ей i -ю строку матрицы AG, а чтобы найти вершины,
из которых ребра идут в vi, необходимо
просмотреть ее i -ый столбец. Требуемая для AG память — по порядку n2 битов —
не может быть уменьшена для графов, у которых «много» ребер. Но для разреженных графов с числом ребер существенно меньшим по порядку n2 в матрице смежности много
«ненужных» нулей. Для таких графов более эффективными могут оказаться другие представления.

Матрица (таблица) инцидентности

Таким образом, в матрице инцидентности BG любому ребру ej = (vi,vk) соответствует j -ый столбец, в котором в i -ой строке стоит 1, а в k -ой — -1. Ребра -петли выделяются
числом 2. Для проверки наличия ребра между двумя вершинам и vi и vk требуется
просмотреть i -ю и k -ую строки BG, поиск всех соседей вершины требует просмотра
соответствующей строки. Если m >> n, то это требует существенно больше времени, чем
при использовании матрицы смежности. Поэтому при практическом решении задач на графах матрица инцидентности почти не используется.

Списки смежности

Определение 9. Пусть G=(V,E) — ориентированный граф, v — вершина из V. Список смежности Lv для вершины v включает все смежные с ней вершины, т.

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

Пример 9. Рассмотрим следующий граф G=(V,E):

Он показан на рис.

Построим для него определенные выше представления.

  • Матрица смежности.
  • Матрица инцидентности.
  • Списки смежности.
  • Представление матрицы смежности
  • Пример матрицы смежности
  • Плюсы матрицы смежности
  • Минусы матрицы смежности
  • Код матрицы смежности
  • Матрица смежности в C++
  • Матрица смежности в Java
  • Матрица смежности в Python

Представление матрицы смежности

Размер матрицы VxV, где V — количество вершин в графе, а значение записи Aij равно 1 или 0, в зависимости от того, существует ли ребро от вершины i до вершины j.

Пример матрицы смежности

Изображение ниже показывает график и его эквивалентную матрицу смежности.

Список смежности

В случае неориентированного графа матрица симметрична относительно диагонали, потому что у каждого ребра (i, j) также есть ребро (j, i).

Плюсы матрицы смежности

Основные операции, такие как добавление ребра, удаление ребра и проверка наличия ребра от вершины i до вершины j, являются чрезвычайно эффективными по времени операциями. Операциями с постоянным временем.

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

Однако самое большое преимущество исходит от использования матриц. Последние достижения в области аппаратного обеспечения позволяют нам выполнять даже дорогостоящие матричные операции на графическом процессоре (GPU).

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

Минусы матрицы смежности

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

Хотя базовые операции просты, такие операции, как inEdges и outEdges, дороги при использовании представления матрицы смежности.

Код матрицы смежности

Если вы знаете, как создавать двумерные массивы, значит вы также знаете, как создать матрицу смежности.

Матрица смежности в C++

Аннотация: Рассматриваются основные математические понятия, связанные с математическими и геометрическими графами, представлением графов, задачами на графах и сетевыми графиками.

Графы и их использование

Многие элементы и их связи удобно изображать не таблицами, а так называемыми графами. Это, хотя и часто связываемые, но все же две различные математические структуры.

Граф определяется двумя множествами V, R, где V — это множество вершин графа (множество элементов), a R — это множество ребер графа или задаваемое в зависимости от элементов V множество связей, отношений между элементами множества V. Любая пара вершин (любое ребро) может быть снабжена числом — весом ребра, которое характеризует отношение между этими вершинами, например, тесноту и важность их связи. Такие графы с весами называют взвешенными графами.

Граф, заданный геометрически (просто геометрический граф), можно изобразить кружками, отождествляемыми с элементами V и соединяющими (в соответствии с заданными отношениями R ) их линиями (ребрами). Ребра плоскостного графа могут пересекаться (зрительно) не только в вершинах, но и вне их.

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

Список смежности

Рис. Ориентированный граф

Пример. Если вершины графа на рис. 1 отождествить с городами,
а ребра — с путями, связывающими их все время «под гору»,
то получим ориентированный граф. Если каждое ребро снабдить
стоимостью бензина на путь, то получим взвешенный граф,
который можно назвать графом стоимости пути между городами
(под гору) или минимальной стоимости переездов. Аналогично можно
построить граф путей «в гору», который не совпадает
с графом «под гору» — как по направлению стрелок,
так и по весам. Если же нас интересуют только веса — длины путей,
то можно изобразить единый взвешенный неориентированный граф путей.

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

Длина пути — число дуг в пути.

Расстоянием между двумя вершинами v1 и v2 графа G называется величина минимального по весам ребер пути из вершины v1 в вершину v2. Пара вершин с ребром, их связывающим, называется дугой и обозначается (i,j) или. Начальная вершина называется истоком, началом дуги, а конечная — стоком, концом дуги. Дуга (i,j) не эквивалентна дуге (j,i). Две вершины смежные, если они соединены дугой. Две дуги смежные, если у них есть общая вершина. Вершина, обозначенная через vk, и дуга (i,j) инцидентны, если эта вершина является началом или концом этой дуги, то есть vk=i или vk=j.

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

Пример. Связный взвешенный граф изображен на рис.

Список смежности

Рис. Связный взвешенный граф

Граф, заданный таблицей инцидентности, — это таблица A элементов aij размером n строк и m столбцов ( n — число вершин графа, m — число ребер графа, i=1,2,. ,n ; j=1,2,. ,m), которая заполняется по правилу: «каждой вершине графа сопоставим строку таблицы, а каждому ребру графа — столбец таблицы». Для неориентированного графа aij=1, если i -ая вершина инцидентна j -ой вершине, и aij=0 — в противном случае. Для ориентированного графа в качестве начальной вершины ставят +1, а для конечной вершины -1. Таблица инцидентности неудобна для обработки, так как она не несет прямой информации о ребрах.

Граф, заданный таблицей смежности, — это таблица B элементов bij размером n строк и n столбцов ( n — число вершин графа), которая заполняется по правилу: bij=1, если i -ая вершина смежна с j -ой вершиной, то есть существует ребро, идущее из вершины i в вершину j, и bij=0, — в противном случае. Таблица смежности неориентированного графа симметрична и удобнее для обработки. Если граф взвешенный, то вместо bij=1 в таблице проставляется вес этого ребра (i,j).

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

Больший эффект имеет в этом плане представление графа списком. Будем называть списком любую упорядоченную последовательность однотипных элементов. Граф представляется списком инциденций. Этот список содержит для любой вершины i список вершин j, таких, что (неориентированный граф). Последняя запись — пара (i,j) списка часто помечается, например, словом «конец» или знаком пустого множества. Начало каждого списка хранится в отдельном списке.

Пример. Для графа, изображенного на рис. 1, таблица инцидентности A и таблица смежности B (она не симметрична, так как ориентирована) имеют вид:

Список смежности

Этот же граф можно определить двумя списками: списком всех вершин (слева) и «привязанного» к каждому элементу этого списка другого списка связанных с ним вершин списка (справа):

Список смежности

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

Пример. Генеалогическое дерево — орграф. Ориентированная дуга соединяет
одного члена семьи с другим, например, по принципу «родитель-сын (дочь)» (рис.

Список смежности

Рис. Генеалогическое дерево двух поколений Ивановых

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

Определение графаГрафы — фундаментальное понятие как в математике, так и в информатике. Проще всего объяснить его с помощью аналогии с дорожной системой. Существует
определённый набор городов, некоторые из которых связаны дорогами, которые
могут быть как односторонними, так и двухсторонними. Вся эта структура и
называется графом. Ну а более формально, граф — комбинация набора вершин и набора рёбер. Вершины — это города, а рёбра — дороги. Визуально граф можно
представить так:

Список смежности

Этот граф состоит из 6 вершин, пронумерованных начиная с единицы, и 7
двухсторонних рёбер. Рёбра обычно записывают в виде пар вершин, которые они
соединяют: (1)-(2), (1)-(5), (2)-(3), (2)-(5), (3)-(4), (4)-(5), (4)-(6). Ориентированные и неориентированные графыМы уже упоминали, что “дороги” в графе могут быть как односторонними, так
и двухсторонними. Для этого свойства существует отдельный термин: односторонние
“дороги” называются ориентированными рёбрами (или дугами), а двухсторонние —
неориентированными. Граф, в котором все рёбра неориентированные, также называют неориентированным,
а граф с ориентированными рёбрами, соответственно, ориентированным. Слева изображён неориентированный граф, а справа — ориентированный. Как
несложно догадаться, левый граф можно обходить как по часовой стрелке, так и
против, а правый можно полностью обойти только по часовой, хотя одно из ребёр в
нём также неориентированное (считается, что это два противоположных
ориентированных ребра). Пути и циклыПутём в графе называется последовательность вершин, каждая из которых
соединена со следующей ребром. Чаще всего под “путём” подразумевают простой
путь, все вершины которого различны. Путь, который проходит через какую-либо
вершину более одного раза называют сложным путём. Если первая вершина пути совпадает с последней, то такой путь называют
циклом. Приведём примеры на этом графе:

Список смежности

Из множества возможных простых путей самый длинный: (a — f — c — d — e — b — h)
(существуют и другие пути с такой же длиной). Циклом является путь (b — c — d — e — b) (выделен цветом). Можно начать и
с любой другой вершины, например, (c — d — e — b — c). Кратные рёбра и петлиСуществует множество разновидностей графов, и среди них встречаются довольно
специфические. В частности, так называемые мультиграфы разрешают наличие между
двумя вершинами нескольких рёбер (называемых кратными рёбрами), а также
наличие петель. Петля — ребро, входящее в ту же вершину, из которой
исходит. Выглядят они следующим образом:

Список смежности

Красным выделены кратные рёбра, а синим — петли. Мультиграфы встречаются в задачах реже чем обычные графы (называемые простыми),
но всё же встречаются, поэтому стоит иметь о них элементарное представление. Связные графыГраф называется связным если между любой парой вершин существует хотя бы
один путь. Как пример рассмотрим следующий граф:

Список смежности

Одно из рёбер проведено штрихами. Если это ребро присутствует, то граф
является связным. Если же его убрать, то связность теряется, граф разбивается
на две части, друг с другом не связанные. Такие части называются компонентами
связности. Определение дереваДерево — вид графа, который можно назвать самым простым, но они
обладают множеством особых свойств и встречаются в задачах чуть ли не чаще
остальных графов. Дерево — это связный граф без циклов, петель и кратных рёбер. Все изображённые графы являются деревьями:

Список смежности

Список смежности

Список смежности

Список смежности

Среди множества свойств деревьев можно выделить два самых известных:

  • Количество рёбер связано с количеством вершин формулой (E = V — 1).
  • Между любой парой вершин существует ровно один путь.

Матрица смежностиВ качестве примера решим простую задачу: для каждой вершины графа выведем
количество рёбер, смежных с ней. Преимущества матрицы смежности:

Недостатки матрицы смежности:

  • Занимает (N^2) памяти, что неприемлемо для достаточно больших графов.
  • Сложность перебора всех вершин, смежных с данной: (O(N))

Список смежностиГораздо чаще для представления графов используется список смежности. Его
идея заключается в хранении для каждой вершины расширяемого массива (вектора),
содержащего всех её соседей. Решим ту же задачу с использованием списка смежности (и С++11 для for-each):

Если требуется также удалять рёбра, то вместо вектора нужно использовать
std::set. Преимущества списка смежности:

  • Использует (O(M)) памяти, что оптимально.
  • Позволяет быстро перебирать соседей вершины.
  • Позволяет за (O(log N)) проверять наличие ребра и удалять его (при использовании std::set).

Недостатки списка смежности:

Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор

В этой статье:

Список смежности (инцидентности)

Взвешенный граф (коротко)

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

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

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

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

Но тем кто знает, но чуть забыл, что такое смежность есть краткое определение.

Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Матрица (назовем ее L) состоит из n строк и n столбцов и поэтому занимает n^2 места.

Каждая ячейка матрицы равна либо 1, либо 0;

Ячейка в позиции L (i, j) равна 1 тогда и только тогда, когда существует ребро (E) между вершинами (V) i и j. Если у нас положение (j, i), то мы также сможем использовать данное правило. Из этого следует, что число единиц в матрице равно удвоенному числу ребер в графе. (если граф неориентированный). Если ребра между вершинами i и j не существует, то ставится 0.

Для практического примера возьмем самый обыкновенный неориентированный граф:

Список смежности

А теперь представим его в виде матрицы:

Список смежности

Ячейки, расположенные на главной диагонали всегда равны нулю, потому что ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней только если мы не используем петли. То есть наша матрица симметрична относительно главной диагонали. Благодаря этому мы можем уменьшить объем памяти, который нам нужен для хранения.

С одной стороны объем памяти будет:

Список смежности

Но используя вышеописанный подход получается:

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

Если граф неориентированный, то, когда мы просуммируем строку или столбец мы узнаем степень рассматриваемой нами вершины.

Если мы используем ориентированный граф, то кое-что меняется.

Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра.

Возьмем в этот раз ориентированный граф и сделаем матрицу смежности для него:

Список смежности

Список смежности

Если мы работаем со строкой матрицы, то мы имеем элемент из которого выходит ребро, в нашем случаи вершина 1 входит в вершину 2 и 8. Когда мы работаем со столбцом то мы рассматриваем те ребра, которые входят в данную вершину. В вершину 1 ничего не входит, значит матрица верна.

Если бы на главной диагонали была бы 1, то есть в графе присутствовала петля, то мы бы работали уже не с простым графом, с каким мы работали до сих пор.

Используя петли мы должны запомнить, что в неориентированном графе петля учитывается дважды, а в ориентированном — единожды.

Инцидентность – понятие, используемое только в отношении ребра и вершины: две вершины (или два ребра) инцидентными быть не могут.

Матрица (назовем ее I) состоит из n строк которое равно числу вершин графа, и m столбцов, которое равно числу ребер. Таким образом полная матрица имеет размерность n x m. То есть она может быть, как квадратной, так и отличной от нее.

Ячейка в позиции I (i, j) равна 1 тогда, когда вершина инцидентна ребру иначе мы записываем в ячейку 0, такой вариант представления верен для неориентированного графа.

Сразу же иллюстрируем данное правило:

Список смежности

Список смежности

Сумма элементов i-ой строки равна степени вершины.

При ориентированным графе, ячейка I (i, j) равна 1, если вершина V (i) начало дуги E(j) и ячейка I (i, j) равна -1 если вершина V (i) конец дуги E (j), иначе ставится 0.

Список смежности

Список смежности

Одной из особенностей данной матрицы является то, что в столбце может быть только две ненулевых ячейки. Так как у ребра два конца.

При суммировании строки, ячейки со значением -1, могут складываться только с ячейками, также имеющими значение -1, то же касается и 1, мы можем узнать степень входа и степень выхода из вершины. Допустим при сложении первой вершины, мы узнаем, что из нее исходит 1 ребро и входят два других ребра. Это является еще одной особенностью (при том очень удобной) данной матрицы.

Список смежности подразумевает под собой, то что мы работаем с некоторым списком (массивом). В нем указаны вершины нашего графа. И каждый из них имеет ссылку на смежные с ним вершины.

Список смежности

В виде списка это будет выглядеть так:

Список смежности

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

Так как здесь рассматривается смежность, то здесь не обойдется без дублирования вершин. Поэтому сумма длин всех списков считается как:

Когда мы работаем с ориентированным графом, то замечаем, что объем задействованной памяти будет меньше, чем при неориентированном (из-за отсутствия дублирования).

Список смежности

В виде списка:

Список смежности

Сумма длин всех списков:

Со списком инцидентности все просто. Вместо вершин в список (массив) вы вставляете рёбра и потом делаете ссылки на те вершины, с которыми он связан.

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

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

К примеру, возьмем граф с весами на ребрах:

Список смежности

И сделаем матрицу смежности:

Список смежности

В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.

Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.

Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.

Представление списка смежности

Граф и его эквивалентное представление списка смежности показаны ниже.

Список смежности

Список смежности эффективен с точки зрения хранения, потому что нам нужно хранить только значения для ребер. Для разреженного графа с миллионами вершин и ребер это может означать много сэкономленного пространства.

Структура списка смежности

Самому простому списку смежности требуется структура данных узла для хранения вершины и структура данных графа для организации узлов.

Давайте рассмотрим структуру данных ниже.

Не позволяйте struct node*

adjLists ошеломить вас. Нам нужно сохранить указатель struct node. Потому, как мы не знаем, сколько вершин будет в графе, и поэтому не можем создать массив связанных списков во время компиляции.

Код списка смежности в C

  • Смежность.

    Говорят, что вершина смежна с другой вершиной, если есть ребро, соединяющее их.

    Вершины 2 и 3 не являются смежными, потому что между ними нет ребра.

  • Путь.

    Последовательность ребер, которая позволяет вам перейти от вершины A к вершине B, называется путем.

    0-1, 1-2 и 0-2 являются путями от вершины 0 до вершины 2.

  • Ориентированный граф.

    Граф, в котором есть ребро (u, v) не обязательно означает, что также имеется ребро (v, u). Ребра в таком графике представлены стрелками, чтобы показать направление ребра.

Способы представления графа

Графы обычно представлены двумя способами:

Матрица смежности

— это двумерный (2D) массив V x V вершин. Каждая строка и столбец представляют вершину.

Матрица смежности для графа, который мы создали выше.

Список смежности

Поскольку это неориентированный граф, для ребра (0,2) нам также нужно отметить ребро (2,0), делая матрицу смежности симметричной относительно диагонали.

Поиск ребер (проверка, существует ли ребро между вершиной A и вершиной B), чрезвычайно быстр в представлении матрицы смежности, но мы должны зарезервировать пространство для каждой возможной связи между всеми вершинами (V x V), поэтому для этого требуется больше места.

Список смежности

Список смежности

представляет собой граф в виде массива связанного списка.

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

Список смежности для графа, который мы создали в первом примере, выглядит следующим образом:

Список смежности

Список смежности эффективен с точки зрения хранения, потому что нам нужно хранить только значения для ребер. Для графа с миллионами вершин это может означать много сэкономленного пространства.

Список смежности Java

Мы используем Java Collections для хранения массива связанных списков.

Тип LinkedList определяет, какие данные вы хотите сохранить в нем. Для помеченного графа вы можете хранить словарь вместо целого значения.

Список смежности Python

Есть причина, по которой Python получает так много «любви». Простой словарь вершин и его ребер является достаточным представлением графа. Вы можете сделать вершину настолько сложной, насколько захотите.

Список смежности C ++

Это та же самая структура, но с помощью встроенного списка структур данных STL в C ++ мы делаем структуру немного чище. Мы также можем абстрагировать детали реализации.