Непоследовательность в определении задних ребер ориентированного графа через DFS

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

введите здесь описание изображения

Я ожидал, что для этого ориентированного графа алгоритмы определят только одно обратное ребро, которое я отметил красным: E->B.

Вместо этого, в отличие от моего понимания, алгоритмы могут определять как задний край также край B->E. Различные результаты зависят от обходов графа, например:

Traversal     | Back Edge
-------------------------
A->B->D->E    | E->B
A->C->D->E->B | B->E

Вопрос 1. Верно ли предположить, что задний край графика равен только E->B?

Вопрос 2. Если да, то какой алгоритм может гарантировать правильный обход DFS?


graph algorithm digraphs graph-algorithm depth-first-search
person acornagl    schedule 15.06.2020    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Ответ на вопрос 1. Нет. Поскольку задние границы зависят от дерева DFS.

Определение заднего ребра. Для дерева DFS графа заднее ребро — это ребро от узла к одному из его предков в дереве DFS. Другими словами, заднее ребро — это ребро, соединяющее вершину с вершиной, которая была посещена до ее родителя.

Может быть несколько возможных деревьев DFS в зависимости от порядка узлов в списке смежности или порядка, в котором вы решили посетить узлы.

Таким образом, для particular DFS tree -> Unique set of back edges.

Ответ на вопрос 2. Как уже говорилось, правильного обхода DFS не существует. Для одного и того же дерева или графа может существовать несколько обходов DFS.

person Deepak Tatyaji Ahire    schedule 15.06.2020
comment
Спасибо за ответ. Я работаю над графами потока управления (CFG) и полагаю, что для определения задних ребер CFG мне нужно работать с деревьями доминаторов. - person acornagl; 15.06.2020