Find if Path Exists in Graph

Q: Зачем BFS нужен массив посещённых узлов?

Без этого цикл вроде 0 → 1 → 2 → 0 будет бесконечно гонять поиск по кругу, а даже без циклов узел с несколькими соседями будет добавляться в очередь по одному разу для каждого соседа. Пометка каждого узла в момент добавления в очередь гарантирует, что он будет обработан один раз, что и ограничивает объём работы величиной O(n + m) .

Q: Что делают сжатие пути и объединение по размеру в структуре «система непересекающихся множеств»?

Они поддерживают деревья неглубокими, чтобы find работал быстро. При объединении по размеру меньшее дерево подвешивается к большему, поэтому глубина узла увеличивается, только когда размер его группы как минимум удваивается, что ограничивает глубину величиной log n . Сжатие путей, или используемое здесь укорачивание путей вдвое, сокращает путь до корня при каждом проходе по нему. Вместе они снижают стоимость каждой операции до α(n) .

ЛегкоГрафы Система непересекающихся множеств

+10

Неориентированный граф содержит n узлов, пронумерованных от 0 до n-1. Каждый элемент [u, v] в edges соединяет узлы u и v, и по ребру можно пройти в любом направлении. Верните true, если по рёбрам можно пройти от source до destination, и false в противном случае. Узел всегда может достичь самого себя.

Функция

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

ninteger: количество узлов
edgesinteger-2d-array: рёбра, каждое из которых — пара [u, v] соединённых узлов
sourceinteger: узел, с которого вы начинаете
destinationinteger: узел, до которого нужно добраться
Возвращаетboolean: объединяет ли какой-либо путь исходный и конечный пути

Ограничения

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] при 0 ≤ u, v ≤ n-1 и u ≠ v
Ни одно ребро не встречается дважды ни в одном направлении.
0 ≤ source, destination ≤ n-1

Примеры

Ввод: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Вывод: true
Пояснение: Путь 0 → 1 → 2 → 3 использует три ребра, поэтому узел 3 достижим. Узлы 4 и 5 образуют отдельную часть, которая этому пути не нужна.

Ввод: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Вывод: false
Пояснение: Из узла 2 можно попасть в 0, а затем в 1, и больше никуда. Узел 4 соединён только с узлом 3, и ни одно ребро не связывает {0, 1, 2} с {3, 4}, поэтому ответ — false.

+16 скрытых тестов при отправке

Дополнительный вопрос

Предположим, что рёбра однонаправленные: [u, v] позволяет пройти только из u в v. Какие из трёх подходов по-прежнему работают и что в них нужно изменить?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Вопрос в том, находятся ли source и destination в одной связной компоненте графа. Медленный способ повторно просматривает список рёбер, пока не будет достигнута ни одна новая вершина. Поиск в ширину по списку смежности обходит каждую вершину и каждое ребро один раз, а структура «система непересекающихся множеств» получает тот же ответ, объединяя группы по мере чтения рёбер, вообще не используя списки соседей.

Обходите края, пока ничего не изменится

Верно, но не успевает на самых больших тестах

Идея

Отмечай каждую вершину, до которой, как ты знаешь, можно добраться, начиная с source. Теперь прочитай список рёбер. Ребро с одним отмеченным концом и одним неотмеченным означает, что можно добраться и до неотмеченного конца, поэтому отметь его. Повторяй весь проход, пока за проход не будет отмечено ничего нового или пока не будет отмечена destination.

Это корректно: вершина на пути длины k от source будет отмечена не позднее чем за k-й проход, а вершина отмечается, только если к ней ведёт ребро от отмеченной вершины. В первом примере за один проход по списку по порядку отмечаются 1, 2 и 3, и на этом всё.

Затраты зависят от порядка рёбер. Если путь указан, начиная с дальнего конца, каждый проход отмечает лишь ещё одну вершину. Тогда путь через 5001 вершину требует 5000 проходов по 5000 рёбрам — 2.5 × 10^7 проверок рёбер, тогда как одного прохода по списку соседей было бы достаточно.

Алгоритм

Создай reached, отметив только source.
Пройдись по каждому ребру [u, v]. Если отмечен ровно один конец, отметь другой и зафиксируй, что произошло изменение.
Повторяй проход, пока происходят изменения и destination остаётся неотмеченным.
Верни, отмечен ли destination.

def validPath(n, edges, source, destination):
    reached = [False] * n
    reached[source] = True
    changed = True
    while changed and not reached[destination]:
        changed = False
        for u, v in edges:
            # An edge with exactly one reached end pulls the other end in.
            if reached[u] != reached[v]:
                reached[u] = reached[v] = True
                changed = True
    return reached[destination]

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

Идея

При таком обходе тратится время на повторное чтение рёбер, концы которых уже давно обработаны. Вместо этого составь для каждого узла список узлов, с которыми он соединён. Каждое ребро [u, v] добавляется в оба списка, потому что по нему можно пройти в обоих направлениях. Затем исследуй граф, двигаясь от source: извлекай узел из очереди и добавляй в неё каждого ещё не посещённого соседа.

Отмечай узел как посещённый, когда добавляешь его в очередь, а не когда извлекаешь. Так ни один узел не попадёт в очередь дважды, и поиск завершится, даже если в графе есть циклы, например 0 → 1 → 2 → 0. Если destination когда-либо будет извлечён из очереди, путь существует. Если очередь опустеет раньше, значит, ты посетил все узлы, достижимые из source, и destination среди них не было.

Каждый узел добавляется в очередь не более одного раза, а каждое ребро просматривается дважды — по одному разу с каждого конца, поэтому временная сложность составляет O(n + m) для m рёбер. Для списков соседей требуется O(n + m) памяти. Очередь вместо рекурсии не даст пути из 5000 узлов переполнить стек вызовов.

