Часть 3: Графики

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

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

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

Цели для этого блога

  • Создайте класс Graph
  • Добавьте в граф вершины и ребра.
  • Удалить вершины и ребра
  • Пройдите по графику

Вот простой график. Вы можете видеть, что каждая точка как минимум связана с одной другой точкой на графике. Если бы мы создали для этого класс Javascript, как бы мы отслеживали каждую вершину и ребро? Ответ проще, чем вы думаете. Мы можем использовать Список смежности.

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

Один из простых способов отслеживать каждую вершину и их соединения - использовать список смежности. Это простой объект Javascript, где каждый ключ является вершиной, а значение - массивом, содержащим все их непосредственные соединения. Вот пример:

this.adjacencyList = 
{
    A: [B, C],
    B: [A, D],
    C: [A, D, E],
    D: [B, C, E],
    E: [C, D]
}

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

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
}

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

addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []
}
addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
}

Чтобы удалить вершину из нашего графа, будет проще сначала удалить ребро. Мы можем использовать функцию filter для массивов, чтобы удалить каждую вершину из массива смежности другой. Затем, чтобы удалить вершину, мы можем использовать функцию removeEdge () для удаления каждого ребра в списке вершин и закончить, используя часто забываемый атрибут delete для объектов Javascript, чтобы полностью избавиться от вершины.

removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1].filter(el => el !== v2)
    this.adjacencyList[v2] = this.adjacencyList[v2].filter(el => el !== v1);
}
removeVertex(vertex) {
    while(this.adjacencyList[vertex].length) {
        const adjacentVertex = this.adjacencyList[vertex].pop();
        this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
}

Обход графа

Теперь самое интересное. Есть много способов пройти по графику (сначала в ширину / сначала в глубину, рекурсивный / итеративный), но мы просто выберем один и будем придерживаться его. При желании вы можете посмотреть другие варианты. Конечный результат тот же, у нас будет массив каждой вершины на графе, начиная с одной точки.

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

"Но как мы узнаем, что мы закончили?" Вы можете спросить. У нас может быть стек (который следует в порядке очереди), чтобы отслеживать, какие вершины мы просматриваем, и посещенный объект, чтобы легко проверять, мы уже посещали вершину раньше, чтобы не встретить дубликатов.

Начнем с инициализации некоторых из наших ценностей.

DepthFirst(start) {
    let stack = [start];
    let result = [];
    let visited = {};
    let currentElement;
    visited[start] = true;

Мы инициализировали наш стек с помощью нашей начальной вершины, в данном случае воспользуемся A. У нас также есть массив results и наш посещенный объект. Поскольку мы уже посетили наш start, мы можем установить значение start в посещенном объекте на true. Мы также устанавливаем переменную currentElement, которая будет изменяться каждый раз, когда мы посещаем вершину.

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

while(stack.length) {
    currentElement = stack.pop();
    result.push(currentElement);
    this.adjacencyList[currentElement].forEach(neighbor => {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            stack.push(neighbor);
        }
    })
}
return result;

Вот и все! Каждая итерация цикла с извлечением элемента из стека и добавлением его в наш массив результатов. Затем мы просматриваем каждого соседа в массиве смежности этого элемента, и, если он не был посещен, он будет установлен как посещенный и добавлен в стек. Если был посещен каждый сосед, цикл пропустит и вытолкнет другой элемент из стека. В конце концов, каждый элемент будет посещен, и стек будет пуст, цикл завершается, и мы возвращаем наш массив result.

Вот все, что мы до сих пор вместе выложили:

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

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

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

Вот наш пример графика с добавленным весом. Какое будет кратчайшее расстояние от A до E? Вы можете легко пройти через некоторые перестановки и увидеть, что это от A-C-D-E, но что, если бы наш граф состоял из тысяч вершин и ребер? Вот тут-то и появляется Дийсктра.

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

Спасибо за чтение и удачного кодирования!

Больше контента на plainenglish.io