Module: Spanning Trees: Kruskal's Algorithm


Problem

1/4

Алгоритм Крускала: Начало

Theory Click to read/hide

Пример минимального остовного дерева в графе с указанными весами ребер: 


Алгоритм Крускала:

1) Сортиртируем ребра по весу  в порядке неубывания.
2) Формируем список из n деревьев ( каждая вершина это дерево ).
3)  Запускаем процесс объединения этих деревьев в минимальное остовное дерево:
      перебираются все рёбра и если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются.
4) По окончании перебора всех рёбер все вершины окажутся принадлежащими одному поддереву.

Problem

Требуется найти в связном графе остовное дерево минимального веса.
 
Формат входных данных:
 
Первая строка входного файла содержит два натуральных числа N, M - количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei, Wi номера концов ребра и его вес соответственно (1 <= Bi, Ei <= N, 0 <= Wi <= 232-1. N <= 10, M <= 10).
 
Формат выходных данных:
 
Единственная строка выходного файла должна содержать одно натуральное число - вес минимального остовного дерева. 
 
Ввод Вывод
4 4
1 2 1
2 3 2
3 4 5
4 1 4
7