Итак, в топологической сортировке, зависящей от входных данных, обычно существует несколько правильных решений, для которых порядок «графа» может быть «обработан», так что все зависимости располагаются перед «зависимыми» от них узлами. Тем не менее, я ищу немного другой ответ:

Предположим, следующие данные:a -> b а такжеc -> d (a должен прийти раньшеb а такжеc должен прийти раньшеd).
Только с этими двумя ограничениями у нас есть несколько вариантов решения:a b c d, a c d b, c a b d, так далее). Однако я собираюсь создать метод «группировки» этих узлов, чтобы после обработки группы все записи в следующей группе имели свои зависимости. Для вышеупомянутых предполагаемых данных я бы искал группировку как(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.

Есть идеи, как это сделать?

РЕДАКТИРОВАТЬ: Я думаю, что мне удалось собрать воедино некоторый код решения. Спасибо всем, кто помог!

// 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;
}