Графы и их представление.

Определение

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

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

1. Список ребер (Edge List): В этом представлении графа хранится список всех ребер. Каждое ребро представляется парой вершин, которые оно соединяет. Если граф взвешенный, то кроме пары вершин хранится также вес ребра.

[(0, 1), (1, 2), (2, 3)]

2. Список смежности (Adjacency List): В этом представлении для каждой вершины хранится список вершин, с которыми она соединена. Это обеспечивает быстрый доступ к соседним вершинам. Если граф взвешенный, то помимо соседних вершин может храниться также информация о весах ребер.

{
  0: [1],
  1: [0, 2],
  2: [1, 3],
  3: [2],
}

3. Матрица смежности (Adjacency Matrix): В этом представлении используется двумерная матрица, где строки и столбцы соответствуют вершинам графа. Если вершины i и j соединены ребром, то элемент матрицы в позиции (i, j) будет равен 1 (или весу ребра). В невзвешенных графах можно использовать булевы значения.

[
  [0, 1, 0, 0],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [0, 0, 1, 0],
]