Выполняй код Python по строкам и следи за графом, очередью и списками. distance[v] — наименьшее число рёбер от старта до вершины v, когда это расстояние уже вычислено.
Соседей рассматриваем по возрастанию номеров. При смене графа, старта или цели опыт начинается заново.
Подсвечена последняя выполненная строка; значения показаны после неё. Строка s = q.popleft() извлекает первый элемент из очереди и сохраняет его в s за один шаг.
Нажми «Следующий шаг», чтобы отметить старт как обнаруженную вершину.
Тёмная карточка — первая в очереди. popleft() извлекает её, append() добавляет новую в конец.
Порядок извлечения: —
Под вершиной d = distance[v]; тире означает, что расстояние ещё не вычислено. Путь к цели покажем после обхода.
x — старт, s — текущая вершина, u — её сосед. adj[s] — список соседей вершины s.
n = 6, граф уже записан в adj, а x равен выбранному старту. Перед каждой попыткой создаём новые списки и пустую очередь. Элемент с индексом 0 не используем: вершины пронумерованы от 1 до n.
from collections import deque visited = [False] * (n + 1) distance = [0] * (n + 1) q = deque()
deque берём из стандартной библиотеки Python. q.append(v) добавляет элемент справа, q.popleft() извлекает слева. При проверке while q пустая очередь считается False, непустая — True.
Подготовка: ни одна строка ещё не выполнена.
adj[s]: —
Условие пока не проверяли.
| v | visited[v] | distance[v] | Состояние |
|---|
Жёлтая ячейка — в неё записали значение на этом шаге. Серый 0 в distance — начальное значение, ещё не вычисленное расстояние. На графе ему соответствует тире.
Тире в карточках s и u означает, что переменной ещё не присвоили значение. После циклов эти переменные сохраняют последние значения: в Python циклы не создают отдельную область видимости.
visited[v] = True означает «вершина уже обнаружена». Её соседи при этом могут быть ещё не обработаны. Поэтому повторную встречу пропускаем через continue.
Если извлекать из очереди прямо сейчас, какую вершину она отдаст? Если очередь пуста, выбери «Ни одной».
В первом графе со стартом 1 остановись на строке 9, когда u = 2. Вершина 2 уже отмечена, но в очереди её ещё нет. Сделай ещё два шага: сначала получим distance[2] = 1, затем q.append(2) добавит её в очередь. Это три разные операции.
В строке 5 popleft() извлекает вершину: она исчезает из очереди и появляется в s. Вершина 5 обнаруживается из 2; при встрече из 3 условие в строке 7 даёт True, а строка 8 выполняет continue. Во втором графе от 1 до 6 пути нет; со стартом 5 путь появится. Если старт совпал с целью, расстояние равно 0.
Дополнительно запоминаем, из какой вершины впервые пришли в каждую новую: parent[u] = s. По этим записям строим путь к цели. Это вспомогательная запись симулятора; в показанном коде Python её нет.