Выполняй код C++ по строкам и следи за графом, очередью и массивами. distance[v] — наименьшее число рёбер от старта до вершины v, когда это расстояние уже вычислено.
Соседей рассматриваем по возрастанию номеров. При смене графа, старта или цели опыт начинается заново.
Подсвечена последняя выполненная строка; значения показаны после её выполнения. В строке 5 две операции: чтение q.front() и удаление q.pop(). Симулятор показывает их отдельно.
Нажми «Следующий шаг», чтобы отметить старт как обнаруженную вершину.
Тёмная карточка — первая в очереди. front() читает её, pop() удаляет.
Порядок извлечения: —
Под вершиной d = distance[v]; тире означает, что расстояние ещё не вычислено. Путь к цели покажем после обхода.
x — старт, s — текущая вершина, u — её сосед. adj[s] — список соседей вершины s.
Граф уже записан в adj, а x равен выбранному старту. Очередь пуста. Массивы и очередь объявляем внутри функции обхода. Фигурные скобки явно заполняют массивы значениями false и 0; эту инициализацию мы добавили к фрагменту книги.
#include <queue>
#include <vector>
using namespace std;
// Объявления внутри функции обхода:
const int N = 7; // вершины от 1 до 6
vector<int> adj[N]; // сюда записаны рёбра
queue<int> q;
bool visited[N]{};
int distance[N]{};Подготовка: ни одна строка ещё не выполнена.
adj[s]: —
Условие пока не проверяли.
| v | visited[v] | distance[v] | Состояние |
|---|
Жёлтая ячейка массива — в неё записали значение на этом шаге. Серый 0 в distance — начальное значение, ещё не вычисленное расстояние. На графе ему соответствует тире.
visited = true означает «вершина уже обнаружена». Её соседи при этом могут быть ещё не обработаны. Поэтому повторную встречу пропускаем через continue.
Если извлекать из очереди прямо сейчас, какую вершину она отдаст? Если очередь пуста, выбери «Ни одной».
В первом графе со стартом 1 остановись на строке 9, когда u = 2. Вершина 2 уже отмечена, но в очереди её ещё нет. Сделай ещё два шага: сначала получим distance[2] = 1, затем q.push(2) добавит её в очередь. Это три разные операции.
В строке 5 после front() первый элемент остаётся в очереди; после pop() исчезает. Вершина 5 обнаруживается из 2 и при встрече из 3 пропускается через continue. Во втором графе от 1 до 6 пути нет; со стартом 5 путь появится. Если старт совпал с целью, расстояние равно 0.
Дополнительно запоминаем, из какой вершины впервые пришли в каждую новую: parent[u] = s. По этим записям строим путь к цели. Это вспомогательная запись симулятора; в показанном фрагменте книги её нет.