graph_algorithm

Мамедов Валентин Юрьевич
Группа 17123
---
Задание: Алгоритм Краскала
Построить минимальный каркас взвешенного связного неориентированного графа
=======
Краткое описание кода
=======
На вход сначала подается число **n** - количество вершин в исходном графе.
Далее вводится **матрица смежности** графа.

На выходе: матрица смежности минимального каркаса взвешенного связного неориентированного графа

[Просмотр кода на Pastebin](https://pastebin.com/gQ35CnyP)
[Тесты программы](https://pastebin.com/cWaJJweq)
=======
Мотивация
=======
Дан взвешенный неориентированный граф. Требуется найти такое поддерево этого графа, которое бы соединяло все его вершины, и при этом обладало наименьшей суммой весов ребер из всех возможных. Такое поддерево называется минимальным каркасом.
=======
Описание алгоритма
=======
Алгоритм изначально помещает каждую вершину в **своё** дерево, затем объединяет на каждой итерации два некоторых дерева некоторым ребром.

Перед началом выполнения алгоритма, все рёбра сортируются по весу (в порядке неубывания). Затем перебираются все рёбра от первого до последнего (в порядке сортировки), и если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро **добавляется** к ответу. По окончании перебора всех рёбер все вершины окажутся принадлежащими одному поддереву.
=======
Это и будет ответом.