Graph (Граф)

Структура данных из вершин (nodes) и рёбер (edges), моделирующая связи между объектами.

Зачем нужно

  • Моделирование сетей (соцсети, маршруты, зависимости)
  • Поиск кратчайшего пути, обнаружение циклов
  • Топологическая сортировка (сборка проектов, расписания)

Где используется

  • Соцсети (друзья), карты (маршруты), npm (зависимости), Git (история коммитов)

Виды графов

Вид Описание
Направленный Рёбра имеют направление (A → B)
Ненаправленный Рёбра двусторонние (A — B)
Взвешенный Рёбра имеют вес (расстояние)
Ациклический (DAG) Без циклов, направленный

Представление

Список смежности (Adjacency List)

class Graph {
  private adj: Map<string, string> = new Map();

  addVertex(v: string) {
    if (!this.adj.has(v)) this.adj.set(v, );
  }

  addEdge(from: string, to: string) {
    this.adj.get(from)?.push(to);
    this.adj.get(to)?.push(from); // убрать для направленного
  }

  getNeighbors(v: string): string {
    return this.adj.get(v) || ;
  }
}

Обходы

BFS (поиск в ширину)

function bfs(graph: Graph, start: string): string {
  const visited = new Set<string>;
  const queue = [start];
  const result: string = ;
  visited.add(start);
  while (queue.length) {
    const v = queue.shift()!;
    result.push(v);
    for (const neighbor of graph.getNeighbors(v)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

DFS (поиск в глубину)

function dfs(graph: Graph, start: string): string {
  const visited = new Set<string>;
  const result: string = ;
  function visit(v: string) {
    visited.add(v);
    result.push(v);
    for (const n of graph.getNeighbors(v)) {
      if (!visited.has(n)) visit(n);
    }
  }
  visit(start);
  return result;
}

Сложность

Операция Список смежности Матрица
Добавить ребро O(1) O(1)
Проверить ребро O(V) O(1)
Обход (BFS/DFS) O(V + E) O(V²)

Связанные темы

Ресурсы