Что такое 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).