Share This
Связаться со мной
Крути в низ
Categories
//☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Граф – сложная нелинейная структура данных, отображающая связи между разными объектами. Разбираемся, как ее представить и как с ней работать в JavaScript.

rasprostranennye algoritmy i struktury dannyh v javascript grafy 224ddc1 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

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

Другие статьи цикла:

  • Часть 1. Основные понятия и работа с массивами
  • Часть 2. Стеки, очереди и связные списки
  • Часть 3. Деревья

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy 7a575da - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Пример графа.

Количество вершин определяет порядок графа, а количество ребер – его размер.

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

Значение и применение структуры

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy 6591a0c - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Схема метро также является графом.

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

С помощью графов можно представить связи между пользователями социальной сети (подписки) или ссылки между разными страницами одного сайта (перелинковка). В таких графах ребра будут иметь направление – пользователь А подписан на пользователя Б, а не наоборот. Это ориентированные графы.

Любой набор объектов, между которыми есть связи, можно изобразить в виде графа.

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

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

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

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

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

При его составлении для ориентированного графа важно учитывать направление ребер.

rasprostranennye algoritmy i struktury dannyh v javascript grafy 1a4f1ea - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Для первого (неориентированного) графа список смежности будет выглядеть так:

         const graph = {   1: [2,4],   2: [1,3,4],   3: [2,4]   4: [1,2,3] }      

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

  • из вершины 1 можно попасть в 2 и 4;
  • из вершины 2 можно попасть в 1, 3 и 4;
  • из вершины 3 можно попасть в 2 и 4;
  • из вершины 4 можно попасть в 1, 2, 3.

Ориентированный граф выглядит почти так же, но список смежности у него другой:

         const graph = {   1: [2],   2: [3,4],   3: [],   4: [1,3] }      

Из вершины 3 не выходит ни одно ребро, поэтому из нее нельзя никуда попасть – ее массив смежных вершин пуст.

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

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy 148496b - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Матрица смежности для неориентированного (слева) и ориентированного (справа) графа.

Связь определяется построчно. Первая строка соответствует вершине 1, нужно определить, есть ли путь из нее в вершины, представленные столбцами таблицы.

У неориентированного графа матрица смежности симметрична, а у ориентированного – нет.

На JavaScript граф можно представить в виде двумерного массива:

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

Сравнение способов

Список смежности – более компактный способ представления графа, он требует меньше памяти и особенно удобен для “разреженных” графов, у которых немного ребер.

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

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

Например, операция проверки наличия связи между двумя вершинами a и b в матрице занимает константное время – достаточно лишь проверить элемент graph[a][b]. В списке смежности же это будет сложнее – потребуется поиск элемента b в массиве graph[a].

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

Реализация на JavaScript

