Графовый алгоритм для рекуррентного разбиения графа на куски с 0 входными ребрами

Question

У меня есть проблема (и я предполагаю решение) следующей проблемы:

Учитывая график зависимости (направленного) некоторых задач (т.е. вам нужно запустить задачу 1,2 до 3 - 1)и 2 - вершины с ребрами, входящими в 3) разбить его на группы вершин, которые могут выполняться параллельно.

Таким образом, в основном все, что нужно сделать, это:

1. Получить все вершиныс 0 ребрами, входящими в них
2. Удалите их из графа, добавьте их в группу
3. Перейдите к 1. для графа без этих вершин или остановитесь, если его нет

И учитывая, что это кажется довольно распространенной проблемой, мне было интересно, есть ли название для этого алгоритма в теории графов?

Answer 1

Я никогда не видел этот алгоритм, но по описанию, которое вы сделаете, я бы описал его как жадную топологическую сортировку в ориентированном ациклическом графе.

Он очень похож на алгоритм Коффмана Грэма , но не является точно таким же; в их алгоритме вершины помечаются по одной, а не группами, и они выбирают их в лексикографическом порядке, чтобы гарантировать уникальность решения. Кажется, проще реализовать их версию алгоритма, поскольку для этого требуется только пометить вершины в графе, не поддерживая список множеств и не удаляя вершины / ребра из графа.

Примечание: график должен быть ацикличным (обычно это должны быть графики планирования, или мы столкнемся с проблемой курицы / яйца), чтобы гарантировать завершение алгоритма.