Алгоритмы с нуля
Связные компоненты: подсчёт островов и заливка
Ты выучил DFS и BFS. Оба начинают от одной вершины и посещают всё достижимое из неё. Но вот загвоздка из последних двух уроков: один обход достигает только один “кусок” графа. Если граф имеет разъединённые части — два отдельных кластера друзей без связи между ними — один BFS никогда не пересечёт разрыв. Так как найти каждый отдельный кусок и сосчитать их? Приём маленький и мощный: перебери все вершины, и каждый раз когда встречаешь вершину которую ещё не посетил, запусти свежий BFS или DFS и увеличь счётчик. Каждый запуск поглощает одну целую связную компоненту. Тот же шаблон решает знаменитую задачу с собеседований “число островов”: сетка из земли и воды это просто граф в маскировке, и каждый остров это связная компонента.
После этого урока ты можешь определить связную компоненту в неориентированном графе (максимальное множество взаимно достижимых вершин). Ты можешь написать алгоритм подсчёта компонент: перебери каждую вершину, запусти BFS или DFS из каждой непосещённой, увеличивай счётчик на каждый запуск. Ты понимаешь почему каждый обход отмечает посещённой ровно одну целую компоненту, так что вершины никогда не считаются дважды. Ты можешь решить сеточный вариант “число островов” / заливку, рассматривая сетку как неявный граф с 4-направленными соседями. Ты знаешь что сложность это O(V + E) для явного графа и O(rows * cols) для сетки. Ты также можешь сформулировать оговорку про ориентированный граф: в ориентированном графе правильные понятия это слабо и сильно связные компоненты, и сильно связным компонентам нужен другой алгоритм (отложен). Следующий урок идёт глубже в структуру графа.
Что это связная компонента?
В неориентированном графе связная компонента это максимальное множество вершин где каждая вершина может достичь каждую другую вершину следуя рёбрам. “Максимальное” значит что ты не можешь добавить ещё вершин в множество и сохранить его связным — компонента уже содержит всё достижимое.
Граф что один единый кусок имеет ровно одну компоненту. Граф разбитый на отдельные кластеры имеет одну компоненту на кластер. Изолированная вершина (без рёбер) это компонента сама по себе.
Пример: граф с тремя компонентами
Component A Component B Component C
0 --- 1 3 5 --- 6
| / |
2 --/ 4
{0, 1, 2} {3, 4} {5, 6}Вершины 0, 1, 2 все взаимно достижимы, так они образуют одну компоненту. 3 и 4 образуют вторую. 5 и 6 образуют третью. Нет ребра соединяющего A, B и C, так этот граф имеет 3 связные компоненты.
Список смежности (неориентированный, так каждое ребро появляется в обоих направлениях):
0: [1, 2]
1: [0, 2]
2: [0, 1]
3: [4]
4: [3]
5: [6]
6: [5]Алгоритм подсчёта компонент
Идея: один BFS (или DFS) из вершины посещает всю её компоненту и ничего больше. Так:
- Создай одно общее множество
visitedдля всего графа. - Установи
count = 0. - Для каждой вершины
vот 0 до V-1:- Если
vне посещена:- Увеличь
count(ты нашёл новую компоненту). - Запусти BFS или DFS из
v. Это отмечает посещённой каждую вершину в компонентеv.
- Увеличь
- Если
- Верни
count.
Общее множество посещённых это ключ. Когда ты позже достигаешь вершину что уже была поглощена более ранним обходом, ты её пропускаешь — так ты никогда не запускаешь второй обход внутри той же компоненты.
Разобранная трассировка на примере
visited = {}, count = 0
v = 0: not visited. count = 1. BFS from 0 marks {0, 1, 2}.
v = 1: visited. skip.
v = 2: visited. skip.
v = 3: not visited. count = 2. BFS from 3 marks {3, 4}.
v = 4: visited. skip.
v = 5: not visited. count = 3. BFS from 5 marks {5, 6}.
v = 6: visited. skip.
Result: count = 3.Каждый запуск обхода выстраивается с ровно одной компонентой, так счётчик равен числу компонент.
Сеточный вариант: число островов
Сетка из клеток это граф в маскировке — неявный граф. Ты не строишь список смежности; соседи вычисляются на лету. Дана сетка где 1 это земля и 0 это вода, сосчитай острова. Остров это группа клеток 1 соединённых горизонтально или вертикально (4 направления: вверх, вниз, влево, вправо — не по диагонали).
1 1 0 0
1 0 0 1
0 0 1 1
0 0 0 1Каждая клетка земли (r, c) имеет до 4 соседей: (r-1, c), (r+1, c), (r, c-1), (r, c+1). Сосед считается только если он внутри сетки и тоже земля. Это ровно тот же шаблон подсчёта компонент:
- Для каждой клетки
(r, c):- Если она земля и не посещена:
- Увеличь счётчик островов.
- Заливка из
(r, c): BFS или DFS по связной земле, отмечая каждую посещённой.
- Если она земля и не посещена:
“Заливка” это просто BFS/DFS на сетке — имя приходит от инструментов заливки которые распространяют цвет по связной области.
В сетке выше: один остров это 0; другой это 3. Итого: 2 острова.
Ориентированные графы: быстрая оговорка
Связные компоненты как описано применяются к неориентированным графам. В ориентированном графе рёбра односторонние, так “достижимый” не симметричен: A может достичь B без B достигающей A. Появляются два уточнённых понятия:
- Слабо связный: связный если ты игнорируешь направления рёбер (рассматриваешь каждое ориентированное ребро как неориентированное). Ты можешь найти слабо связные компоненты ровно тем же алгоритмом выше, запущенным на неориентированной версии.
- Сильно связный: каждая вершина достигает каждую другую следуя направлениям в обе стороны. Поиск сильно связных компонент нужен выделенный алгоритм (Kosaraju или Tarjan), который мы откладываем на более поздний урок.
Для этого урока, оставайся неориентированным: простой шаблон перебери-и-обойди это всё что тебе нужно.
Подсчёт связных компонент (BFS внутри)
1
function countComponents(V, adj) {
2
const visited = new Set();
3
let count = 0;
4
5
// Try every vertex as a potential new starting point
6
for (let v = 0; v < V; v++) {
7
if (!visited.has(v)) {
8
count++; // found a brand-new component
9
bfs(v, adj, visited); // mark its whole component visited
10
}
11
}
12
13
return count;
14
}
15
16
function bfs(start, adj, visited) {
17
const queue = [start];
18
visited.add(start);
19
while (queue.length > 0) {
20
const u = queue.shift();
21
for (const w of adj[u]) {
22
if (!visited.has(w)) {
23
visited.add(w);
24
queue.push(w);
25
}
26
}
27
}
28
}
- L2 Одно общее множество посещённых для всего графа (не на компоненту).
- L3 Счётчик компонент начинается с 0.
- L6 Перебери каждую вершину 0..V-1, так ни одна компонента не пропущена.
- L7 Если v не была достигнута никаким более ранним обходом, она открывает новую компоненту.
- L8 Увеличивай раз на компоненту, не раз на вершину.
- L9 Этот обход отмечает посещённой всю компоненту v, так её другие вершины пропускаются позже.
- L19 Отметка-при-добавлении: каждая вершина входит в очередь ровно раз.
- L22 Исследуй каждого соседа; добавляй только непосещённых.
Запуск на графе из 3 компонент
Число островов (заливка DFS на сетке)
1
function numIslands(grid) {
2
const rows = grid.length;
3
const cols = grid[0].length;
4
let count = 0;
5
6
function flood(r, c) {
7
// Stop at the grid edge or on water/visited cells
8
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
9
if (grid[r][c] !== 1) return;
10
11
grid[r][c] = 0; // sink this cell so it is never revisited
12
flood(r - 1, c); // up
13
flood(r + 1, c); // down
14
flood(r, c - 1); // left
15
flood(r, c + 1); // right
16
}
17
18
for (let r = 0; r < rows; r++) {
19
for (let c = 0; c < cols; c++) {
20
if (grid[r][c] === 1) {
21
count++; // a fresh island
22
flood(r, c); // erase the whole island
23
}
24
}
25
}
26
27
return count;
28
}
- L8 Проверка границ: сосед вне сетки это не валидная клетка.
- L9 Стоп на воде (0) или уже-затопленной земле — это проверка посещённости.
- L11 Отметка посещённой перезаписью земли водой; отдельное множество не нужно.
- L12 Рекурсия в 4 ортогональных соседа (без диагоналей).
- L20 Сканируй каждую клетку; каждая незатопленная клетка земли открывает новый остров.
- L21 Считай раз на остров, потом заливка стирает остаток его.
Запуск числа островов
1
adj = { 0:[1,2], 1:[0,2], 2:[0,1], 3:[4], 4:[3], 5:[6], 6:[5] };
2
visited = new Set();
3
count = 0;
4
for (v = 0; v < 7; v++) { if (!visited.has(v)) { count++; bfs(v); } }
Явный граф: время O(V + E)
Кажется что внешний цикл плюс обход на вершину могут стоить больше, но это не так. Внешний цикл for запускается V раз. Проверка if (!visited.has(v)) это O(1) каждая, так накладные расходы цикла одни это O(V). Обходы, взятые вместе, посещают каждую вершину ровно раз и исследуют каждое ребро ровно раз за весь запуск — потому что общее множество посещённых останавливает любую вершину от входа дважды. Так вся работа BFS/DFS суммируется в O(V + E), не O(V) обходов каждый стоящий O(V + E).
Итого: O(V + E).
Пример: граф с 7 вершинами и 5 неориентированными рёбрами (10 ориентированных записей в списке смежности) запускается за O(7 + 10) ≈ O(17) работы, неважно как разбиты компоненты.
Сетка: время O(rows * cols)
Для задачи островов, пусть R = rows, C = cols. Двойной цикл посещает все R * C клеток. Заливка, суммированная по всем островам, касается каждой клетки константное число раз (раз чтобы затопить её, плюс до 4 проверок соседей). Так итого это O(R * C).
Здесь сетка это неявный граф с V = R * C клеток и максимум E ≈ 2 * R * C рёбер (каждая клетка имеет до 4 соседей, каждое ребро разделено 2 клетками). Так O(V + E) = O(R * C), совпадая с общей формулой.
Память: O(V) (сетка: O(rows * cols))
Множество посещённых хранит до V вершин: O(V). Очередь BFS или стек DFS может удерживать до V вершин в худшем случае: O(V).
Для сетки, если ты топишь клетки на месте (перезаписываешь 1 на 0) тебе не нужно дополнительное множество посещённых — но глубина рекурсии для заливки DFS может достичь O(R * C) в худшем случае (сетка что одна длинная змея земли), что это стоимость стека рекурсии. Итеративная заливка BFS ограничивает размер очереди O(R * C) тоже.
Почему общее множество посещённых имеет значение
Wrong (a fresh visited set per traversal):
Outer loop hits v=1 after the component {0,1,2} was already counted.
With a per-traversal visited set, v=1 looks "unvisited" again.
-> count increments wrongly; the same component is counted 3 times.
Right (one shared visited set):
After BFS from 0, visited = {0,1,2}.
v=1 and v=2 are seen as visited, so they are skipped.
-> each component is counted exactly once.В неориентированном графе, что это связная компонента?
Когда считаешь компоненты, почему множество посещённых должно быть общим для всех обходов (не сброшено на каждый обход)?
В задаче 'число островов', две клетки земли принадлежат одному острову когда они...
Какая сложность по времени подсчёта связных компонент на графе с V вершинами и E рёбрами?
Связные компоненты (как учат здесь) применяются к неориентированным графам. Для ориентированного графа, какое понятие нужен отдельный, более продвинутый алгоритм?
Сетка 4x5 (4 строки, 5 столбцов) дана для задачи числа островов. В терминах итогового числа клеток, сложность по времени это O(rows * cols). Сколько это клеток?
Почему это работает
Почему один обход равен одной компоненте. BFS или DFS запущенный из вершины v посещает ровно множество вершин достижимых из v — не больше, не меньше. В неориентированном графе, “достижимый из v” это точно связная компонента v. Так один запуск покрывает одну целую компоненту, и общее множество посещённых гарантирует что следующий запуск случается только когда ты достигаешь вершину в совсем новой компоненте. Это выравнивание это почему счётчик запусков равен числу компонент.
Частая ошибка
Подсчёт на вершину вместо на запуск. Частая ошибка это увеличивать счётчик каждый раз когда посещаешь вершину, или сбрасывать множество посещённых внутри цикла. Увеличивай только когда начинаешь свежий обход из непосещённой вершины, и держи одно общее множество посещённых для всего запуска. Иначе ты считаешь вершины, не компоненты.
Граничные случаи
Изолированные вершины и пустые сетки. Вершина без рёбер это своя собственная компонента (обход из неё посещает только её саму, потом останавливается). Считай её как любую другую. Для сеток: сетка вся-вода имеет 0 островов; одна клетка земли это 1 остров; цикл и проверки границ обрабатывают пустые строки и неровный ввод пока ты охраняешь grid[0].length когда сетка непустая.
Ещё практика
BFS или DFS — твой выбор. Шаблон подсчёта компонент работает идентично с BFS (очередь) или DFS (рекурсия или стек); оба посещают одну целую компоненту на запуск. Для глубоких, узких форм, рекурсивный DFS рискует глубоким стеком вызовов — предпочти итеративный BFS/DFS или подними лимит стека. Для широких форм, очередь BFS может вырасти большой. Счётчик компонент один и тот же в любом случае.
Объясни что это связная компонента, как работает алгоритм подсчёта компонент, почему общее множество посещённых существенно, как сеточная задача 'число островов' отображается на него, и сложность.
Связная компонента неориентированного графа это максимальное множество взаимно достижимых вершин.
Алгоритм: держи одно общее множество посещённых, перебери каждую вершину, и для каждой непосещённой вершины увеличь счётчик и запусти BFS или DFS. Каждый запуск отмечает посещённой ровно одну целую компоненту, так счётчик равен числу компонент.
Число островов / заливка: сетка это неявный граф с 4-направленными соседями; залей каждую непосещённую клетку земли и считай один остров на запуск — идентичный шаблон.
Ориентированная оговорка: это для неориентированных графов. Ориентированные графы имеют слабо связные компоненты (запусти это на неориентированной версии) и сильно связные компоненты (нужен Kosaraju или Tarjan, отложено).
Время: O(V + E) для явного графа, O(rows * cols) для сетки. Память: O(V).