Я пытаюсь разработать алгоритм, чтобы определить, имеет ли ориентированный граф уникальное топологическое упорядочение. Кто-нибудь знает, как писать псевдо-код для этого?Определение того, имеет ли направленный граф уникальное топологическое упорядочение?
Напомним, процедура топологического рода, который короче:
n, который является стоком в графеn и n из графикаЕсли на любой итерации на шаге 2 вы можете выбрать 1 из 2 или более узлов, топологическая сортировка не уникальна. Если в какой-то момент вы застряли перед исчерпанием графика - топологического типа вообще нет.
Также, если на втором шаге нет раковины, нет уникального топологического упорядочения (или, фактически, любого топологического упорядочения). –
@Anonymous Спасибо, добавил, чтобы быть явным в ответе. – amit
Вы что-то сделали сами? Вы пытались это сделать? Из-за этого его отдал. Есть много алгоритмов, чтобы делать то, что вы хотите. – justanothercoder
Звучит как типичная домашняя задача. – Gumbo
Что касается ваших прав: почему вы активно пытаетесь сделать свой вопрос хуже, чем первоначально? – HugoRune