Мосты и точки сочленения
Находите рёбра и вершины, удаление которых разъединяет граф
«Мосты и точки сочленения» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Уязвимые места в графе
Некоторые части неориентированного графа являются критическими: если их удалить, граф распадётся. Их поиск помогает обнаружить слабые связи.
Что такое мост
Мост — это ребро, удаление которого увеличивает количество связных компонент. Оно является единственным путём между двумя областями графа.
Что такое точка сочленения
Точка сочленения — это вершина, удаление которой нарушает связность графа. В сетях такие единственные точки отказа особенно опасны.
Снова о деревьях DFS
Оба алгоритма выполняются за один DFS, отслеживая время обнаружения и значение low, подобно алгоритму Тарьяна, но для неориентированного графа.
disc = [-1] * n
low = [-1] * nLow означает самую раннюю достижимость
Значение low вершины — это самый ранний идентификатор обнаружения, достижимый из её поддерева DFS, возможно через одно обратное ребро вверх.
Инициализируйте при входе
Когда DFS входит в вершину, установите её disc и low равными значению текущего таймера и переходите к её соседям.
disc[u] = low[u] = timer
timer += 1Условие для моста
После рекурсивной обработки потомка v, если low[v] > disc[u], ни одно обратное ребро не проходит выше u, поэтому ребро u-v является мостом.
if low[v] > disc[u]:
bridges.append((u, v))Условие для точки сочленения
Не являющаяся корнем вершина u — точка сочленения, если для потомка v выполняется low[v] >= disc[u]: поддерево v не может обойти u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Особый случай корня
Корень DFS является точкой сочленения только тогда, когда у него два или более потомка в дереве DFS, поэтому подсчитайте их.
if parent[u] == -1 and children > 1:
art.add(u)Пропускайте ребро к родителю
При обновлении low по обратному ребру не возвращайтесь по ребру к родителю, иначе неправильно определите мосты.
if v != parent[u]:
low[u] = min(low[u], disc[v])Один проход — оба результата
Один DFS одновременно находит все мосты и точки сочленения за O(V + E). Дополнительный обход не нужен.
Быстрая проверка
После рекурсивной обработки потомка v из u вы обнаружили условие low[v] > disc[u]. Что вы нашли?
Итоги: критические рёбра и вершины
Один DFS с disc и low находит всё: low[v] > disc[u] означает мост, а low[v] >= disc[u] — точку сочленения. 🌉
Часто задаваемые вопросы
Урок «Мосты и точки сочленения» бесплатный?
Да — полный текст урока «Мосты и точки сочленения» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Мосты и точки сочленения»?
Находите рёбра и вершины, удаление которых разъединяет граф Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Мосты и точки сочленения»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Топологическая сортировка алгоритмом Кана
- Поиск циклов в ориентированных графах
- Компоненты сильной связности
- Мосты и точки сочленения