Уникальная топологическая сортировка для DAG с несколькими решениями tsort

Таким образом, вопрос, который вы задаете, больше относится к семантике программирования, чем к самому алгоритму. Алгоритм топологической сортировки на базовом уровне предполагает, что пользователь будет корректировать алгоритм с учетом того, что ему/ей может потребоваться от алгоритма. Таким образом, чтобы получить решение ABCD, а не решение ACBD, вам нужно будет утверждать в своем алгоритме, что в ситуации, когда есть два возможных кандидата, будет выбран символ с алфавитным приоритетом. Чтобы обобщить это на любой DAG, вы просто указываете его в своем алгоритме.

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

Разве вы не можете использовать стандартную топологическую сортировку с функцией разрешения конфликтов? То есть не используйте подход DFS, а итеративно (или рекурсивно) удаляйте и ставьте в очередь вершины без оставшихся ограничений. Каждый раз, когда доступно более одной неограниченной вершины, используйте функцию разрешения конфликтов для выбора между ними. Ваша функция прерывания связи будет (как я понимаю вашу проблему) просто выбрать вершину, метка которой появляется первой в алфавитном порядке.