Граф — представление, обход графа (DFS, BFS): гайд и примеры на JavaScript

[Aladdin]

Граф — это структура данных, которая представляет связи между объектами. Граф состоит из вершин (узлов) и рёбер (связей между ними).

Графы используются повсеместно:

• Социальные сети: пользователи — вершины, дружба — рёбра
• Маршрутизация: города — вершины, дороги — рёбра
• Рекомендации: товары связаны по схожести
• Анализ зависимостей: модули в проекте, задачи с приоритетами
• Поиск кратчайшего пути: навигация, логистика
• Паутина интернета: веб-страницы и ссылки между ними

Типы графов

Ориентированный граф — рёбра имеют направление (A → B). Неориентированный граф — рёбра двусторонние (A B). Взвешенный граф — рёбра имеют вес/стоимость. Невзвешенный граф — все рёбра одинакового веса.

---

Представление графа в коде

Существует три основных способа представить граф. Выбор зависит от задачи, количества вершин и плотности графа.

1. Список смежности (Adjacency List) — самый эффективный

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

// Неориентированный граф с помощью Map
const graph = new Map();

// Добавление рёбер
graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);
graph.set('C', ['A', 'D']);
graph.set('D', ['B', 'C']);

// Или с помощью объекта
const graphObj = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'D'],
  'D': ['B', 'C']
};

Преимущества: компактный для разреженных графов, быстрый доступ к соседям, O(V+E) память.
Недостатки: проверка наличия конкретного ребра требует линейного поиска.

2. Матрица смежности (Adjacency Matrix)

Двумерный массив, где matrix[i][j] = 1, если есть ребро между вершиной i и j.

// Граф с 4 вершинами
const matrix = [
  [0, 1, 1, 0],  // A: связана с B, C
  [1, 0, 0, 1],  // B: связана с A, D
  [1, 0, 0, 1],  // C: связана с A, D
  [0, 1, 1, 0]   // D: связана с B, C
];

// Или с индексами для удобства
const vertices = ['A', 'B', 'C', 'D'];

// Проверка ребра A → B: matrix[0][1] === 1
// Для взвешенного графа: matrix[i][j] = вес

Преимущества: быстрая проверка ребра O(1), подходит для плотных графов.
Недостатки: требует O(V²) памяти, неэффективна для разреженных графов.

3. Список рёбер (Edge List)

Просто список всех рёбер в виде пар вершин.

const edges = [
  ['A', 'B'],
  ['A', 'C'],
  ['B', 'D'],
  ['C', 'D']
];

// Для взвешенного графа:
const weightedEdges = [
  ['A', 'B', 5],
  ['A', 'C', 3],
  ['B', 'D', 2],
  ['C', 'D', 7]
];

Используется: когда нужно обрабатывать все рёбра, в алгоритмах вроде Краскала.

---

Класс Graph для удобства

Создадим удобный класс для работы с графами:

class Graph {
  constructor(isDirected = false) {
    this.adjacencyList = new Map();
    this.isDirected = isDirected;
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(vertex1, vertex2, weight = 1) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);
    
    this.adjacencyList.get(vertex1).push({ node: vertex2, weight });
    
    // Для неориентированного графа добавляем обратное ребро
    if (!this.isDirected) {
      this.adjacencyList.get(vertex2).push({ node: vertex1, weight });
    }
  }

  getNeighbors(vertex) {
    return this.adjacencyList.get(vertex) || [];
  }

  hasVertex(vertex) {
    return this.adjacencyList.has(vertex);
  }

  display() {
    for (let [vertex, neighbors] of this.adjacencyList) {
      console.log(`${vertex} →`, neighbors.map(n => n.node).join(', '));
    }
  }
}

Использование:

const g = new Graph(false); // неориентированный граф
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.display();
// Вывод:
// A → B, C
// B → A, D
// C → A
// D → B

---

DFS (Depth-First Search) — Поиск в глубину

Как работает DFS

1. Начинаем с начальной вершины
2. Идём в глубину, посещая первого соседа
3. Затем идём в соседа этого соседа и т.д.
4. Когда соседей нет, возвращаемся (backtrack) к последней вершине и ищем другой путь
5. Повторяем, пока не посетим все вершины

Аналогия: исследование лабиринта — идёшь в одну сторону полностью, потом разворачиваешься и пробуешь другую.

DFS рекурсивная реализация

class Graph {
  // ... предыдущий код ...

  dfsRecursive(startVertex, visited = new Set(), result = []) {
    visited.add(startVertex);
    result.push(startVertex);

    const neighbors = this.getNeighbors(startVertex);
    for (let neighbor of neighbors) {
      if (!visited.has(neighbor.node)) {
        this.dfsRecursive(neighbor.node, visited, result);
      }
    }

    return result;
  }

