Хорошо, поэтому при топологической сортировке в зависимости от входных данных обычно имеется несколько правильных решений, для которых порядок «графика» может быть обработан так, чтобы все зависимости приходили к ним, зависящим от них. Тем не менее, я ищу немного другой ответ:
Предположим, что следующие данные: a -> b и c -> d ( a должно быть до того, как b и c должны прийти до d ).
Только с этими двумя ограничениями мы имеем несколько вариантов решений: ( abcd , acdb , cabd и т. Д.). Тем не менее, я ищу создать метод группировки этих узлов, чтобы после обработки группы все записи в следующей группе зависели от зависимостей. Для вышеупомянутых предполагаемых данных я бы искал такую группировку, как (a, c) (b, d) . В каждой группе не имеет значения, в каком порядке обрабатываются узлы ( a до c или b до d и т. Д. И наоборот) до тех пор, пока группа 1 (a, c) завершится до любой из группы 2 (b, d) обрабатываются.
Единственный дополнительный улов будет заключаться в том, что каждый узел должен быть в самой ранней группе. Рассмотрим следующее:
a -> b -> c
d -> e -> f
x -> y
Схема группировки (a, d) (b, e, x) (c, f, y) бы технически правильной, так как x перед y , более оптимальным решением было бы (a, d, x) (b, e, y) (c, f) поскольку из x в группе 2 следует, что x зависел от некоторого узла в группе 1.
Любые идеи о том, как это сделать?
EDIT: Я думаю, мне удалось удалять некоторые решения. Спасибо всем, кто помог!
// Topological sort // Accepts: 2d graph where a [0 = no edge; non-0 = edge] // Returns: 1d array where each index is that node's group_id vector<int> top_sort(vector< vector<int> > graph) { int size = graph.size(); vector<int> group_ids = vector<int>(size, 0); vector<int> node_queue; // Find the root nodes, add them to the queue. for (int i = 0; i < size; i++) { bool is_root = true; for (int j = 0; j < size; j++) { if (graph[j][i] != 0) { is_root = false; break; } } if (is_root) { node_queue.push_back(i); } } // Detect error case and handle if needed. if (node_queue.size() == 0) { cerr << "ERROR: No root nodes found in graph." << endl; return vector<int>(size, -1); } // Depth first search, updating each node with it's new depth. while (node_queue.size() > 0) { int cur_node = node_queue.back(); node_queue.pop_back(); // For each node connected to the current node... for (int i = 0; i < size; i++) { if (graph[cur_node][i] == 0) { continue; } // See if dependent node needs to be updated with a later group_id if (group_ids[cur_node] + 1 > group_ids[i]) { group_ids[i] = group_ids[cur_node] + 1; node_queue.push_back(i); } } } return group_ids; }
Обозначьте все корневые узлы значением уровня 0. Обозначьте всех детей с помощью значения уровня parent + 1. Если, узел пересматривается, то есть уже присвоено значение уровня, проверьте, было ли ранее присвоенное значение ниже нового. Если это так, обновите его с более высоким значением и передайте их потомкам.
теперь у вас столько групп, сколько уникальных меток уровня 0 … K
Недавно я реализовал этот алгоритм. Я начал с подхода, который вы показали, но он не масштабируется до графиков с 20 + миллионами узлов. Решение, с которым я столкнулся, основано на подробном описании этого подхода .
Вы можете думать об этом как о вычислении высоты каждого узла, а затем результат представляет собой группу каждого узла на заданной высоте.
Рассмотрим график:
A -> X
B -> X
X -> Y
X -> Z
Таким образом, желаемый выход равен (A, B), (X), (Y, Z)
Основной подход заключается в том, чтобы найти все, что ничего не использует (A, B в этом примере). Все они находятся на высоте 0.
Теперь удалите A и B из графика, найдите что-нибудь, что теперь ничего не использует (теперь X в этом примере). Таким образом, X находится на высоте 1.
Удалите X из графика, найдите все, что в настоящее время ничего не использует (теперь Y, Z в этом примере). поэтому Y, Z находятся на высоте 2.
Вы можете сделать оптимизацию, осознав тот факт, что вам не нужно хранить двунаправленные края для всего или фактически удалять что-либо из вашего графика, вам нужно знать только количество вещей, указывающих на узел, и узлы, которые, как вы знаете, находятся на следующий высота.
Итак, для этого примера в начале:
Когда вы посещаете узел, уменьшайте количество каждого из узлов, на которые он указывает, если это число обращается в нуль, вы знаете, что узел находится на следующей высоте.