Поиск в графе: в ширину и в глубину

В 1736 г. Леонард Эйлер доказал, что нельзя пройти по каждому из семи мостов Кёнигсберга ровно один раз, и с этого ответа началась теория графов.

Точки и линии

Граф представляет собой набор точек, их называют вершинами или узлами, соединённых линиями, их называют рёбрами. Идея простая, и она подходит к огромному числу вещей: города, соединённые дорогами, веб-страницы, соединённые ссылками, люди, связанные дружбой, клетки лабиринта, соединённые там, где нет стены. Если задачу нарисовать в виде графа, на вопросы вроде «можно ли добраться отсюда туда?» и «какой путь самый короткий?» отвечает одна и та же горстка алгоритмов.

Как хранить граф в коде

Распространённый способ хранить граф называется списком смежности: для каждой вершины список её соседей. В конспектах курса MIT 6.006 используется именно это, массив или словарь Adj, где Adj[u] перечисляет вершины, соединённые с u. Для графа выше это выглядит так:

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Поиск в ширину: кольцо за кольцом

Поиск в ширину (BFS) исследует граф кольцами вокруг начала. Сначала само начало, на расстоянии 0. Затем все его соседи, на расстоянии 1. Затем каждая новая вершина рядом с ними, на расстоянии 2, и так далее. Для этого он держит очередь, ряд, в котором первым выходит тот, кто первым вошёл. Возьми вершину в начале очереди, посети её и добавь её непросмотренных соседей в конец. Из A в примере BFS посещает A, затем B и C, затем D и E, затем F. Поскольку он движется наружу по одному кольцу, то, впервые достигнув вершины, BFS уже нашёл путь с наименьшим числом рёбер. F находится в 3 рёбрах от A, например A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // первым пришёл, первым ушёл
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Поиск в глубину: как можно дальше, потом назад

Поиск в глубину (DFS) ведёт себя как человек в лабиринте, который держится одной рукой за стену. Он идёт по одному пути так глубоко, как только можно. Дойдя до тупика или до места, где уже был, он возвращается к последней развилке и пробует следующий вариант. Он использует стек вместо очереди, последним пришёл, первым ушёл, и его очень естественно писать рекурсией, где запоминанием занимается стек вызовов. Из A рекурсивный DFS посещает A, B, D, C, E, F. DFS достигает всех вершин, которых достигает BFS, но путь, по которому он идёт, не обязательно самый короткий.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F
}

Что выбрать

В первом лабиринте лаборатории BFS посещает 105 клеток и находит путь из 22 ходов, самый короткий из возможных. DFS случайно ныряет в сторону цели и посещает всего 31 клетку, но его путь занимает 28 ходов. Ни один не дешевле всегда. Оба обрабатывают каждую вершину и каждое ребро фиксированное число раз, поэтому оба работают за время O(V + E) для V вершин и E рёбер. Выбирай BFS, когда нужно наименьшее число шагов: меньше всего ходов в головоломке, меньше всего связей между двумя людьми. Выбирай DFS, когда нужно исследовать всё или проследить выбор до конца: проверить, связаны ли все комнаты лабиринта, или перебирать ходы головоломки по одной линии и возвращаться, когда застрял. Когда у рёбер разная длина, как у дорог, ни одного из них самого по себе не хватает; методы вроде алгоритма Дейкстры расширяют идею BFS расстояниями.