  dfs(startVertex) {
    return this.dfsRecursive(startVertex);
  }
}

Пример использования:

const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');
g.addEdge('D', 'E');

console.log(g.dfs('A')); // ['A', 'B', 'D', 'C', 'E']

Как это работает step-by-step:

1. Посетить A, добавить в результат
2. A имеет соседей B и C, идём к B (первому)
3. B имеет соседей A (уже посещена) и D, идём к D
4. D имеет соседей B (уже посещена), C и E, идём к C
5. C имеет соседей A (уже посещена) и D (уже посещена)
6. Возвращаемся к D, идём к E
7. E соседей нет, всё готово

DFS итеративная реализация (со стеком)

class Graph {
  dfsIterative(startVertex) {
    const visited = new Set();
    const stack = [startVertex];
    const result = [];

    while (stack.length > 0) {
      const vertex = stack.pop();

      if (!visited.has(vertex)) {
        visited.add(vertex);
        result.push(vertex);

        const neighbors = this.getNeighbors(vertex);
        // Добавляем соседей в стек в обратном порядке
        // чтобы первого соседа обработать первым
        for (let i = neighbors.length - 1; i >= 0; i--) {
          if (!visited.has(neighbors[i].node)) {
            stack.push(neighbors[i].node);
          }
        }
      }
    }

    return result;
  }
}

Когда использовать DFS:

• Поиск пути в лабиринте или графе
• Обнаружение циклов в графе
• Топологическая сортировка
• Проверка связности компонент
• Задачи с backtracking (судоку, головоломки)
• Когда граф очень широкий (много соседей) — DFS экономит память

---

BFS (Breadth-First Search) — Поиск в ширину

Как работает BFS

1. Начинаем с начальной вершины
2. Посещаем всех её соседей (уровень 1)
3. Затем посещаем всех соседей уровня 1 (уровень 2)
4. Затем уровень 3 и т.д.
5. Продолжаем, пока не посетим все вершины

Аналогия: расширяющиеся волны в воде — сначала ближайшие точки, потом дальше.

BFS реализация (с очередью)

class Graph {
  bfs(startVertex) {
    const visited = new Set();
    const queue = [startVertex];
    const result = [];

    visited.add(startVertex);

    while (queue.length > 0) {
      const vertex = queue.shift(); // берём первый элемент
      result.push(vertex);

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          visited.add(neighbor.node);
          queue.push(neighbor.node); // добавляем в конец
        }
      }
    }

    return result;
  }
}

Пример использования:

const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');
g.addEdge('D', 'E');

console.log(g.bfs('A')); // ['A', 'B', 'C', 'D', 'E']

Как это работает step-by-step:

1. Очередь: [A], посетить A, результат: [A]
2. Соседи A: B, C. Очередь: [B, C], посетить B, результат: [A, B]
3. Соседи B: A (уже), D. Очередь: [C, D], посетить C, результат: [A, B, C]
4. Соседи A (уже), D (уже в очереди). Очередь: [D], посетить D, результат: [A, B, C, D]
5. Соседи B (уже), C (уже), E. Очередь: [E], посетить E, результат: [A, B, C, D, E]

Когда использовать BFS:

• Поиск кратчайшего пути в невзвешенном графе
• Проверка, является ли граф двудольным
• Уровневый обход дерева/графа
• Поиск всех вершин на определённом расстоянии
• Когда граф глубокий, а решение близко к началу

---

DFS vs BFS

Параметр	DFS	BFS
Структура данных	Стек (рекурсия)	Очередь
Память	O(h) где h — глубина	O(w) где w — ширина
Кратчайший путь	Не гарантирует	✓ Гарантирует (невзвешённый граф)
Порядок посещения	Глубоко в одну ветку	Слой за слоем
Применение	Циклы, топосорт, backtracking	Кратчайший путь, проверка расстояния
Сложность	O(V + E)	O(V + E)

---

Практические примеры

Пример 1: Поиск пути между двумя вершинами

class Graph {
  // ... предыдущий код ...

  findPath(start, end) {
    const visited = new Set();
    const path = [];

    const dfs = (vertex) => {
      visited.add(vertex);
      path.push(vertex);

      if (vertex === end) {
        return true; // путь найден
      }

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          if (dfs(neighbor.node)) {
            return true;
          }
        }
      }

      path.pop(); // backtrack
      return false;
    };

    if (dfs(start)) {
      return path;
    }
    return null; // пути нет
  }
}

// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('B', 'C');
g.addEdge('A', 'D');
g.addEdge('D', 'C');

