Графы: обходы, компоненты, порядок

Перед началом: предыдущий модуль — trie и поиск в строках (13); практически нужны рекурсия (7), обходы деревьев (11), срезы и map (2, 4). Инструменты: Go 1.27, срез как очередь и стек, container/heap — обзорно. Трудоёмкость: ~6 ч (теория 2.5 ч · практика 3.5 ч).

🔥 Инцидент: «Деплой встал на середине: сервис ждал того, кого выкатили позже»

Ночной релиз платформы из двенадцати сервисов. Порядок выката жил в вики и держался на памяти тимлида. После рефакторинга billing начал ходить в pricing — и «примерно правильный» порядок перестал быть правильным: pricing подняли первым, но старая версия billing ещё принимала трафик.

Обнаружилось это на health-check, когда половина сервисов уже была обновлена. Откат занял сорок минут простоя: в вики порядок выглядел логично, но никто не проверял его на согласованность с кодом.

Зависимости сервисов — ориентированный граф, и корректный порядок выката существует ровно тогда, когда в графе нет циклов. В этом модуле считаем такой порядок алгоритмически, а цикл получаем явной ошибкой.

📖 Теория

14.1 Представления графа

go
adj := make([][]int, n)    // вершины 0..n-1: срез срезов, без аллокаций
adj[u] = append(adj[u], v) // ребро u→v
adj[v] = append(adj[v], u) // неориентированное — оба направления

Список смежности — дефолт: O(V+E) памяти, обход только реальных рёбер. Матрица выигрывает на плотных графах, map — когда у вершин произвольные ключи.

14.2 BFS: очередь и волны

BFS обходит граф волнами: расстояние, на котором вершину впервые достали из очереди, в невзвешенном графе — кратчайшее.

go
queue := []int{start}
dist[start] = 0
for len(queue) > 0 {
	v := queue[0]
	queue = queue[1:] // срез вместо container/list: быстрее и проще
	for _, to := range adj[v] {
		if dist[to] == -1 { // первый визит — он же кратчайший
			dist[to] = dist[v] + 1
			queue = append(queue, to)
		}
	}
}

Время O(V+E); память — O(ширины фронта): фронт «широкого» графа держит миллионы вершин.

Показать кодКопировать код

14.3 DFS: рекурсия, стек и цвета

DFS идёт вглубь до упора и откатывается. Рекурсия коротка, но глубину ограничивает стек: путь из миллиона вершин — миллион кадров (модуль 11). Три состояния: белая — не посещалась, серая — в пути, чёрная — обработана.

go
const white, gray, black = 0, 1, 2
func dfs(adj [][]int, v int, color []int, order []int) ([]int, bool) {
	color[v] = gray
	for _, to := range adj[v] {
		if color[to] == gray {
			return order, true // обратное ребро: цикл
		}
		if color[to] == white {
			var cycle bool
			if order, cycle = dfs(adj, to, color, order); cycle {
				return order, true
			}
		}
	}
	color[v] = black
	return append(order, v), false // пост-ордер: вершина после потомков
}

Ребро в серую вершину замыкает цикл, а post-order — основа топосорта: развернули порядок завершения — получили топологический порядок.

14.4 Компоненты, сетка, двудольность

Компоненты — внешний цикл: каждая непосещённая вершина начинает новый обход.

go
for v := 0; v < n; v++ {
	if !seen[v] { // новая компонента связности
		count++
		bfs(adj, v, seen)
	}
}

Сетка — тоже граф: клетка — вершина, соседи — рёбра (4 или 8); flood fill считает «острова».

Двудольность — раскраска в два цвета: одноцветное ребро означает нечётный цикл.

go
if color[to] == -1 {
	color[to] = 1 - color[v]
	queue = append(queue, to)
} else if color[to] == color[v] {
	return false // конфликт: граф не двудольный
}

14.5 Топологическая сортировка

Топологический порядок — линейный порядок, где каждое ребро u→v идёт «вперёд»; он существует ровно для графа без циклов. Kahn: в очередь идут вершины с нулевым in-degree; сняли вершину — уменьшили степени соседей.

go
for len(queue) > 0 {
	v := queue[0]
	queue = queue[1:]
	order = append(order, v)
	for _, to := range adj[v] {
		if indeg[to]--; indeg[to] == 0 {
			queue = append(queue, to)
		}
	}
}
// len(order) < V — в графе цикл, порядка не существует

Kahn устойчив; лексикографически минимальный порядок — срез заменить на кучу из модуля 9.

14.6 Компромиссы

Вывод: обходы любят списки смежности, алгоритмы на рёбрах — edge list, плотные проверки — матрицу; расстояния — BFS, циклы и порядок — цвета или Kahn.

💻 Практика

1. BFS-расстояние в лабиринте. Сетка []string: '.' — проход, '#' — стена, 'S'/'T' — старт и цель. Верните минимальное число шагов (4 направления) или −1: func mazeSteps(grid []string) int. Тесты: один шаг; обход стены «змейкой»; цель недостижима; S == T → 0.
2. Число островов. []string из '0'/'1'; остров — группа единиц, смежных по стороне. Требование: O(rows·cols), вход не мутировать. Тесты: всё вода → 0; всё суша → 1; диагональ не соединяет → 2; «восьмёрка» → 1.
3. Цикл в ориентированном графе. hasCycle(n int, edges [][2]int) bool через цвета white/gray/black, затем та же проверка итеративно. Тесты: самопетля; 2-цикл; ромб 0→1, 0→2, 1→3, 2→3 — цикла нет; DAG и цикл в разных компонентах; цепочка 100 000 вершин — что произойдёт с рекурсивной версией?
4. Порядок курсов (Kahn). orderCourses(n int, prereq [][2]int) ([]int, bool): prereq = [a, b] значит «b до a». Верните порядок курсов или false при цикле. Тесты: цепочка; ромб; два независимых корня; 0↔1 → false; изолированные вершины в ответе. Бонус: минимальный порядок через кучу.
5. Двудольность. isBipartite(adj [][]int) bool — раскраска BFS по всем компонентам. Тесты: отрезок, чётный цикл, дерево — true; треугольник и несвязный граф с недвудольной компонентой — false. Почему раскраска?

🧩 Quiz

✅ Итоги модуля

• Списки смежности — дефолт для обходов; матрица — для плотных графов.
• BFS — очередь и волны: кратчайшие расстояния без весов за O(V+E).
• DFS — рекурсия или стек; цвета white/gray/black дают детект цикла.
• Сетка — тот же граф: flood fill закрывает острова и связность.
• Топосорт: Kahn по in-degree или DFS post-order; порядка нет при цикле.

🔗 Мостик к Модулю 15

Порядок выката построен, расстояния в рёбрах посчитаны. Но BFS мерил путь числом переходов, а у рёбер реальных сетей есть вес: задержка, цена, пропускная способность. В следующем модуле — «Кратчайшие пути, DSU и остовное дерево»: Дейкстра с кучей, Беллман-Форд, Флойд-Уоршелл, DSU и минимальное остовное дерево.