Давайте поговорим об очень распространенной и широко используемой структуре данных, Graphs. К сожалению, это не те графики, к которым мы привыкли в математике с начальной школы. Однако они столь же полезны при расшифровке отношений между двумя или более объектами. Это одна из наиболее часто используемых и полезных структур данных для моделирования реальной жизни в информатике.

В социальных сетях Facebook использует графики для отображения дружеских отношений, Linkedin использует графики для отображения связей и т. Д. Когда вы пытаетесь найти самый быстрый или лучший путь из точки A в точку B, скажем, на Google Maps, их системы используют графики. Вы когда-нибудь задумывались, как Amazon рекомендует вам похожие товары на основе истории поиска или покупок? Графики. Netflix, Spotify, множество приложений на основе рекомендаций; Графики !!

Так что же такое графики?

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

Граф - это набор значений, связанных попарно.
Узел / вершина, соединенные ребрами

Типы графиков

Графы можно описать тремя основными способами.

  1. Направленные и ненаправленные: графики можно считать направленными или ненаправленными в зависимости от того, как пересекаются их узлы. В ориентированных графах узлы, соединенные ребром, двунаправлены. Если узлы A и B соединены ребром, мы можем пройти от A к B и от B к A. Facebook - неориентированный граф, друг A связан с другом B и наоборот.
    В ориентированном графе обход выполняется только в одном направлении. Twitter и Instagram - хорошие примеры ориентированных графов; человек A может следовать за человеком B, а человек B не должен следовать за ним.
  2. Взвешенные и невзвешенные. Мы уже можем представить узлы графа, несущие какую-то ценность или информацию. В графах ребра тоже несут информацию. Когда это происходит, их называют взвешенными графами. Когда это не так, они считались невзвешенными. Взвешенные графики используются Google для расчета наиболее оптимального пути.
  3. Циклические и ациклические: когда вершины соединены в цикл, они считаются циклическими. Циклические графы очень распространены в взвешенных графах, таких как Google Maps. Вы можете искать направления из точки A в точку B в точку C и возвращаться в точку A из точки C, не проезжая через точку A.

Построение графиков / управление данными графика

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

  1. Edge List: первый подход (метод) - подход Edge List. Список ребер просто показывает соединения вершин друг с другом. На нашем графике выше мы можем представить его, используя список ребер как таковой:
const graph = [[0,1], [0,2], [1,2], [1,3], [2,4], [3,4], [4,5], [5,6]]

Узел 0 подключен к узлу 1, узел 0 также подключен к узлу 2, узел 1 - 2, снова 1 - к 3, 2 - 4 и так далее. Простой.

2. Смежность / смежный список: при описании графов с использованием смежности или смежных списков мы можем использовать массивы, объекты или связанные списки для представления графа. Конкретный индекс графа - это узел, а значения - это соседи узла или узлы, с которыми он связан. Скажем, мы должны были использовать массив для построения нашего графика выше, мы бы представили его как таковой:

const graph = [[1,2], [0,2,3], [0,1,4], [1,4], [2,3,5], [4,6], [5]]

В индексе 0, который является узлом 0, узлы, подключенные к 0, являются узлами 1 и 2, представленными в нашем массиве графов с индексом 0. В индексе 1 узел подключен к узлам 0, 2 и 3. В точке 2 мы имеют соседей 0, 1 и 4. На 6 у нас есть одно соединение с узлом 5.

3. Смежная матрица: при описании графов с использованием смежных матриц нули и единицы используются для определения того, имеет ли узел x соединение с узлом y.

const graph = [
  [0, 1, 1, 0, 0, 0, 0],
  [1, 0, 1, 1, 0, 0, 0],
  [1, 1, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0],
  [0, 0, 1, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 1],
  [0, 0, 0, 0, 0, 1, 0]
]

Узел 0 связан с узлами 1 и 2, представленными на нашем графике цифрами 1. Узел 1 имеет соединение с узлами 0, 2 и 3. Единственное соединение узла 6 - 5, как показано одной единицей в этом массиве.

Реализация

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

class Graph { 
  constructor() { 
    this.numberOfNodes = 0; 
    this.adjacentList = {}; 
  }
}

Как обычно, мы начинаем с шаблона, состоящего из класса графа, который поставляется с конструктором. В конструкторе мы устанавливаем количество узлов равным 0, а в соседнем списке - пустой объект.

//adding a vertex (node)
addVertex(node)  { 
    this.adjacentList[node] = []; 
    this.numberOfNodes++;
}

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

//adding edges
addEdge(node1, node2) { 
    this.adjacentList[node1].push(node2); 
    this.adjacentList[node2].push(node1); 
}

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

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

Сначала добавим 6 узлов:

let ourGraph = new Graph();
ourGraph.addVertex('0');
ourGraph.addVertex('1');
ourGraph.addVertex('2');
ourGraph.addVertex('3');
ourGraph.addVertex('4');
ourGraph.addVertex('5');
ourGraph.addVertex('6');

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

ourGraph.addEdge('0', '1'); 
ourGraph.addEdge('0', '2'); 
ourGraph.addEdge('1', '0'); 
ourGraph.addEdge('1', '2'); 
ourGraph.addEdge('1', '3');