console.log(g.findPath('A', 'C')); // ['A', 'B', 'C']

Пример 2: Поиск кратчайшего пути (невзвешённый граф)

class Graph {
  // ... предыдущий код ...

  shortestPath(start, end) {
    const visited = new Set();
    const queue = [[start, [start]]]; // [вершина, путь до неё]
    visited.add(start);

    while (queue.length > 0) {
      const [vertex, path] = queue.shift();

      if (vertex === end) {
        return path;
      }

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          visited.add(neighbor.node);
          queue.push([neighbor.node, [...path, neighbor.node]]);
        }
      }
    }

    return null; // пути нет
  }
}

// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('B', 'C');
g.addEdge('A', 'D');
g.addEdge('D', 'E');
g.addEdge('E', 'C');

console.log(g.shortestPath('A', 'C')); // ['A', 'B', 'C'] (длина 2)
// Не выберет ['A', 'D', 'E', 'C'] (длина 3)

Пример 3: Проверка наличия цикла в графе

class Graph {
  // ... предыдущий код ...

  hasCycle() {
    const visited = new Set();
    const recursionStack = new Set();

    const dfs = (vertex, parent = null) => {
      visited.add(vertex);
      recursionStack.add(vertex);

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        const nextVertex = neighbor.node;

        // Для неориентированного графа проверяем, не родитель ли это
        if (this.isDirected && visited.has(nextVertex) && recursionStack.has(nextVertex)) {
          return true; // цикл найден
        }

        if (!this.isDirected && nextVertex === parent) {
          continue; // пропускаем обратную ссылку
        }

        if (!visited.has(nextVertex)) {
          if (dfs(nextVertex, vertex)) {
            return true;
          }
        }
      }

      recursionStack.delete(vertex);
      return false;
    };

    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        if (dfs(vertex)) {
          return true;
        }
      }
    }

    return false;
  }
}

// Использование
const g1 = new Graph(false);
g1.addEdge('A', 'B');
g1.addEdge('B', 'C');
g1.addEdge('C', 'A'); // цикл!

console.log(g1.hasCycle()); // true

const g2 = new Graph(false);
g2.addEdge('A', 'B');
g2.addEdge('B', 'C');

console.log(g2.hasCycle()); // false

Пример 4: Подсчёт количества связных компонент

class Graph {
  // ... предыдущий код ...

  countConnectedComponents() {
    const visited = new Set();
    let count = 0;

    const dfs = (vertex) => {
      visited.add(vertex);
      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          dfs(neighbor.node);
        }
      }
    };

    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        dfs(vertex);
        count++;
      }
    }

    return count;
  }
}

// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('C', 'D');
g.addEdge('E', 'F');
g.addEdge('F', 'G');

console.log(g.countConnectedComponents()); // 3 компоненты: [A,B], [C,D], [E,F,G]

Пример 5: Поиск всех вершин на определённом расстоянии

class Graph {
  // ... предыдущий код ...

  verticesAtDistance(start, distance) {
    const visited = new Set();
    const queue = [[start, 0]]; // [вершина, расстояние]
    const result = [];

    visited.add(start);

    while (queue.length > 0) {
      const [vertex, dist] = queue.shift();

      if (dist === distance) {
        result.push(vertex);
      }

      if (dist < distance) {
        const neighbors = this.getNeighbors(vertex);
        for (let neighbor of neighbors) {
          if (!visited.has(neighbor.node)) {
            visited.add(neighbor.node);
            queue.push([neighbor.node, dist + 1]);
          }
        }
      }
    }

    return result;
  }
}

// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
g.addEdge('D', 'F');

console.log(g.verticesAtDistance('A', 0)); // ['A']
console.log(g.verticesAtDistance('A', 1)); // ['B', 'C']
console.log(g.verticesAtDistance('A', 2)); // ['D', 'E']
console.log(g.verticesAtDistance('A', 3)); // ['F']

Пример 6: Топологическая сортировка (для ориентированного ацикличного графа)

class Graph {
  // ... предыдущий код ...

  topologicalSort() {
    const visited = new Set();
    const stack = [];

    const dfs = (vertex) => {
      visited.add(vertex);

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          dfs(neighbor.node);
        }
      }

      stack.push(vertex);
    };

    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        dfs(vertex);
      }
    }

    return stack.reverse();
  }
}

// Использование: расписание задач с зависимостями
// Задача B зависит от A, задача D зависит от B и C
const g = new Graph(true);
g.addEdge('A', 'B');
g.addEdge('B', 'D');
g.addEdge('C', 'D');

