В чем заключается основная идея алгоритма двух китайцев для построения минимального остовного дерева?

Основная идея алгоритма двух китайцев для построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине заключается в постепенном удалении рёбер с минимальным весом из всех рёбер, входящих в каждую вершину, кроме корня. neerc.ifmo.ru wiki.algocourses.ru

Затем для каждой вершины (кроме корня) фиксируется одно ребро нулевого веса. wiki.algocourses.ru Если рассматриваемые рёбра образуют дерево, то алгоритм завершается. wiki.algocourses.ru Если же нет, то находится цикл из этих рёбер, который сжимается: вместо цикла создаётся новая вершина, а рёбра внутри цикла удаляются. wiki.algocourses.ru

Алгоритм был разработан математиками Чу Йонджином и Лю Цзенхонгом. neerc.ifmo.ru

Пользователь

Время добавления