Топологическая сортировка с наименьшей доступной вершиной

Я пытаюсь решить проблему на основе TopSort. Поскольку будет несколько действительных отсортированных топологических порядков, мне нужно вывести тот, который лексикографически наименьший, то есть сначала наименьшая доступная вершина.

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

void dfs(int u){

visited[u] = true;
cout<<u<<" ";

list<int>::iterator i;
for(i = adj[u].begin(); i != adj[u].end(); ++i){

if(!visited[*i]){

inedge[*i]--;
if(!inedge[*i]){
pq.push(*i);
}

if(!pq.empty()){
int temp = pq.top();
pq.pop();
dfs(temp);
}
}
}
}

Теперь при первом вызове этой функции очередь с приоритетами содержит только те узлы, для которых inedge [i] = 0 (количество внутренних ребер равно нулю). Я выскакиваю минимальный узел из этой очереди приоритетов u = pq.top()и позвоните dfs(u),

Но мой код дает неправильные результаты. Кто-нибудь может мне помочь, если логика, которую я здесь использовал, неверна?

Мой вход состоит из N неполных последовательностей (с пропущенными числами в каждом из N).
Входные данные:

2
1 3
2 3 4

Выход:

1 2 3 4

Это правильный ожидаемый результат, и мой код генерирует это. Но для ввода данных в этот образ
Входные данные:

6
7 8 9
7 11 9
5 11 2
3 8 9
11 10
3 10

ожидаемый результат:

3 5 7 8 11 2 9 10

Мой код выводит:

3 5 7 8 11 9 2 10

Мой код выводит неверные результаты и для нескольких других тестовых случаев, но я не знаю, как решить эту проблему.

3

Решение

Кажется, проблема в том, что pq.top вызывается до того, как все исходящие ребра текущего узла будут проверены.

Рассмотрим следующий график: узлы: A, B, C; Края A-> B, A-C. Пусть C имеет меньшее значение приоритета, то есть оно должно стоять первым. Во время dfs (A) вы проверяете B перед C. Поскольку он сразу же снова берется из очереди, B обрабатывается первым (но не должно быть). Итак, вставьте все соседние узлы, прежде чем снова запрашивать очередь.

1

Другие решения


По вопросам рекламы [email protected]