Напишем класс для самого простого неориентированного графа с хранением данных в виде списка смежности.

         class Graph {   constructor() {     this.vertices = {}; // список смежности графа   }      addVertex(value) {     if (!this.vertices[value]) {       this.vertices[value] = [];     }   }      addEdge(vertex1, vertex2) {     if (!(vertex1 in this.vertices) || !(vertex2 in this.vertices)) {       throw new Error('В графе нет таких вершин');     }      if (!this.vertices[vertex1].includes(vertex2)) {       this.vertices[vertex1].push(vertex2);     }     if (!this.vertices[vertex2].includes(vertex1)) {       this.vertices[vertex2].push(vertex1);     }   } }      

Основные методы графа:

  • addVertex – добавление новой вершины;
  • addEdge – добавление нового ребра.

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

Основные алгоритмы на графах

Алгоритмов работы с графами очень много.

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

  • 🌌 10 анимированных алгоритмов на графах

Обход графа

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

Создадим тестовый граф для демонстрации работы алгоритмов:

rasprostranennye algoritmy i struktury dannyh v javascript grafy 07f3904 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Пример простого неориентированного графа с одной изолированной вершиной.

Перенесем его представление в JavaScript:

         const graph = new Graph();  graph.addVertex('A'); graph.addVertex('B'); graph.addVertex('C'); graph.addVertex('D'); graph.addVertex('E'); graph.addVertex('F'); graph.addVertex('G'); graph.addVertex('H');  graph.addEdge('A', 'B'); graph.addEdge('A', 'C'); graph.addEdge('C', 'D'); graph.addEdge('C', 'E'); graph.addEdge('A', 'F'); graph.addEdge('F', 'G');     

Поиск в глубину (depth-first search)

Алгоритм поиска в глубину движется последовательно по ветвям графа от начала до конца.

rasprostranennye algoritmy i struktury dannyh v javascript grafy 778e7d7 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Визуализация поиска в глубину в графе.

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

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

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

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

  1. Берем вершину с конца стека. В соответствии с описанием структуры данных стек это будет вершина, добавленная в него последней.
  2. Получаем все ее смежные вершины.
  3. Отбрасываем те вершины, которые уже были посещены ранее.
  4. Остальные отмечаем как посещенные, добавляем в стек и возвращаемся к пункту 1.

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy eeceda8 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Порядок обхода вершин графа алгоритмом поиска в глубину.

На JavaScript это может выглядеть так:

         class Graph {   // ..    dfs(startVertex, callback) {     let list = this.vertices; // список смежности     let stack = [startVertex]; // стек вершин для перебора     let visited = { [startVertex]: 1 }; // посещенные вершины          function handleVertex(vertex) {       // вызываем коллбэк для посещенной вершины       callback(vertex);              // получаем список смежных вершин       let reversedNeighboursList = [...list[vertex]].reverse();             reversedNeighboursList.forEach(neighbour => {         if (!visited[neighbour]) {           // отмечаем вершину как посещенную           visited[neighbour] = 1;           // добавляем в стек           stack.push(neighbour);         }       });     }          // перебираем вершины из стека, пока он не опустеет     while(stack.length) {       let activeVertex = stack.pop();       handleVertex(activeVertex);     }          // проверка на изолированные фрагменты     stack = Object.keys(this.vertices);      while(stack.length) {       let activeVertex = stack.pop();       if (!visited[activeVertex]) {         visited[activeVertex] = 1;         handleVertex(activeVertex);       }     }   } }      

Несколько важных моментов:

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

Запустим этот метод для нашего тестового графа:

         graph.dfs('A', v => console.log(v));      

Порядок перебора вершин:

         A -> B -> C -> D -> E -> F -> G -> H     

rasprostranennye algoritmy i struktury dannyh v javascript grafy 45f6e0d - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Порядок перебора вершин алгоритмом поиска в глубину.

Поиск в глубину напоминает поиск пути в лабиринте, алгоритм идет по ветке, пока не упрется в “стену”, после этого он возвращается назад.

Поиск в ширину (breadth-first-search)

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy 9bcada6 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

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

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

  1. Берем вершину с начала очереди. В соответствии с описанием структуры данных очередь это будет вершина, добавленная в нее самой первой.
  2. Получаем все ее смежные вершины.
  3. Отбрасываем те вершины, которые уже были посещены ранее.
  4. Остальные отмечаем как посещенные, добавляем в стек и возвращаемся к пункту 1.

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy bd58baf - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Порядок обхода вершин графа алгоритмом поиска в ширину.

На JavaScript поиск в ширину выглядит примерно так:

         class Graph {   // ..    bfs(startVertex, callback) {     let list = this.vertices; // список смежности     let queue = [startVertex]; // очередь вершин для перебора     let visited = { [startVertex]: 1 }; // посещенные вершины          function handleVertex(vertex) {       // вызываем коллбэк для посещенной вершины       callback(vertex);              // получаем список смежных вершин       let neighboursList = list[vertex];              neighboursList.forEach(neighbour => {         if (!visited[neighbour]) {           visited[neighbour] = 1;           queue.push(neighbour);         }       });     }              // перебираем вершины из очереди, пока она не опустеет     while(queue.length) {       let activeVertex = queue.shift();       handleVertex(activeVertex);     }          queue = Object.keys(this.vertices);      // Повторяем цикл для незатронутых вершин     while(queue.length) {       let activeVertex = queue.shift();       if (!visited[activeVertex]) {         visited[activeVertex] = 1;         handleVertex(activeVertex);       }     }   } }      

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

После перебора основного дерева обязательно повторяем процедуру для всех изолированных вершин.

Запустим этот метод для нашего тестового графа:

         graph.bfs('A', v => console.log(v));     

Порядок перебора вершин:

         A -> B -> C -> F -> D -> E -> G -> H     

rasprostranennye algoritmy i struktury dannyh v javascript grafy a9624c6 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Порядок перебора вершин алгоритмом поиска в ширину.

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

Поиск кратчайшего пути

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

Вариантов постановки этой задачи очень много, мы начнем с самого простого.

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy 4508422 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Пример неориентированного графа.

Например, в этом графе из точки A в точку G можно попасть тремя разными способами. Как выяснить, какой из них самый быстрый?

Сначала создадим JavaScript-представление этой структуры:

         let graph = new Graph(); graph.addVertex('A'); graph.addVertex('B'); graph.addVertex('C'); graph.addVertex('D'); graph.addVertex('E'); graph.addVertex('F'); graph.addVertex('G'); graph.addVertex('H');  graph.addEdge('A', 'B'); graph.addEdge('B', 'F'); graph.addEdge('F', 'G'); graph.addEdge('A', 'C'); graph.addEdge('C', 'D'); graph.addEdge('D', 'F'); graph.addEdge('C', 'E'); graph.addEdge('E', 'F');     

Для решения нашей задачи подойдет уже знакомый нам алгоритм поиска в ширину с некоторыми модификациями.

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

         class Graph {   // ..    bfs2(startVertex) {     let list = this.vertices;      let queue = [startVertex];     let visited = { [startVertex]: 1 };           // кратчайшее расстояние от стартовой вершины     let distance = { [startVertex]: 0 };      // предыдущая вершина в цепочке     let previous = { [startVertex]: null };      function handleVertex(vertex) {       let neighboursList = list[vertex];        neighboursList.forEach(neighbour => {         if (!visited[neighbour]) {           visited[neighbour] = 1;           queue.push(neighbour);           // сохраняем предыдущую вершину           previous[neighbour] = vertex;           // сохраняем расстояние            distance[neighbour] = distance[vertex] + 1;         }       });     }      // перебираем вершины из очереди, пока она не опустеет     while(queue.length) {       let activeVertex = queue.shift();       handleVertex(activeVertex);     }          return { distance, previous }   } }     

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

Опробуем обновленный алгоритм:

         let data = graph.bfs2('A');  /* {   distance: {     A: 0,     B: 1,     C: 1,     D: 2,     E: 2,     F: 2,     G: 3   },   previous: {     A: null,     B:'A',     C:'A',     D:'C',     E: 'C',     F:'B',     G: 'F'   }, } */      

В свойстве distance хранятся кратчайшие расстояния от вершины А до всех остальных вершин графа. Выходит, что до вершины G можно добраться всего за три шага. А восстановить этот путь поможет свойство previous, которое хранит всю цепочку шагов:

         class Graph {    // ...     findShortestPath(startVertex, finishVertex) {     let result = this.bfs2(startVertex);      if (!(finishVertex in result.previous))          throw new Error(`Нет пути из вершины ${startVertex} в вершину ${finishVertex}`);              let path = [];          let currentVertex = finishVertex;          while(currentVertex !== startVertex) {       path.unshift(currentVertex);       currentVertex = result.previous[currentVertex];     }          path.unshift(startVertex);          return path;   } }     

Запустим алгоритм поиска:

         graph.findShortestPath('A', 'G'); // ['A', 'B', 'F', 'G'] graph.findShortestPath('A', 'Z'); // Error: Нет пути из вершины A в вершину Z     

Взвешенные графы

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

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy 24b6372 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Карта метро – пример взвешенного графа.

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

Представление взвешенного графа

Для взвешенного графа необходимо хранить не только факт связи, но и вес ребра, соединяющего две вершины.

Попробуем перенести в JavaScript вот такой граф:

rasprostranennye algoritmy i struktury dannyh v javascript grafy 1248955 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Ориентированный взвешенный граф.

Если мы используем матрицу смежности, то веса можно подставлять вместо единиц и нулей (наличие или отсутствие связи).

A B C D E F G
A 0 2 1 0 0 0 0
B 0 0 0 0 0 7 0
C 0 0 0 5 2 0 0
D 0 0 0 0 0 2 0
E 0 0 0 0 0 1 0
F 0 0 0 0 0 0 1
G 0 0 0 0 0 0 0

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

         let graph = {   a: [ [b, 2], [c, 1] ],   b: [ [f, 7] ],   c: [ [d, 5], [e, 2] ],   d: [ [f, 2] ],   e: [ [f, 1] ],   f: [ [g, 1] ],   g: [ ] }      

Первым элементом в массиве идет сама смежная вершина, вторым – длина пути до нее (вес ребра).

Или можно представить то же самое с помощью объектов JavaScript:

         let graph = {   a: { b: 2, c: 1 },   b: { f: 7 },   c: { d: 5, e: 2 },   d: { f: 2 },   e: { f: 1 },   f: { g: 1 },   g: { }, }      

Дальше мы будем использовать именно такое представление.

Кратчайший путь во взвешенном графе

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

В графе на картинке выше более короткий (по количеству ребер) путь ABFG весит 10, а вот более длинный ACEFG – всего 5, и он оказывается выгоднее.

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

Алгоритм Дейкстры

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

Он похож на поиск в ширину – мы начинаем со стартовой вершины и перебираем ее смежные вершины. На каждом шаге мы рассчитываем все возможные пути до вершины и выбираем среди них самый короткий.

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

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

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

Текущая вершина отмечается как посещенная и в дальнейших манипуляциях не участвует.

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

Если расстояние для какой-то вершины уже было определено на предыдущих шагах, мы должны сравнить его с новым и выбрать минимальное.

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

rasprostranennye algoritmy i struktury dannyh v javascript grafy 551afb5 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: графы

Визуализация работы алгоритма Дейкстры в графе.

Реализация алгоритма Дейкстры на JavaScript

Для реализации алгоритма Дейкстры на потребуется вспомогательная функция для поиска ближайшей вершины из известных:

         function findNearestVertex(distances, visited) {   let minDistance = Infinity;   let nearestVertex = null;    Object.keys(distances).forEach(vertex => {     if (!visited[vertex] && distances[vertex] < minDistance) {       minDistance = distances[vertex];       nearestVertex = vertex;     }   });    return nearestVertex; }      

Она принимает объект distances, в котором каждой вершине соответствует известное на данный момент расстояние, и объект visited, в котором отмечены посещенные вершины.

Сам алгоритм выглядит так:

         function dijkstra(graph, startVertex) {   let visited = {};   let distances = {}; // кратчайшие пути из стартовой вершины   let previous = {}; // предыдущие вершины        let vertices = Object.keys(graph); // список вершин графа      // по умолчанию все расстояния неизвестны (бесконечны)   vertices.forEach(vertex => {     distances[vertex] = Infinity;     previous[vertex] = null;   });    // расстояние до стартовой вершины равно 0   distances[startVertex] = 0;    function handleVertex(vertex) {     // расстояние до вершины     let activeVertexDistance = distances[vertex];           // смежные вершины (с расстоянием до них)     let neighbours = graph[activeVertex];          // для всех смежных вершин пересчитать расстояния     Object.keys(neighbours).forEach(neighbourVertex => {       // известное на данный момент расстояние       let currentNeighbourDistance = distances[neighbourVertex];       // вычисленное расстояние       let newNeighbourDistance = activeVertexDistance + neighbours[neighbourVertex];              if (newNeighbourDistance < currentNeighbourDistance) {         distances[neighbourVertex] = newNeighbourDistance;         previous[neighbourVertex] = vertex;       }     });          // пометить вершину как посещенную     visited[vertex] = 1;   }      // ищем самую близкую вершину из необработанных   let activeVertex = findNearestVertex(distances, visited);    // продолжаем цикл, пока остаются необработанные вершины    while(activeVertex) {     handleVertex(activeVertex);     activeVertex = findNearestVertex(distances, visited);   }      return { distances, previous }; }     

Запустим алгоритм для нашего взвешенного графа:

         dijkstra(graph, 'a');  /* {   distances: {     a: 0,     b: 2,     c: 1,     d: 6,     e: 3,     f: 4,     g: 5   },   previuos: {     a: null,     b: 'a',     c: 'a',     d: 'c',     e: 'c',     f: 'e',     g: 'f',   } }    */     

Кратчайший путь от A до G составляет 5 и проходит через вершины ACEFG (Алгоритм восстановления пути по объекту previous рассмотрен выше).

Заключение

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

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

В следующей статье цикла мы поговорим про еще одну очень важную структуру – хеш-таблицу.

Больше полезной информации вы найдете на нашем телеграм-канале «Библиотека программиста». Интересно, перейти к каналу

  • 0 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Свежие комментарии

    Рубрики

    About Author 01.

    blank
    Roman Spiridonov

    Моя специальность - Back-end Developer, Software Engineer Python. Мне 39 лет, я работаю в области информационных технологий более 5 лет. Опыт программирования на Python более 3 лет. На Django более 2 лет.

    Categories 05.

    © Speccy 2022 / All rights reserved

    Связаться со мной
    Close