Поиск в ширину

При поиске в ширину (breadth-first search — BFS) вершины графа посещаются в порядке возрастания расстояния от начальной вершины. Следовательно, используя поиск в ширину, мы сможем вычислить расстояния от начальной вершины до всех остальных. Однако реализовать поиск в ширину труднее, чем поиск в глубину.

В процессе поиска в ширину мы обходим вершины уровень за уровнем. Сначала посещаются вершины, стоящие от начальной на расстоянии \(1\), затем — на расстоянии \(2\) и т.д. Процесс продолжается, пока не останется не посещенных вершин.

На рисунке ниже показано, как происходит обход графа при поиске в ширину. Предположим, что поиск начинается с вершины \(1\). Сначала мы посещаем вершины \(2\) и \(4\), удаленные на растояние \(1\), затем — вершины \(3\) и \(5\), удаленные на расстояние \(2\), и, наконец, вершину \(6\), удаленную на расстояние \(3\).

Переменная

Реализация

Поиск в ширину труднее реализовать, чем поиск в глубину, потому что алгоритм посещает вершины, находящиеся в разных частях графа. Типичная реализация основана на очереди вершин. На каждом шаге обрабатывается следующий узел из очереди.

В приведенном ниже коде предполагается, что граф представлен списками смежности и что определены следующие структуры данных:

q = deque()
used = [False] * n
dist = [INF] * n

Очередь q содержит вершины, подлежащие обработке в порядке возрастания расстояния. Новые вершины добавляются в конец очереди, а обрабатывается вершина, находящаяся в начале очереди. В массиве used хранится информация о том, какие вершины уже посещались, а в массиве dist — расстояния от начальной вершины до всех остальных вершин графа.

Поиск, начинающийся в вершине x, реализуется следующим образом:

used[x] = True
dist[x] = 0
q.append(x)
while q:
    u = q.popleft()
    # обработать вершину u
    for v in g[u]:
        if used[v]:
            continue
        used[v] = True
        dist[u] = dist[v] + 1
        q.append(v)

Временная сложность поиска в ширину, как и поиска в глубину, равна O(n+m), где n — число вершин, а m — число рёбер.

0-1 BFS

Задача

Дан связный неориентированный граф. Вес его рёбер может быть равен только значениям \(0\) или \(1\). Найдите кратчайшее расстояние между вершинами s и f.

Решение

Если от вершины u до вершины v можно дойти по пути, состоящему из рёбер веса \(0\), то кратчайшие расстояния до этих вершин совпадают.

Заметим тогда, что если в нашем графе оставить только \(0\)-рёбра, то он распадётся на компоненты связности (возможно, некоторые будут иметь размер \(1\)), в каждой из которых ответ одинаковый. Если теперь вернуть \(1\)-рёбра, и сказать, что эти рёбра соединяют не вершины, а компоненты связности, то мы сведём задачу к обычному BFS.

Чтобы решить исходную задачу, необходимо при посещении первой вершины из компоненты обойти всю компоненту, проставив во всех вершинах такой же ответ, как и у первой вершины. Для этого можно запустить BFS на \(0\)-рёбрах.

Заметим, что на самом деле нам не нужно запускать BFS внутри BFS, достаточно при посещении вершины добавлять всех её непосещённых соседей по \(0\)-рёбрам в голову очереди, чтобы обработать их раньше, чем следующие в очереди. Для добавления вершин не только в хвост, но и в голову можно использовать дек.

from collections import deque

INF = 1 << 32

n, m, s, f = map(int, input().split())
s -= 1
f -= 1
g = [[] for _ in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append((v, w))
    g[v].append((u, w))

dist = [INF] * n
dq = deque([s])
dist[s] = 0
while dq:
    u = dq.popleft()
    for v, w in g[u]:
        if dist[u] + w >= dist[v]:
            continue
        dist[v] = dist[u] + w
        if w == 0:
            dq.appendleft(v)
        else:
            dq.append(v)
print(f"{dist[f]}")

Практические задания

Авторизация