Список смежности и матричное представление графа
Хотя они выглядят по-разному, все типы графиков можно представить аналогичным образом. Обычно существует два типа представления графов:
- Матрица смежности
- Список смежности
Список смежности
Список смежности состоит из связанных списков. Каждая вершина считается индексом массива, а каждый элемент представляет собой связанный список. Эти связанные списки содержат вершины, у которых есть ребра с индексной вершиной.
Вот пример списка смежности:
Допустим, граф содержит 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 означает количество узлов в графике.