Список смежности и матричное представление графа

Хотя они выглядят по-разному, все типы графиков можно представить аналогичным образом. Обычно существует два типа представления графов:

  1. Матрица смежности
  2. Список смежности

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

Список смежности состоит из связанных списков. Каждая вершина считается индексом массива, а каждый элемент представляет собой связанный список. Эти связанные списки содержат вершины, у которых есть ребра с индексной вершиной.

Вот пример списка смежности:

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

Допустим, граф содержит V вершин и E ребер.

Как правило, пространственная сложность будет равна O(V + E).

В худшем случае пространственная сложность составит O(V2) если данный граф является полным графом

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

Матрица смежности представляет собой двумерный массив. Граф, имеющий число вершин V, размер матрицы будет VxV.

Сказать, matrix[i][j] = 5. Это означает, что между узлами i и j есть ребро, вес которого равен 5.

Давайте посмотрим на следующий график и его матрицу смежности:

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

Мы создали 2D массив используя эти шаги:

Шаг 1) Вершина A имеет прямое ребро с B, а вес равен 5. Таким образом, ячейка в строке A и столбце B будет заполнена цифрой 5. Остальные ячейки строки A будут заполнены нулями.

Шаг 2) Вершины B имеют прямое ребро с C, а вес равен 4. Таким образом, ячейка в строке B и столбце C будет заполнена цифрой 4. Остальные ячейки в строке B будут заполнены нулями, поскольку B не имеет исходящего ребра ни к какому другие узлы.

Шаг 3) Вершины C не имеют прямых ребер с другими вершинами. Итак, строка C будет заполнена нулями.

Шаг 4) Вершина D имеет направленное ребро с A и C.

  • Здесь ячейка в строке D и столбце A будет иметь значение 7. Ячейки в строке D и столбце C будут иметь значение 2.
  • Остальные ячейки строки D будут заполнены нулями.

Шаг 5) Вершины E имеют направленное ребро с B и D. Ячейка в строке E и столбце B будет иметь значение 6. Ячейки в строке E и столбце D будут иметь значение 3. Остальные ячейки в строке D будут заполнено нулями.

Вот некоторые моменты, на которые следует обратить внимание:

  • Граф не имеет циклов, если главная диагональ матрицы смежности равна 0.
  • Граф является ориентированным, если индексы (a,b) и (b,a) не имеют одинакового значения. В противном случае граф является ориентированным графом.
  • График будет взвешенным, если значение ячеек больше 1.

Есть некоторая проблема с матрицей смежности, поскольку она требует квадратов пробелов. Здесь мы сохраняем ребра, которые не соединены. Эти края выделяют пространство в памяти.

Например, если у нас есть граф со 100 узлами, то для его хранения в Оперативная память. При меньшем количестве ребер в графе выделение такой большой памяти может быть пустой тратой. Таким образом, сложность пространства с использованием матрицы смежности будет O(N2), где N означает количество узлов в графике.