Как найти длину кратчайшего цикла в графе?
Нужна длина самого короткого цикла (обхвата графа, girth) в невзвешенном неориентированном графе. Через DFS ловлю наличие цикла, но как найти именно МИНИМАЛЬНЫЙ по длине? Перебирать все циклы нереально.
2 ответа
Классический приём: запускаем BFS из каждой вершины и ищем «обратное ребро» — момент, когда BFS встречает уже посещённую вершину НЕ через своего предка. Кратчайший цикл, проходящий через стартовую вершину s, замыкается там, где две BFS-ветви встречаются.
int girth = INT_MAX;
for (int s = 0; s < n; s++) {
vector<int> dist(n, -1), par(n, -1);
queue<int> q; dist[s] = 0; q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : g[v]) {
if (dist[u] == -1) { dist[u] = dist[v]+1; par[u] = v; q.push(u); }
else if (u != par[v]) // обратное ребро (не назад к предку)
girth = min(girth, dist[v] + dist[u] + 1);
}
}
}
Сложность O(V·(V + E)) по времени — BFS из каждой вершины. Для невзвешенного графа это стандарт. girth == INT_MAX означает, что граф ациклический (лес).
Тонкость для неориентированного графа: условие u != par[v] отбрасывает ребро, по которому мы пришли в v (иначе посчитаете «цикл» длины 2 из одного ребра туда-обратно). Если граф взвешенный, BFS не годится — для кратчайшего цикла с весами есть приём на Флойде: перебрать ребро (i,j) и взять dist_без_этого_ребра(i,j) + w(i,j), что аккуратно делается прямо внутри циклов Флойда за O(V³). Для ориентированного графа кратчайший цикл через вершину v = dist(v, v) после Дейкстры/BFS, где старт и финиш — это v.