Я сделал программу на Java, которая находит самый дешёвый способ соединить все районы города дорогами.
Использовал два алгоритма: Prim и Kruskal.
Написал Prim’s algorithm
Написал Kruskal’s algorithm
Сделал свои классы Graph.java и Edge.java
Программа читает граф из JSON-файла
Сохраняет результат в output.json
Написал JUnit-тесты
Протестировал на 4 графах: маленьких, среднем и большом
Сравнил время работы и количество операций
Одинаковая ли стоимость у Prim и Kruskal?
Есть ли ровно V - 1 рёбер?
Нет ли циклов?
Что будет, если граф несвязный? → выдаёт ошибку
Время и операции не отрицательные?
Все тесты проходят.
Prim лучше для больших или плотных графов (быстрее).
Kruskal проще писать, но медленнее на больших данных.
Для города с кучей районов я бы выбрал Prim.