console.log(g.topologicalSort()); // ['A', 'C', 'B', 'D'] или ['C', 'A', 'B', 'D']
// Суть: A и C выполняются первыми, потом B, потом D

Пример 7: Реальный пример — поиск маршрута между аэропортами

class Graph {
  // ... весь предыдущий код ...
}

// Создаём граф аэропортов
const airports = new Graph(false);
airports.addEdge('JFK', 'LAX');
airports.addEdge('JFK', 'ATL');
airports.addEdge('LAX', 'SFO');
airports.addEdge('ATL', 'DFW');
airports.addEdge('DFW', 'SFO');
airports.addEdge('ATL', 'MIA');

// Найти кратчайший маршрут из JFK в SFO
const route = airports.shortestPath('JFK', 'SFO');
console.log(`Маршрут из JFK в SFO: ${route.join(' → ')}`);
// Маршрут из JFK в SFO: JFK → LAX → SFO (2 перелёта)
// Альтернатива была бы: JFK → ATL → DFW → SFO (3 перелёта)

// Проверить, есть ли прямой путь
const allNeighbors = airports.bfs('JFK');
console.log(`Достижимые из JFK:`, allNeighbors);
// Достижимые из JFK: ['JFK', 'LAX', 'ATL', 'SFO', 'DFW', 'MIA']

---

Сложность алгоритмов

Временная сложность обоих алгоритмов: O(V + E)

• V — количество вершин
• E — количество рёбер
• Мы посещаем каждую вершину один раз и рассматриваем каждое ребро один раз

Пространственная сложность:

• DFS: O(h) где h — глубина графа (из-за рекурсивного стека вызовов)
• BFS: O(w) где w — максимальная ширина на каждом уровне

Практический вывод: для широких графов DFS более экономен по памяти, для глубоких графов BFS.

---

Полный рабочий класс Graph

class Graph {
  constructor(isDirected = false) {
    this.adjacencyList = new Map();
    this.isDirected = isDirected;
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(vertex1, vertex2, weight = 1) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);
    
    this.adjacencyList.get(vertex1).push({ node: vertex2, weight });
    
    if (!this.isDirected) {
      this.adjacencyList.get(vertex2).push({ node: vertex1, weight });
    }
  }

  getNeighbors(vertex) {
    return this.adjacencyList.get(vertex) || [];
  }

  hasVertex(vertex) {
    return this.adjacencyList.has(vertex);
  }

  dfs(startVertex) {
    const visited = new Set();
    const result = [];

    const dfsHelper = (vertex) => {
      visited.add(vertex);
      result.push(vertex);

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          dfsHelper(neighbor.node);
        }
      }
    };

    dfsHelper(startVertex);
    return result;
  }

  bfs(startVertex) {
    const visited = new Set();
    const queue = [startVertex];
    const result = [];

    visited.add(startVertex);

    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          visited.add(neighbor.node);
          queue.push(neighbor.node);
        }
      }
    }

    return result;
  }

  shortestPath(start, end) {
    const visited = new Set();
    const queue = [[start, [start]]];
    visited.add(start);

    while (queue.length > 0) {
      const [vertex, path] = queue.shift();

      if (vertex === end) {
        return path;
      }

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          visited.add(neighbor.node);
          queue.push([neighbor.node, [...path, neighbor.node]]);
        }
      }
    }

    return null;
  }

  hasCycle() {
    const visited = new Set();
    const recursionStack = new Set();

    const dfs = (vertex, parent = null) => {
      visited.add(vertex);
      recursionStack.add(vertex);

      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        const nextVertex = neighbor.node;

        if (this.isDirected && visited.has(nextVertex) && recursionStack.has(nextVertex)) {
          return true;
        }

        if (!this.isDirected && nextVertex === parent) {
          continue;
        }

        if (!visited.has(nextVertex)) {
          if (dfs(nextVertex, vertex)) {
            return true;
          }
        }
      }

      recursionStack.delete(vertex);
      return false;
    };

    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        if (dfs(vertex)) {
          return true;
        }
      }
    }

    return false;
  }

  countConnectedComponents() {
    const visited = new Set();
    let count = 0;

    const dfs = (vertex) => {
      visited.add(vertex);
      const neighbors = this.getNeighbors(vertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor.node)) {
          dfs(neighbor.node);
        }
      }
    };

    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        dfs(vertex);
        count++;
      }
    }

    return count;
  }

  display() {
    for (let [vertex, neighbors] of this.adjacencyList) {
      console.log(`${vertex} →`, neighbors.map(n => n.node).join(', '));
    }
  }
}

---

Заключение

DFS и BFS — это фундаментальные алгоритмы для работы с графами. Оба работают за O(V+E) и выбор между ними зависит от задачи:

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

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