Топологическая сортировка на направленных и ненаправленных графах с использованием алгоритма DFS
Я могу определить топологический вид ориентированного графа, используя алгоритм DFS. Если циклов нет, я предполагаю, что найденный топологический порядок верен. Если есть цикл, я предполагаю, что топологический порядок бесполезен. Я прав сейчас?
А как насчет неориентированных графов? Является ли "топологический вид неориентированного графа" верным утверждением? Должен ли граф быть направленным ациклическим графом для топологической сортировки?
2 ответа
Трудно определить, как будет выглядеть или выглядеть топологический порядок неориентированного графа. Топологическое упорядочение ориентированного графа - это такое, при котором для каждого ребра (u, v) в графе u отображается в порядке перед v. Если у вас есть ориентированный граф, ребра (u, v) и (v, u) не совпадают друг с другом, и края имеют четкую начальную и конечную точку.
Однако в неориентированном графе ребра не имеют начальной и конечной точек - узлы либо взаимно смежны, либо взаимно не смежны. Так как будет выглядеть топологический порядок? Учитывая ребро {u, v} = {v, u}, неясно, какой узел должен был бы стоять первым в порядке, поскольку ни один из них не занимал привилегированную позицию над другим.
Ближе всего к тому, что вам нужно в этом случае, порядок, который идет от «листьев» такого графа к центроиду графа. Это означает, что самые правые элементы (или вершина стека) в упорядочении будут иметь минимальную высоту (т.е. расстояние) до любого другого узла в графе. Для этого можно использовать модификацию алгоритма Кана. Вместо того, чтобы начинать с 0 вершин в степени, вы должны начать со всех листьев, имеющих 1 вершину в степени. Помните, что в неориентированном графе все ребра узла являются двунаправленными, поэтому невозможно иметь вершину с нулевой степенью вхождения. Затем вы удаляете все 1 вершины в степени, добавляете в свой стек, обновляете вершины в степени других и повторяете, пока все вершины в графе не будут добавлены в ваш стек.
Использование DFS здесь не имеет смысла, так как ваш результат будет зависеть от порядка исходной вершины в выбранном вами графе.