Структура данных графика

В этом руководстве вы узнаете, что такое структура данных графика. Кроме того, вы найдете представления графа.

Структура данных графа - это набор узлов, которые имеют данные и подключены к другим узлам.

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

Каждое отношение - это переход от одного узла к другому. Публикуете ли вы фотографию, присоединяетесь к группе, например к странице и т. Д., Для этих отношений создается новое преимущество.

Пример структуры данных графика

Тогда весь facebook - это совокупность этих узлов и ребер. Это потому, что facebook использует структуру данных графа для хранения своих данных.

Точнее, граф - это структура данных (V, E), состоящая из

Набор вершин V
Набор ребер E, представленных в виде упорядоченных пар вершин (u, v)

Вершины и ребра

На графике

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Терминология графа

Смежность : Вершина называется смежной с другой вершиной, если их соединяет ребро. Вершины 2 и 3 не смежны, потому что между ними нет ребра.
Путь : последовательность ребер, которая позволяет перейти от вершины A к вершине B, называется путем. 0-1, 1-2 и 0-2 - это пути от вершины 0 к вершине 2.
Направленный граф : граф, в котором ребро (u, v) не обязательно означает, что есть ребро (v, u). Ребра в таком графе представлены стрелками, указывающими направление ребра.

Графическое представление

Графики обычно представлены двумя способами:

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

Матрица смежности - это двумерный массив из V x V вершин. Каждая строка и столбец представляют собой вершину.

Если значение любого элемента a(i)(j)равно 1, это означает, что существует ребро, соединяющее вершину i и вершину j.

Матрица смежности для созданного выше графа имеет вид

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

Поскольку это неориентированный граф, для ребра (0,2) нам также нужно отметить ребро (2,0); сделать матрицу смежности симметричной относительно диагонали.

Поиск ребер (проверка наличия ребра между вершиной A и вершиной B) чрезвычайно быстр в представлении матрицы смежности, но мы должны зарезервировать место для каждой возможной связи между всеми вершинами (V x V), поэтому для этого требуется больше места.

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

Список смежности представляет собой граф в виде массива связанных списков.

Индекс массива представляет вершину, и каждый элемент в его связанном списке представляет другие вершины, которые образуют ребро с вершиной.

Список смежности для графа, который мы создали в первом примере, выглядит следующим образом:

Представление списка смежности

Список смежности эффективен с точки зрения хранения, потому что нам нужно хранить только значения для краев. Для графа с миллионами вершин это может означать много сэкономленного места.