Хорошо, поэтому в топологической сортировке, в зависимости от входных данных, обычно существует несколько правильных решений, для которых порядок «графа» может быть «обработан», так что все зависимости располагаются перед «зависимыми» от них узлами. Однако я ищу немного другой ответ:
Допустим, следующие данные:
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;
}