Ключевая наблюдение: в невзвешенном связном графе все ребра имеют одинаковую «стоимость», поэтому минимизация суммы весов сводится к минимизации числа рёбер. Любое остовное дерево связного графа содержит ровно $n-1$ рёбер, где $n$ — число вершин, следовательно любое остовное дерево минимально.
Алгоритм (простая и эффективная реализация):
1. Пусть $G=(V,E)$, $|V|=n$, $|E|=m$. Если граф несвязен, алгоритм строит минимальный остовный лес (по одному дереву на компоненту).
2. Выберите произвольную вершину как корень. Запустите обход в ширину (BFS) или в глубину (DFS).
3. При посещении новой вершины $v$ запомните ребро $(u,v)$ по которому она впервые достигнута (у $u$ уже есть метка). Добавляйте эти ребра в множество $T$.
4. Продолжайте, пока все достижимые вершины не посещены. Если граф несвязен — повторите запуск из непосещённой вершины, чтобы получить остовный лес.
5. В результате $T$ — остовное (если граф связен) дерево с ровно $n-1$ рёбрами (или лес с суммарным числом рёбер $\sum (n_i-1)$ по компонентам).
Обоснование корректности:
- BFS/DFS строит ацикличный связный подграф, включающий все вершины компоненты: это и есть дерево.
- Число рёбер в остове компоненты с $n$ вершинами равно $n-1$; поскольку все рёбра равны, никакой остов не может иметь меньшую суммарную «стоимость».
Сложность:
- Временная: $O(n+m)$ для одного обхода (или для построения леса по всем компонентам).
- Память: $O(n)$ для хранения меток/предков плюс $O(m)$ для представления графа (если используется списковое представление).
Случаи неоднозначности:
- Если в графе есть циклы (обычно), существует множество различных остовных деревьев — выбор зависит от порядка обработки соседей в BFS/DFS (то есть от реализации). Поэтому результат обычно не единственен.
- Если граф несвязен, отсутствует единый остов — существует множество остовных лесов (по одному дереву на компоненту).
- Единственность достигается только в специальных случаях (например, граф уже является деревом, либо введено дополнительное правило детерминированного выбора рёбер).