Алгоритм

Построй список смежности: для каждого ребра [u, v] добавь v в список u, а u — в список v.
Отметь source как посещённый и помести его в очередь.
Извлеки узел из начала очереди. Если это destination, верни true.
Отметь и добавь в очередь каждого соседа, который ещё не посещён.
Когда очередь опустеет, верни false.

from collections import deque


def validPath(n, edges, source, destination):
    # Each edge goes both ways, so list it under both of its ends.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    seen[source] = True
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for nxt in graph[node]:
            if not seen[nxt]:
                # Mark on push, so no node enters the queue twice.
                seen[nxt] = True
                queue.append(nxt)
    return False

Система непересекающихся множеств

Идея

Вам не нужен путь, важно только, существует ли он. Поэтому рассматривайте граф как группы связанных узлов. Вначале каждый узел — отдельная группа. Ребро [u, v] означает, что u и v принадлежат одной группе, поэтому объедините их группы. После обработки всех рёбер source и destination связаны тогда и только тогда, когда находятся в одной группе.

Храните каждую группу в виде дерева со ссылками parent; корень обозначает группу. find(x) поднимается к корню. Чтобы объединить группы, сделайте один корень потомком другого. Во втором примере [0, 1] и [0, 2] образуют группу {0, 1, 2}, а [3, 4] образует группу {3, 4}; find(2) и find(4) возвращают разные корни, поэтому ответ — false.

Два приёма помогают сохранять деревья плоскими. Подвешивайте меньшую группу под большей, а во время find уменьшайте длину пути вдвое, направляя каждый узел на его прародителя. Вместе они обеспечивают стоимость каждой операции α(n) — обратную функцию Аккермана, значение которой для любых входных данных, с которыми вы когда-либо столкнётесь, остаётся меньше 5. Рёбра считываются один раз, и хранятся только parent и size: требуется O(n) памяти, а списки соседей создавать не нужно.

Алгоритм

Установи parent[x] = x и size[x] = 1 для каждого узла.
Для каждого ребра [u, v] найди корни a и b обоих концов.
Если они различаются, присоедини корень меньшей группы к другой и сложи размеры.
Верни результат проверки, равен ли find(source) find(destination).

def validPath(n, edges, source, destination):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the group's root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        if a != b:
            # Hang the smaller group under the larger one.
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
    return find(source) == find(destination)

Ловушки и крайние случаи

Граф небольшой, но несколько деталей определяют, завершится ли поиск и будет ли ответ правильным.

Добавление каждого ребра только в одном направлении. Граф неориентированный, поэтому [1, 0] должен позволять пройти и из 0 в 1. Односторонний список смежности не учитывает пути, в которых ребро проходится в обратном направлении.
Отметка узлов как посещённых при извлечении из очереди, а не при добавлении в неё. Тогда узел попадает в очередь один раз для каждого соседа, обработанного до него, поэтому в очереди может оказаться до 2m элементов вместо максимум n.
Забыть, что source может совпадать с destination. Ответ будет true, даже если у этого узла вообще нет рёбер.
Использование рекурсивного DFS на длинном пути. Путь через 5000 узлов — это 5000 вложенных вызовов, что превышает стандартное ограничение Python в 1000. Используйте очередь или явный стек.
Сравнение parent[source] и parent[destination] в структуре непересекающихся множеств. Только корни обозначают группу; всегда сравнивайте find(source) с find(destination).
Забыть о смещении в Lua и R, где массивы начинаются с 1: узел x находится по индексу x+1.

Частые вопросы4

Следует ли использовать BFS, DFS или union-find, чтобы проверить, существует ли путь?

Все три имеют линейную или близкую к ней сложность. BFS и DFS могут остановиться, как только достигнут пункта назначения, и могут вернуть сам путь. Для алгоритма union-find не нужен список смежности; он считывает каждое ребро один раз и особенно эффективен, когда для одного и того же графа возникает много вопросов о связности, потому что после объединений для каждого вопроса требуется два вызова find.

Какова временная сложность проверки существования пути в графе?

При использовании BFS или DFS временная и пространственная сложность составляет O(n + m) для n узлов и m рёбер: каждый узел посещается один раз, а каждое ребро проверяется с обоих концов. Структура данных «система непересекающихся множеств» с объединением по размеру и сокращением пути требует O(n + m·α(n)) времени и O(n) памяти, где функция α растёт настолько медленно, что на практике является небольшой константой.

Зачем BFS нужен массив посещённых узлов?

Без этого цикл вроде 0 → 1 → 2 → 0 будет бесконечно гонять поиск по кругу, а даже без циклов узел с несколькими соседями будет добавляться в очередь по одному разу для каждого соседа. Пометка каждого узла в момент добавления в очередь гарантирует, что он будет обработан один раз, что и ограничивает объём работы величиной O(n + m).

Что делают сжатие пути и объединение по размеру в структуре «система непересекающихся множеств»?

Они поддерживают деревья неглубокими, чтобы find работал быстро. При объединении по размеру меньшее дерево подвешивается к большему, поэтому глубина узла увеличивается, только когда размер его группы как минимум удваивается, что ограничивает глубину величиной log n. Сжатие путей, или используемое здесь укорачивание путей вдвое, сокращает путь до корня при каждом проходе по нему. Вместе они снижают стоимость каждой операции до α(n).

Python

def validPath(n, edges, source, destination):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

n = 6
edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
source = 0
destination = 3

Ожидается

true

Find if Path Exists in Graph

Функция

Ограничения

Примеры

Подсказки

Решение

Обходите края, пока ничего не изменится

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

Система непересекающихся множеств

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи