Меню
Главная
Случайная статья
Настройки
|
Алгоритм Демукрона — алгоритм решения задачи топологической сортировки, то есть упорядочивания вершин ориентированного ациклического графа по уровням. Уровни нумеруются от 0 до n и отражают зависимость: вершины более высоких уровней зависят от вершин нижележащих. Все дуги направлены от вершин с меньшим уровнем к вершинам с большим.
Содержание
Формулировка
Основная идея алгоритма Демукрона заключается в последовательном удалении из графа вершин с нулевой входящей степенью (входов) и присвоении им уровня. После каждого удаления пересчитываются входящие степени остальных вершин, и процесс повторяется до тех пор, пока не будут обработаны все вершины[1].
Принцип работы
Алгоритм выполняет топологическую сортировку графа по уровням следующим образом:
1. Определяются все вершины, в которые не входит ни одна дуга (входящая степень равна нулю). Эти вершины относятся к нулевому уровню и удаляются из графа вместе с их исходящими дугами.
2. После удаления пересчитываются входящие степени оставшихся вершин. Вновь находятся вершины с нулевой входящей степенью — им присваивается следующий уровень (уровень 1), и они также удаляются.
3. Процесс повторяется до тех пор, пока не будут распределены по уровням все вершины графа.
В реализации алгоритма может использоваться бинарная матрица смежности B размером n n, где b = 1, если из вершины i существует дуга в вершину j, и 0 в инном случае.
На основе матрицы B формируется вектор входных степеней M, в котором m равен сумме значений в столбце j и отражает количество входящих дуг в вершину j.
На каждом шаге алгоритма в векторе M определяются вершины с нулевой входной степенью — они формируют текущий уровень. Соответствующие этим вершинам строки в матрице B обнуляются, после чего значения в векторе M пересчитываются. Процесс повторяется до тех пор, пока все вершины не будут упорядочены по уровням.
Примечания
- Дискретная математика, 2006, с. 351.
Литература- Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.
|
|