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

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

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

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

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

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

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

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

Как правило, космическая связьplexэто будет O(V + E).

Наихудший случай в космосеplexэто будет O(V2) если данный граф является полным графом

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

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

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

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

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

Мы создали 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) не имеют одинакового значения. Другойwise, Граф является ориентированным графом.
  • График будет взвешенным, если значение ячеек больше 1.

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

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