Оригинальная ссылка:Graph Data Structures for Beginners

Адрес перевода Чжунчэн:Структуры данных, которые должны знать новички: граф

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

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

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

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

---

Эта статья является частью следующих руководств:

Структуры данных и алгоритмы (DSA), которые должны знать новички

1. Временная сложность алгоритмов и нотация Big O
2. Восемь сложностей со временем, которые должен знать каждый программист
3. Структуры данных, которые должны знать новички: массив, HashMap и список (перевод)
4. Структуры данных, которые должны знать новички: граф 👈 Это эта статья
5. Структуры данных, которые должны знать новички: дерево (Быть в курсе)
6. Приложение I: Анализ рекурсивных алгоритмов

---

Ниже приводится краткое изложение работы графа в этой статье:

	список смежности	матрица смежности
космическая сложность	O(|V|+ |E|)	O(|V|²)
Добавить квершина	O(1)	O(|V|²)
Удалитьвершина	O(|V| + |E|)	O(|V|)²
Добавить кбоковая сторона	O(1)	O(1)
УдалитьEdge (реализован на основе массива)	O(|E|)	O(1)
УдалитьEdge (на основе реализации HashSet)	O(1)	O(1
Получатьсмежные вершины	O(|E|)	O(|V|)
судитьЯвляется ли он смежным (реализовано на основе массива)	O(|E|)	O(1)
судитьЯвляется ли он смежным (реализовано на основе HashSet)	O(1)	O(1)

основы графиков

Граф представляет собой (содержит несколько узлов), каждыйузел0 или более элементов могут быть соединены

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

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

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

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

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

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

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

Для полного графа каждая вершина имеет количество вершин в графе - 1 ребро. В приведенном выше примере полного графа 7 вершин, поэтому каждая вершина имеет 6 ребер.

применение графиков

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

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

• Карта авиакомпании (как показано выше)

  • вершина = аэропорт
  • edge = траектория полета между двумя аэропортами
  • Вес = расстояние между двумя аэропортами

• GPS-навигация

  • вершина = пересечение
  • край = дорога
  • Вес = время, затраченное на то, чтобы добраться от одного перекрестка до другого.

• Интернет

  • вершина = сервер
  • край = канал данных
  • вес = скорость соединения

В общем, реальные приложения графов:

• Электронная схема
• управление авиацией
• навигация для вождения
• Телекоммуникационные объекты: Планирование строительства базовой станции
• Социальные сети: Facebook использует графики, чтобы рекомендовать друзей (вы, возможно, знаете)
• Система рекомендаций: Amazon/Netflix использует графики, чтобы рекомендовать продукты и фильмы.
• Используйте диаграммы для планирования логистических маршрутов

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

представление графа

Существует два основных способа представления графиков:

1. список смежности
2. матрица смежности

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

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

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

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

Мы можем представить приведенный выше граф, установив следующую матрицу смежности:

  a b c d e
a 1 1 - - -
b - - 1 - -
c - - - 1 -
d - 1 1 - -

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

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

Какова временная сложность запроса о том, являются ли две вершины смежными?

В матрице смежности временная сложность запроса о том, являются ли две вершины смежными, равнаO(1).

Как насчет пространственной сложности?

Используя матрицу смежности для хранения графа, пространственная сложность равнаO(n²), n — количество вершин, поэтому его также можно выразить какO(|V|²).

Как насчет временной сложности добавления вершины?

Матрица смежности хранится по количеству вершин какV x Vматрица. Таким образом, каждый раз, когда добавляется вершина, матрица должна быть восстановлена ​​какV+1 x V+1новая матрица.

(Следовательно) временная сложность добавления вершины в матрицу смежности равнаO(|V|²).

Как получить смежные вершины?

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

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

  a b c d e
b - - 1 - -

Получите доступ к его отношению ко всем другим вершинам, поэтому:

В матрице смежности временная сложность запроса соседних вершин равнаO(|V|).

Представьте, что вам нужно представить сеть людей в FaceBook в виде графика. вы должны построить20亿 x 20亿Матрица смежности , и многие позиции в этой матрице пусты. Никто не может знать всех остальных, максимум несколько тысяч.

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

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

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

Вы можете использовать массив или HashMap для создания списка смежности, в котором хранятся все вершины. Каждая вершина имеет список (который может быть массивом, связанным списком, набором и т. д.), в котором хранятся смежные вершины.

Например, на приведенном выше графе к вершине a примыкает вершина b, которая также является петлей, а вершина b имеет ребро, указывающее на вершину c, и так далее:

a -> { a b }
b -> { c }
c -> { d }
d -> { b c }

Как и ожидалось, если вы хотите узнать, соединена ли вершина с другими вершинами, вам нужно пройти весь список (вершин).

Временная сложность запроса, связаны ли две вершины в списке смежности, составляетO(n), n — количество вершин, поэтому его также можно выразить какO(|V|).

Как насчет пространственной сложности?

Объемная сложность хранения графа с использованием списка смежности составляетO(n), n представляет собой сумму количества вершин и количества ребер, поэтому его также можно выразить какO(|V| + |E|).

Список смежности на основе реализации HashMap

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

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

const graph = {
  a：[ 'a'，'b' ]，
  b：[ 'c' ]，
  c：[ 'd' ]，
  d：[ 'b'，'c' ]
};

Графики обычно требуют реализации следующих двух операций:

• Добавить или удалить вершины.
• Добавьте или удалите ребра.

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

Предположим, что вершину b нужно удалить. Нам нужно не толькоdelete graph['b'], а также необходимо удалить ссылку в массиве смежности вершины a и вершины d.

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

На основе списка смежности граф реализован в объектно-ориентированном стиле.

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

class Node {
  constructor(value) {
    this.value = value;
    this.adjacents = []; // adjacency list
  }

  addAdjacent(node) {
    this.adjacents.push(node);
  }

  removeAdjacent(node) {
    const index = this.adjacents.indexOf(node);
    if (index > -1) {
      this.adjacents.splice(index, 1);
      return node;
    }
  }

  getAdjacents() {
    return this.adjacents;
  }

  isAdjacent(node) {
    return this.adjacents.indexOf(node) > -1;
  }
}

Уведомление,addAdjacentВременная сложность методаO(1), но функциональная временная сложность удаления смежных вершин равнаO(|E|). Что если вместо массива использовать HashSet? Временная сложность (для удаления смежных вершин) падает доO(1). Но сначала позвольте коду работать, а затем оптимизируйте его.

Make it work. Make it right. Make it faster.

теперь естьNodeкласс, пора писатьGraphкласс, который может выполнять добавление или удаление вершин и ребер.

Graph.constructor

class Graph {
  constructor(edgeDirection = Graph.DIRECTED) {
    this.nodes = new Map();
    this.edgeDirection = edgeDirection;
  }
  // ...
}
Graph.UNDIRECTED = Symbol('directed graph'); // one-way edges
Graph.DIRECTED = Symbol('undirected graph'); // two-ways edges

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

Graph.addEdge

Чтобы добавить новое ребро, вам нужно знать две вершины: начальную точку ребра и конечную точку ребра.

addEdge(source, destination) {
  const sourceNode = this.addVertex(source);
  const destinationNode = this.addVertex(destination);
  sourceNode.addAdjacent(destinationNode);
  if(this.edgeDirection === Graph.UNDIRECTED) {
    destinationNode.addAdjacent(sourceNode);
  }
  return [sourceNode, destinationNode];
}

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

Временная сложность добавления ребра в список смежности:O(1).

Если вершины на обоих концах вновь добавленного ребра не существуют, их нужно сначала создать (несуществующие верх и низ), давайте это реализуем!

Graph.addVertex

Вершины создаются переходом кthis.nodesДобавьте вершину в .this.nodesХранится в группе пар ключ-значение, ключ — это значение вершины, значение —Nodeэкземпляр класса. Обратите внимание на строки 5-6 кода ниже (т.е.const vertex = new Node(value); this.nodes.set(value, vertex);):

addVertex(value) {
  if(this.nodes.has(value)) {
    return this.nodes.get(value);
  } else {
    const vertex = new Node(value);
    this.nodes.set(value, vertex);
    return vertex;
  }
}

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

Временная сложность добавления вершины в список смежности:O(1).

Graph.removeVertex

Удаление вершины из графа немного сложнее. Мы должны проверить, не является ли удаляемая вершина соседней с другими вершинами.

removeVertex(value) {
  const current = this.nodes.get(value);
  if(current) {
    for (const node of this.nodes.values()) {
      node.removeAdjacent(current);
    }
  }
  return this.nodes.delete(value);
}

Каждая вершина и набор соседних вершин должны быть посещены.

Временная сложность удаления вершины в списке смежности:O(|V| + |E|).

Наконец, давайте вместе удалим ребро!

Graph.removeEdge

Удалить ребро так же просто, как и добавить ребро.

removeEdge(source, destination) {
  const sourceNode = this.nodes.get(source);
  const destinationNode = this.nodes.get(destination);
  if(sourceNode && destinationNode) {
    sourceNode.removeAdjacent(destinationNode);
    if(this.edgeDirection === Graph.UNDIRECTED) {
      destinationNode.removeAdjacent(sourceNode);
    }
  }
  return [sourceNode, destinationNode];
}

Основное различие между удалением и добавлением ребра заключается в следующем:

• Если вершина на обоих концах ребра не существует, ее больше не нужно создавать.
• использоватьNode.removeAdjacentвместоNode.addAdjacent.

так какremoveAdjacentНабор смежных узлов должен быть пройден, поэтому его время выполнения:

Временная сложность удаления ребра в списке смежности:O(|E|).

Далее мы обсудим, как искать по графу.

Поиск в ширину (BFS) — поиск по графу

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

Давайте посмотрим, как это реализовать в коде:

*bfs(first) {
  const visited = new Map();
  const visitList = new Queue();
  visitList.add(first);
  while(!visitList.isEmpty()) {
    const node = visitList.remove();
    if(node && !visited.has(node)) {
      yield node;
      visited.set(node);
      node.getAdjacents().forEach(adj => visitList.add(adj));
    }
  }
}

Как видите, мы используем очередь для временного хранения вершин, к которым нужно получить доступ, очередь следует принципу «первым пришел — первым обслужен» (FIFO).

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

Вот пример того, как использовать приведенный выше код BFS:

const graph = new Graph(Graph.UNDIRECTED);
const [first] = graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(5, 2);
graph.addEdge(6, 3);
graph.addEdge(7, 3);
graph.addEdge(8, 4);
graph.addEdge(9, 5);
graph.addEdge(10, 6);
bfsFromFirst = graph.bfs(first);
bfsFromFirst.next().value.value; // 1
bfsFromFirst.next().value.value; // 2
bfsFromFirst.next().value.value; // 3
bfsFromFirst.next().value.value; // 4
// ...

ты сможешьЭтотНайдите больше тестового кода.

Теперь пришло время поговорить о поиске в глубину!

Фигура поиска - поиск в глубину (DFS)

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

Реализация DFS аналогична BFS, но вместо очередей используются стеки:

*dfs(first) {
  const visited = new Map();
  const visitList = new Stack();
  visitList.add(first);
  while(!visitList.isEmpty()) {
    const node = visitList.remove();
    if(node && !visited.has(node)) {
      yield node;
      visited.set(node);
      node.getAdjacents().forEach(adj => visitList.add(adj));
    }
  }
}

Пример теста выглядит следующим образом:

const graph = new Graph(Graph.UNDIRECTED);
const [first] = graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(5, 2);
graph.addEdge(6, 3);
graph.addEdge(7, 3);
graph.addEdge(8, 4);
graph.addEdge(9, 5);
graph.addEdge(10, 6);
dfsFromFirst = graph.dfs(first);
visitedOrder = Array.from(dfsFromFirst);
const values = visitedOrder.map(node => node.value);
console.log(values); // [1, 4, 8, 3, 7, 6, 10, 2, 5, 9]

Как видите, графы, используемые BFS и DFS, одинаковы, однако порядок посещения вершин сильно различается. BFS выводит последовательно от 1 до 10, а DFS сначала обращается к самым глубоким вершинам.

Временная и пространственная сложность графов

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

	список смежности	матрица смежности
космическая сложность	O(|V|+ |E|)	O(|V|²)
Добавить квершина	O(1)	O(|V|²)
Удалитьвершина	O(|V| + |E|)	O(|V|)²
Добавить кбоковая сторона	O(1)	O(1)
УдалитьEdge (реализован на основе массива)	O(|E|)	O(1)
УдалитьEdge (на основе реализации HashSet)	O(1)	O(1
Получатьсмежные вершины	O(|E|)	O(|V|)
судитьЯвляется ли он смежным (реализовано на основе массива)	O(|E|)	O(1)
судитьЯвляется ли он смежным (реализовано на основе HashSet)	O(1)	O(1)

Как видно из приведенной выше таблицы, почти все операции в списке смежности выполняются быстрее. Есть только один способ сделать матрицу смежности более производительной, чем список смежности: проверка, является ли вершина смежной с другими вершинами, однако реализация списка смежности с использованием HashSet вместо Array также может получить результат за константное время: )

Суммировать

Граф может быть абстракцией многих реальных сценариев, таких как аэропорты, социальные сети, Интернет и т. д. Мы вводим некоторые основные алгоритмы для графов, такие как поиск в ширину (BFS) и поиск в глубину (DFS). Мы также взвешиваем различные реализации графов: матрицы смежности и списки смежности. Другие применения графов мы рассмотрим в отдельной статье (более подробно), такие как нахождение кратчайшего расстояния между двумя вершинами графа и другие интересные алгоритмы.Этот алгоритм является наиболее интересным, и заинтересованные студенты могут прочитать егоэто).