re:re:actable
Урок 043 минуты чтения

Что такое graph и как его хранить?

На этой странице
Кратко

Graph - структура из вершин и ребер. Граф может быть directed/undirected, weighted/unweighted, cyclic/acyclic. В JavaScript его чаще всего хранят как adjacency list через Map<Node, Node[]>.

Вопрос

Что такое граф и как его хранить: список смежности или матрица смежности?

Термины

  • Vertex/node - вершина.
  • Edge - ребро.
  • Directed graph - ребра имеют направление.
  • Undirected graph - ребра без направления.
  • Weighted graph - у ребер есть вес.
  • Cycle - путь, который возвращается в уже посещенную вершину.

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

A --- B
|     |
C     D

Один и тот же граф ниже записан тремя способами.

Edge list

const edges: Array<[string, string]> = [
  ['A', 'B'],
  ['A', 'C'],
  ['B', 'D'],
]

Удобно для входных данных.

Adjacency list

const graph = new Map<string, string[]>()
 
graph.set('A', ['B', 'C'])
graph.set('B', ['A', 'D'])
graph.set('C', ['A'])
graph.set('D', ['B'])

Чаще всего используется в задачах.

Построение из edges

function buildGraph(edges: Array<[string, string]>): Map<string, string[]> {
  const graph = new Map<string, string[]>()
 
  for (const [a, b] of edges) {
    if (!graph.has(a)) graph.set(a, [])
    if (!graph.has(b)) graph.set(b, [])
 
    graph.get(a)!.push(b)
    graph.get(b)!.push(a)
  }
 
  return graph
}

Для directed graph добавляют только одно направление: graph.get(from)!.push(to). Для weighted graph вместо имени соседа хранят объект: { to: 'B', weight: 4 }.

Matrix

Adjacency matrix:

matrix[i][j] = 1, если есть ребро i -> j

Тот же граф (A=0, B=1, C=2, D=3):

     A  B  C  D
A  [ 0, 1, 1, 0 ]
B  [ 1, 0, 0, 1 ]
C  [ 1, 0, 0, 0 ]
D  [ 0, 1, 0, 0 ]

Для неориентированного графа матрица симметрична.

Плюсы: быстрый check edge O(1).

Минусы: память O(V^2).

Что отвечать на собеседовании?

Graph состоит из вершин и ребер. Его можно хранить как edge list, adjacency list или adjacency matrix. Для большинства JS-задач adjacency list через Map<string, string[]> удобнее и экономит память: O(V + E). Matrix полезна, когда нужно часто проверять наличие ребра между двумя вершинами.

Что важно помнить: частые ошибки

  • Забывать добавить обе стороны в undirected graph.
  • Не создавать пустой список для вершины без outgoing edges.
  • Не использовать visited и уходить в цикл.
  • Путать V и E в сложности.
  • Использовать matrix для sparse graph без необходимости.

Мини-шпаргалка

  • Graph = vertices + edges.
  • Directed - направление.
  • Undirected - две стороны.
  • Weighted - есть вес.
  • Adjacency list - O(V + E).
  • Matrix - O(V^2).

Документация

Wikipedia: Graph (abstract data type), VisuAlgo: Graph DS.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам