Структура данных 101: введение в графики в JavaScript

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

Что такое график?

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

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

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

Терминология графа

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

Степень вершины: общее количество ребер, соединенных с вершиной. Есть два типа степеней:

• In-Degree: общее количество подключенных к вершине.
• Out-Degree: общее количество исходящих ребер, соединенных с вершиной.

Смежность: две вершины называются смежными, если есть ребро, соединяющее их напрямую.

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

Самостоятельная петля: это происходит, когда ребро начинается и заканчивается в одной и той же вершине.

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

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

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

Скажем, мы хотели вычислить максимально возможные ребра для неориентированного графа. Максимально возможные ребра графа с n вершинами будут всеми возможными парами вершин. ЕстьС (п, 2)С ( п, 2 )возможные пары вершин согласно комбинаторике. Решение с помощью биномиальных коэффициентов дает нам\ гидроразрыва {п (п-1)} {2}​2​​п ( п — 1 )​​, так что есть \ гидроразрыва {п (п-1)} {2}​2​​п ( п — 1 )​​ Максимально возможные ребра в неориентированном графе.

В ориентированном графе ребра однонаправлены; например, для пары (0,1) это означает, что существует ребро от вершины 0 к вершине 1, и единственный способ пройти — перейти от 0 к 1.

Это изменяет количество ребер, которые могут существовать в графе. Для ориентированного графа спп вершин, минимальное количество ребер, которые могут соединить вершину с любой другой вершиной, равно п-1п — 1. Итак, если у вас есть n вершин, то возможных ребер будетп * (п-1)п * ( п — 1 ).

Типы представлений графов

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

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

Матрица смежности — это двумерная матрица, в которой каждая ячейка может содержать 0 или 1. Заголовки строк и столбцов представляют исходную и целевую вершины соответственно. Если ячейка содержит 1, это означает, что между соответствующими вершинами есть ребро. Граничные операции выполняются в постоянное время, так как нам нужно только манипулировать значением в конкретной ячейке.

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

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

Добавление ребра и вершины в список смежности также является постоянной во времени операцией. Удаление края требуетO (E)O ( E )время, потому что — в худшем случае — все ребра могут быть в одной вершине. Следовательно, мы должны пройти все ребра E, чтобы добраться до последнего. Удаление вершины требуетО (В + Е)О ( В + Е ) время, потому что нам нужно удалить все его края, а затем переиндексировать оставшуюся часть списка на один шаг назад.

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

Как реализовать график в JavaScript

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

Как мы знаем, Graphкласс состоит из двух членов данных:

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

class Graph{

  constructor(vertices){

    //Total number of vertices in the graph

    this.vertices=vertices;

    //Defining an array which can hold LinkedLists equal to the number of vertices in the graph

    this.list=[];

    //Creating a new LinkedList for each vertex/index of the list

    for(i=0; i<vertices.length; i++){

      let temp=new LinkedList();

      this.list.push(temp);

    }

  }

}

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

• printGraph(): Печатает содержимое графика.
• addEdge(): Это связывает источник с местом назначения

index.js

«use strict»;

const LinkedList = require(‘./LinkedList.js’);

const Node = require(‘./Node.js’);

class Graph {

  constructor(vertices) {

    //Total number of vertices in the graph

    this.vertices = vertices;

    //Array that holds linked lists equal to the number of vertices in the graph

    this.list = [];

    //Creating a new linked list for each vertice of the graph

    var it;

    for (it = 0; it < vertices; it++) {

      let temp = new LinkedList();

      this.list.push(temp);

    }

  }

  addEdge(source, destination) {

    if (source < this.vertices && destination < this.vertices)

    //Since we are implementing a directed list, (0,1) is not the same as (1,0)

    this.list[source].insertAtHead(destination);

    //If we were to implement an undirected graph where (0,1)==(1,0),

    //we would create an additional edge from destination to source too:

    //this.list[destination].insertAtHead(source);

  }

  printGraph() {

    console.log(«>>Adjacency List of Directed Graph<<«);

    var i;

    for (i = 0; i < this.list.length; i++) {

      process.stdout.write(«|» + String(i) + «| => «);

      let temp = this.list[i].getHead();

      while (temp != null) {

        process.stdout.write(«[» + String(temp.data) + «] -> «);

        temp = temp.nextElement;

      }

      console.log(«null «);

    }

  }

}

let g = new Graph(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 3);

g.addEdge(2, 3);

g.printGraph();

Node.js

«use strict»;

module.exports = class Node {

  constructor(data) {

    this.data = data;

    this.nextElement = null;

  }

}

LinkedList.js

«use strict»;

const Node = require(‘./Node.js’);

