Tüm bağımlılıkları onlara "bağımlı" düğümleri önce gelen Tamam, böylece veri girişi bağlı topolojik sıralama içinde, grafik sipariş ettiğiniz için birden fazla doğru çözümleri genellikle var yani "işlenmiş" olabilir. Ancak, ben biraz farklı bir cevap arıyorum:

Suppose the following data: a -> b and c -> d (a must come before b and c must come before d).
With just these two constraints we have multiple candidate solutions: (a b c d, a c d b, c a b d, etc). However, I'm looking to create a method of "grouping" these nodes so that after the processing of a group, all of the entries in the next group have their dependencies taken care of. For the above supposed data I'd be looking for a grouping like (a, c) (b, d). Within each group it doesn't matter which order the nodes are processed (a before c or b before d, etc and vice versa) just so long as group 1 (a, c) completes before any of group 2 (b, d) are processed.

The only additional catch would be that each node should be in the earliest group possible. Consider the following:
a -> b -> c
d -> e -> f
x -> y

x y, daha optimal bir çözüm olabilir (a, d, x) (b, e, y) (c, f) çünkü istiyorum önce çünkü (a, d) (b, e, x) (c, f, y) teknik olarak doğru olurdu bir gruplama şeması olan {[ (1)]} grup 2'de x grup 1'de bir düğüm bağımlı olduğunu ima eder.

Bunu yapma hakkında gitmek nasıl bir fikir?

EDIT: Ben bazı çözüm kod birlikte tokat başardı düşünüyorum. Yardım eden herkese teşekkürler!

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