04.07.2017
Закрыв практику и уйдя на каникулы, самое время вспомнить конец первого курса и процесс сдачи зачёта по дискретной математике. В то время мы как раз проходили методы обхода графов и нахождения кратчайшего пути. Собственно, решению этой проблемы и посвящена сегодняшняя программа. Я подумал, что было бы интересной задачей основательно разобраться в теме и реализовать демонстрацию работы обходов в ширину, в глубину и алгоритм Дейкстры «вживую».
После получения зачёта кодовая база этого проекта, получается, уже «джва» года лежала мёртвым грузом в приватном репозитории Microsoft Team Foundation Server. Но лучше поздно, чем никогда! Немного поправив оформление кода по советам моего нынче любимого ReSharper'а (да, программа написана на C#) и докинув туда всякой "макулатуры", я выкладываю его на всеобщее обозрение в публичном git-репозитории!
Для запуска требуется .NET Framework 4.5!
Язык описания графа
Вообще, граф рисуется случайным образом (поэтому его можно всегда перестроить, нажав на «Сбросить/обновить», если он построился криво), но его структура и номинальные расстояния между вершинами явно задаются с помощью специального и очень простого описательного языка, состоящего всего из четырёх конструкций:
- AddVertex(<расстояние>); — добавляет к текущей вершине новую через указанное расстояние и переходит на неё.
- Back(); — возвращает указатель текущей вершины на предыдущую.
- JoinVertex(номер вершины, <расстояние>); — соединяет текущую вершину с указанной через переданное расстояние.
- Close(<расстояние>); — соединяет текущую вершину с самой первой через указанное расстояние и переходит на неё.