Графы: BFS, DFS, когда что

Граф — вершины и рёбра. Для сервисов вершина — модуль, таблица, под. Ребро — «зависит от», «зывает», «может перейти».

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

Пример. Карта метро без весов рёбер. BFS найдёт путь с наименьшим числом пересадок: как круги по воде, сначала все соседи, потом соседи соседей. DFS залезет в одну ветку до конца и не обещает кратчайший путь.

BFS идёт вширь: очередь. Первый раз, когда вы пришли в вершину в невзвешенном графе, путь уже кратчайший по числу рёбер.

DFS идёт вглубь: стек или рекурсия. Кратчайший путь не обещает. Зато хорошо ловит циклы (цвета вершин) и строит топологический порядок на DAG — направленном графе без циклов.

Рекурсивный DFS на глубоком графе в Go опасен для стека горутины. Глубокая цепочка зависимостей или цикл без visited упрётся в лимит. Явный стек безопаснее. Без множества visited оба обхода на циклическом графе не закончатся.

BFS и DFS

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

func shortest(adj [][]int, start, goal int) int {
	dist := make([]int, len(adj))
	for i := range dist {
		dist[i] = -1
	}
	dist[start] = 0
	q := []int{start}
	for len(q) > 0 {
		v := q[0]
		q = q[1:]
		if v == goal {
			return dist[v]
		}
		for _, w := range adj[v] {
			if dist[w] == -1 {
				dist[w] = dist[v] + 1
				q = append(q, w)
			}
		}
	}
	return -1
}

// DFS цвета: 0 белый, 1 серый (в стеке), 2 чёрный
// ребро в серую вершину = цикл в направленном графе

Типичные задачи

Цикл в зависимостях модулей или миграций — направленный граф и DFS с тремя цветами. Серая вершина в стеке вызова означает: мы вернулись к предку. BFS тоже обойдёт граф, но классический ответ на цикл в DAG — раскраска DFS или отслеживание «в текущем пути».

• Кратчайший путь в сетке без весов — BFS. Если есть рёбра веса 0 и 1 — 0-1 BFS.
• Dijkstra — неотрицательные веса. С отрицательными — Bellman–Ford, не «просто Dijkstra».
• Топологическая сортировка — только DAG: порядок сборки, порядок миграций, порядок инициализации сервисов.
• Компоненты связности — DFS или BFS от каждой не посещённой вершины.

Зачем это бэкенду

Микросервисы — граф вызовов. Цикл A→B→A на синхронных HTTP — скрытый deadlock по таймаутам. Пайплайн CI — DAG. Иерархия отделов — дерево или DAG, не полный граф. Обход «все подчинённые» — BFS/DFS по списку смежности, не N+1 SQL в цикле, если заранее собрать рёбра.

Пример. Сервис заказов зовёт склад, склад зовёт заказы. Без таймаутов оба ждут друг друга. DFS с цветами на графе зависимостей находит такой цикл ещё на картинке, не в три часа ночи.