Как найти минимальное остовное дерево (MST)?

MST — поддерево графа, соединяющее все вершины с минимальной суммой весов рёбер. Два классических алгоритма.

# Kruskal's: sort рёбра, добавлять если не создаёт cycle (через DSU)
def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])
    dsu = DSU(n)
    mst = []
    for u, v, w in edges:
        if dsu.union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst   # O(E log E) из-за сортировки

# Prim's: добавлять минимальное ребро к непосещённой вершине
import heapq
def prim(graph, start):
    visited = set([start])
    heap = [(w, v) for v, w in graph[start]]
    heapq.heapify(heap)
    mst = []
    while heap:
        w, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u); mst.append((u, w))
        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(heap, (w, v))
    return mst   # O(E log V)

Применения: network design (min cost to connect cities), clustering, approximate TSP. В directed graphs MST не определено — есть arborescence (Edmonds).