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