A            A -- B      
       / \           |    |       
      B - C          D -- C

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

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

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

Матрица смежности — это не что иное, как двумерный массив. где количество строк и столбцов равно количеству узлов в графе. Каждая строка и столбец являются соответствующими узлами в графе. Каждое значение матрицы зависит от того, существует ли путь между двумя узлами (строка и столбец). Если путь существует, значение равно 1, иначе 0. Ниже приведен пример графа из трех узлов.

      A                                       
     / \          
    B - C    
        A B C              
     A  0 1 1
     B  1 0 1
     C  1 1 0
   Adjacency matrix

Для строки A нет пути к A, поэтому значение равно 0. Есть путь к B и C поэтому значение в столбцах B и C для строки A равно 1. То же самое для остальных узлов.

Нет пути между узлом и самим собой. Таким образом, значение равно 0. Такой путь возможен, если есть петля от узла к самому себе. В этом случае значение для строки A и столбца B будет равно 1.

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

В списке смежности мы поддерживаем список соседей (где существует путь от этого узла) для каждого узла в графе.

      A -- B        A : [B,D]   
      |    |        B : [C,D] 
      D -- C        C : [B,D]
                    D : [A,C]
                     Adjacency list

Последнее представление называется списком смежности. Это как пара ключ-значение. Чтобы собрать все узлы вместе со списками, мы можем использовать Hash Map.

 graph = {
        A : [B,C,D]
        B : [A,C,D] 
        C : [A,B,D]
        D : [A,B,C]
    }

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

Пространство, занимаемое матрицей, равно размеру двумерного массива размером v строк и v столбцов.

количество строк * количество столбцов

или O(V * V) v = количество вершин

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

Пространственный анализ списка смежности

В худшем случае могут быть ребра от каждого узла к другому узлу, где пространство будет O (V * V-1) или O (v ^ 2). Но в среднем это занимает меньше места по сравнению с этой матрицей смежности. что равно O(V + E). V - нет вершин, а E - нет ребер.