MST Algorithms: Kruskal vs Prim

🔴 Алгоритм Краскала (Edge-based)

Ідея: працюємо з ребрами. Вибираємо найменше ребро, яке не створює цикл.

🟢 Алгоритм Прима (Vertex-based)

Ідея: починаємо з однієї вершини, поступово розширюємо дерево.
1.5s

Порівняння алгоритмів

Характеристика Краскал (Edge-based) Прим (Vertex-based)
Старт Будь-яке ребро Вказана вершина
Основна структура Сортування ребер Черга з пріоритетами
Критерій додавання Вага і відсутність циклу Найменша вага серед прилеглих
Складність O(E log E) O(E + V log V)
Обхід Може бути розрізнений на початку Постійно зв'язаний компонент