module.exports = class LinkedList {

  constructor() {

    this.head = null;

  }

  //Insertion At Head

  insertAtHead(newData) {

    let tempNode = new Node(newData);

    tempNode.nextElement = this.head;

    this.head = tempNode;

    return this; //returning the updated list

  }

  isEmpty() {

    return (this.head == null);

  }

  //function to print the linked list

  printList() {

    if (this.isEmpty()) {

      console.log(«Empty List»);

      return false;

    } else {

      let temp = this.head;

      while (temp != null) {

        process.stdout.write(String(temp.data));

        process.stdout.write(» -> «);

        temp = temp.nextElement;

      }

      console.log(«null»);

      return true;

    }

  }

  getHead() {

    return this.head;

  }

  setHead(newHead) {

    this.head = newHead;

    return this;

  }

  getListStr() {

    if (this.isEmpty()) {

      console.log(«Empty List»);

      return «null»;

    } else {

      let st = «»;

      let temp = this.head

      while (temp != null) {

        st += String(temp.data);

        st += » -> «;

        temp = temp.nextElement;

      }

      st += «null»;

      return st;

    }

  }

  insertAtTail(newData) {

    //Creating a new Node with data as newData

    let node = new Node(newData);

    //check for case when list is empty

    if (this.isEmpty()) {

      //Needs to Insert the new node at Head

      this.head = node;

      return this;

    }

    //Start from head

    let currentNode = this.head;

    //Iterate to the last element

    while (currentNode.nextElement != null) {

      currentNode = currentNode.nextElement;

    }

    //Make new node the nextElement of last node of list

    currentNode.nextElement = node;

    return this;

  }

  search(value) {

    //Start from the first element

    let currentNode = this.head;

    //Traverse the list until you find the value or reach the end

    while (currentNode != null) {

      if (currentNode.data == value) {

        return true; //value found

      }

      currentNode = currentNode.nextElement

    }

    return false; //value not found

  }

  deleteAtHead() {

    //if list is empty, do nothing

    if (this.isEmpty()) {

      return this;

    }

    //Get the head and first element of the list

    let firstElement = this.head;

    //If list is not empty, link head to the nextElement of firstElement

    this.head = firstElement.nextElement;

    return this;

  }

  deleteVal(value) {

    let deleted = null; //True or False

    //Write code here

    //if list is empty return false

    if (this.isEmpty()) {

      return false;

    }

    //else get pointer to head

    let currentNode = this.head;

    // if first node’s is the node to be deleted, delete it and return true

    if (currentNode.data == value) {

      this.head = currentNode.nextElement;

      return true;

    }

    // else traverse the list

    while (currentNode.nextElement != null) {

      // if a node whose next node has the value as data, is found, delete it from the list and return true

      if (currentNode.nextElement.data == value) {

        currentNode.nextElement = currentNode.nextElement.nextElement;

        return true;

      }

      currentNode = currentNode.nextElement;

    }

    //else node was not found, return false

    deleted = false;

    return deleted;

  }

  deleteAtTail() {

    // check for the case when linked list is empty

    if (this.isEmpty()) {

      return this;

    }

    //if linked list is not empty, get the pointer to first node

    let firstNode = this.head;

    //check for the corner case when linked list has only one element

    if (firstNode.nextElement == null) {

      this.deleteAtHead();

      return this;

    }

    //otherwise traverse to reach second last node

    while (firstNode.nextElement.nextElement != null) {

      firstNode = firstNode.nextElement;

    }

    //since you have reached second last node, just update its nextElement pointer to point at null, skipping the last node

    firstNode.nextElement = null;

    return this;

  }

}

addEdge (источник, место назначения)

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

this.list[source].insertAtHead(destination)

Мы реализуем ориентированный граф, поэтому addEdge(0, 1)не равно addEdge(1, 0).

printGraph ()

Эта функция использует вложенный цикл для перебора списка смежности. Каждый связанный список просматривается.

А как насчет неориентированного графа?

До сих пор мы рассмотрели реализацию ориентированного графа.

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

Алгоритмы обхода графа

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

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

Два основных метода обхода графа:

• Поиск в ширину (BFS): алгоритм BFS расширяется вширь. Все узлы на определенном уровне проходят перед переходом на следующий уровень. Это поэтапное расширение гарантирует, что для любой начальной вершины вы можете достичь всех остальных по одному уровню за раз.
• Поиск в глубину (DFS): этот алгоритм противоположен BFS; он растет по глубине. Начиная с любого узла, мы переходим к соседнему узлу, пока не достигнем самого дальнего уровня. Затем мы возвращаемся к начальной точке и выбираем другой соседний узел. Еще раз прощупываем до самого дальнего уровня и возвращаемся. Этот процесс продолжается до тех пор, пока не будут посещены все узлы.

Реальное использование графиков

Графы используются для решения реальных задач, которые включают представление проблемного пространства в виде сети. Любое сетевое приложение (пути, поиск взаимосвязей, маршрутизация и т.д.) Применяет концепцию графов. Таким образом, структура данных графа играет фундаментальную роль в нескольких приложениях:

• GPS
• Нейронные сети
• Одноранговые сети
• Сканеры поисковых систем
• Вывоз мусора
• Сайты социальных сетей

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

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

• Facebook Graph API, например, использует концепцию графов, где пользователи считаются вершинами, а граница проходит между друзьями и другими объектами, такими как комментарии, фотографии, заметки и т.д.
• Карты Google также основывают свою систему навигации на графиках. Пересечение двух или более дорог считается вершиной, а дорога, соединяющая две вершины, считается ребром. Таким образом, они могут вычислить кратчайший путь между двумя вершинами.
• Большинство веб-сайтов электронной коммерции, таких как Amazon, используют отношения между продуктами, чтобы показывать рекомендации пользователю. При этом используется сетевая структура графиков для установления связей и предложений о связанном контенте.