Структуры данных — это просто способы организации данных.

Я уверен, что вы знакомы с списком или массивом, линейной упорядоченной последовательностью значений. Это ваш список покупок, ваших дел, чтения, чего угодно.

Давайте познакомимся с еще более захватывающей областью нелинейных графиков!

Но сначала немного основ:

Граф состоит из объектов, соединенных линиями.

В JavaScript (и информатике в целом) мы называем эти объекты и линии вершинами и ребрами.

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

Двумя общими свойствами ребер являются веса и направление.

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

Сьюзен может быть влюблена в Салли, но это не значит, что Салли влюблена в Сьюзен.

А теперь представьте, что вы парите в космосе в полном одиночестве. У вас много знаний, а поделиться ими не с кем.

Появляется другой космический путешественник: «Эй, друг! Давайте поддерживать связь». Вы даете им свой номер, и вдруг вы обретаете смысл и перестаете быть единственной пылинкой в ​​пространстве. Вы стали узлом и создали связующее ребро.

Но это стоит вам.

Каждый раз, когда вы звоните своему космическому другу, ваша телефонная компания выставляет вам счет в размере 1 239 3900,00 долларов США. Это вес вашего соединительного ребра.

Давайте вернемся из космоса и посмотрим на структуры данных графа IRL.

Классический пример — карты Google. Это всего лишь один большой график!

Пересекающиеся улицы — вершины, а сами улицы — ребра.
Они взвешиваются по расстоянию по длине и времени. У улиц также есть свойство направленность… некоторые улицы идут только в одну сторону.

Обход графа относится к поиску пути между двумя узлами, поиску кратчайшего пути от одного узла к другому и поиску кратчайшего пути, который посещает все узлы [1].

Одним из многих методов обхода графа является использование алгоритма Дейкстры (или алгоритма поиска кратчайшего пути Дейкстры, алгоритма SPF). Это тот, который Google использовал (или его вариант) для реализации своего картографического приложения. Этот алгоритм был первоначально придуман Дейкстрой в 1958 году за 20 минут в парижском кафе [2].

Вот как это выглядит в Javascript:

Заметка о древовидных графиках…

То генеалогическое древо, которое тебе пришлось составить в детском саду? Ага, древовидный график.

Дело в том, что древовидные графы — это узкоспециализированная форма графа с корневым узлом, потомками которого являются все остальные узлы.

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

Таким образом, в JavaScript они считаются совершенно разными структурами данных.

Графики — это неиерархические структуры взаимосвязи данных, соединяющие весь наш мир!

Заглавное изображение: визуализация анализа социальных сетей [Grandjean, M. (2016)]
[1] https://www.jenniferbland.com/the-difference-between-a-tree-and-a-graph- data-structure/
[2] https://www.vice.com/en_us/article/4x3pp9/the-simple-элегантный-алгоритм-который-делает-google-maps-возможным

Первоначально опубликовано на https://dev.to 29 сентября 2019 г.