Итак, вы новичок в структурах данных и узнали о связанных списках и бинарных деревьях, но что такое графы ?!

Привет, графики

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

Графики состоят из двух основных частей:
1. Вершины - где хранятся фактические данные (также известные как узлы)
2. Края - линии, соединяющие вершины

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

Помимо направления, ребра также могут иметь вес. Обычно (хотя и не обязательно) число от 0 до 1, вес ребра просто обозначает значение или стоимость, связанную с отношением этих двух вершин.

Представьте себе сеть из 4 человек: Алиса и Бет - лучшие друзья - они постоянно болтают и общаются каждый день. Бет и Хлоя друзья, но не так близки и общаются лишь изредка. Диана - это та девушка, которую Бет и Хлоя встретили однажды на вечеринке и больше никогда не видели. Мы можем представить, что взвешенный график их сети будет выглядеть примерно так:

Отличным примером использования взвешенного графика для представления физической сети являются Google Maps. Когда вы наносите на карту маршруты между двумя точками (вершинами), Google Maps часто предлагает более одного варианта маршрута. Эти маршруты представляют собой ребра, которые имеют разные значения (веса), связанные с каждым из них, в зависимости от ряда факторов, включая расстояние и время в пути. Учитывая вес, Google Maps выделит и предложит самый быстрый маршрут синим цветом.

Требуется еще одно реальное применение графика? Итак, вы смотрите на один прямо сейчас. Вся сеть представляет собой график! Это огромная и сложная сеть страниц, которые указывают друг на друга. Когда мы перемещаемся между URL-адресами, мы на самом деле просто переходим к вершинам и обратно. Некоторые края ориентированы (вы можете переходить только от одной страницы к другой, но не наоборот), а некоторые - нет (вы можете свободно перемещаться вперед и назад между ними). Сногсшибательно, правда?

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

Два распространенных способа представления графа: 1) список смежности и 2) матрица смежности. У обоих есть свои плюсы и минусы, но в целом матрицы смежности используются для плотных графов (графов с множеством ребер), а списки смежности используются для разреженных графов (графов с несколькими ребрами).

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

Реализация матрицы смежности представляет все ребра между всеми узлами, независимо от того, существуют они или нет. 0 означает отсутствие соединения, а 1 означает, что связь между этими двумя узлами существует. Элементы в матрице также могут показывать направление - например, на приведенном ниже графике край между A и B существует только в одном направлении, и, следовательно, в матрице смежности (A, B) равно 0, но (B, A) равно 1.

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

Большой O: список против матрицы

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

Однако для большинства приложений графов список смежности является достаточным и наиболее подходящим.

Основные выводы

  1. Графы - это набор вершин и ребер, которые представляют данные и их отношения.
  2. Графики можно использовать для всех типов сетей (социальных, физических и т. Д.) - реальные приложения включают Facebook и Google Maps.
  3. В большинстве случаев лучше использовать список смежности.

Надеюсь, теперь вы лучше понимаете графики, но имейте в виду, что это только верхушка айсберга. Есть причина, по которой крупные компании, такие как LinkedIn, Google и Facebook, в значительной степени полагаются на графики - прочтите о причинах перехода Facebook в 2007 году от реляционных баз данных к графическим базам данных здесь или о масштабировании баз данных LinkedIn здесь.

Вперед!

  1. У freeCodeCamp есть отличное введение для фактической реализации структуры данных графа с помощью Javascript.
  2. Получите быструю практику с учебником по графическому представлению Khan Academy.
  3. Хотите получить более подробную информацию о списках и матрицах смежности? Прочтите статью Вайдехи Джоши о графическом представлении, в котором потрясающе хорошо разбираются концепции!
  4. Все еще хотите большего? Пойдите для глубоких вещей здесь.