Алгоритм Чу Йонджина и Лю Цзенхонга построения кратчайшего корневого дерева в ориентированном графе

© C.Ю. Пименов, Г.А. Корнеев, А.А. Шалыто

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Проектная документация в формате PDF
Исходные коды

Визуализатор (online)

Аннотация

В проекте разработан визуализатор алгоритма Чу Йонджина и Лю Цзенхонга построения корневого дерева с минимальной суммой весов, содержащихся в нем дуг, во взвешенном ориентированном графе. В визуализатор включено несколько примеров графов, которые позволяют понять как основную идею алгоритма, так и некоторые его особенности. Кроме того имеется возможность редактировать имеющиеся графы и создавать новые, что позволяет проанализировать работу алгоритма в каждом конкретном случае.

Визуализатор построен на базе технологии Vizi. Логика алгоритма реализована с помощью двух автоматов («прямой» и «обратный»), каждый из которых содержит по 28 состояний. Автоматы реализованы с помощью двух операторов switch, один из которых определяет следующее состояние, а другой — действие в текущем состоянии. Оба автомата автоматичестки сгенерированы из XML описания алгоритма.