Как Краскал и Прим строят минимальное остовное дерево?

Question

Accepted Answer

**Минимальное остовное дерево (MST)** соединяет все вершины взвешенного связного графа с **минимальным общим весом рёбер** и без циклов. **Краскал** и **Прим** — два классических жадных алгоритма.

## Краскал (сортировка рёбер, union-find)

Отсортируйте все рёбра по весу; добавьте самое дешёвое ребро, которое не создаёт цикл.

```python
def kruskal(n, edges):                 # edges: (weight, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # cheapest first
        ru, rv = find(u), find(v)
        if ru != rv:                   # no cycle -> take it
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Прим (рост дерева с мин-кучей)

Начните с любой вершины; многократно добавляйте самое дешёвое ребро, выходящее из текущего дерева.

## Сравнение

| | Краскал | Прим |
|---|--------|------|
| Подход | сортировка рёбер + union-find | рост из узла + куча |
| Время | O(E log E) | O(E log V) |
| Лучше всего для | разреженные графы | плотные графы |

## Когда использовать / ловушки

Используйте MST для **проектирования сетей** — прокладка кабелей, водопровода, кластеризация. Оба являются жадными и доказуемо оптимальны здесь. Краскалу нужен union-find, чтобы эффективно избегать циклов.

## Почему это важно

MST минимизирует стоимость соединения всего — напрямую применимо к инфраструктуре и компоновке сети.

Это чистый случай, когда жадность доказуемо оптимальна, что подкрепляет жадное рассуждение при выборе.

Краскал также демонстрирует union-find — структуру с широким алгоритмическим охватом.

	Краскал	Прим
Подход	сортировка рёбер + union-find	рост из узла + куча
Время	O(E log E)	O(E log V)
Лучше всего для	разреженные графы	плотные графы