Графики, которые заставляют DFS и BFS обрабатывать узлы в одном и том же порядке

Для некоторых графиков алгоритмы поиска DFS и BFS обрабатывают узлы в одном и том же порядке при условии, что они оба начинаются на одном и том же узле. Два примера - графы, которые являются путями, и графы в форме звезды (деревья глубины с произвольным числом детей). Есть ли способ классификации графов, которые удовлетворяют этому свойству? $1$

algorithms graphs graph-traversal saadtaame
источник

Обратите внимание, что в обоих случаях это работает, только если вы начинаете с какого-то определенного узла. Например, если вы выберете центральный узел в длинном пути, вы получите разные порядки от DFS и BFS.

templatetypedef

Есть ли другие интересные возможности, кроме звезды или пути? На первый взгляд может показаться, что если у вас есть вершина с братом и дочерью, то вы сразу получаете разные обходы, поэтому либо у вершины нет детей (кроме корня), и вы получаете звезду, либо у вершины нет родного брата и вы получите путь. Я предполагаю, что клика также работает, но в ней есть и звезда, и путь.

Люк Мэтисон

@LukeMathieson Я думаю о звезде с самым правым ребенком, являющимся корнем другой звезды. Я думаю, это сработало бы. Мы можем даже сделать общее утверждение: если

удовлетворяет свойству, когда поиск начинается в узле v∈V, то и звезда, чей самый правый ребенок

. Еще лучше, если

удовлетворяют свойству, а узел

является последним, обработанным в

- это место, где начинается поиск в

, тогда добавляется ребро моста

G = (V, E)

$G = (V,E)$

= v

$= v$

G_{1}

$G_1$

G_{2}

$G_2$

v_{1}

$v_1$

G_{1}

$G_1$

v_{2}

$v_2$

G_{2}

$G_2$

создает граф, который удовлетворяет свойству. Замена

на

также работает, я думаю.

(v_{1}, v_{2})

$(v_1, v_2)$

v_{1}

$v_1$

v_{2}

$v_2$

saadtaame

Хорошая мысль, так что есть какая-то правильно-рекурсивная композиция, в которой вы можете отождествить правый лист первого графа с корнем второго.

Люк Мэтисон

@LukeMathieson Похоже, вы можете исправить ситуацию, когда у узла

есть родной и дочерний элементы , добавив ребро между этим потомком и родителем

. Вот мое предложение: Дан граф

, если

такой, что

v

$v$

v

$v$

G = (V, E)

$G=(V,E)$

\forall x \in V

$\forall x \in V$

\exists y, z, w \in V

$\exists y,z,w \in V$

(y, x), (z, y), (x, w) \in E

$(y,x),(z,y),(x,w) \in E$ тогда

(x, z) \in E ⟹

$(x,z) \in E \implies$ свойство имеет место для

. Следующий шаг - доказать или опровергнуть это утверждение.

G

$G$

saadtaame

Ответы:

Предположим, что у наших BFS и dfs есть правило начинать с определенного узла, и в каждом двустороннем пути они сначала посещают узел с наименьшей степенью:

ДФС-BFS

начать с самого левого черного узла, затем (BFS и DFS) посетить самый левый красный узел, затем они посетят следующий черный узел и т. д. Чтобы сделать его более общим, можно добавить несколько путей между треугольниками или добавить звезду после окончания треугольников ...

источник

Это правильно, по вашему предположению. Вы подняли хорошую мысль на самом деле; мы должны указать, в каком порядке узлы добавляются в повестку дня (стек или очередь) при выборе.

saadtaame

Принимая во внимание, что LIFO и FIFO для планирования дают DFS и BFS соответственно, можно утверждать, что такое планирование (в котором планирование не может быть стековым или очередным) не является ни поиском по глубине, ни по ширине - хотя вы можете в некоторых случаях описать его тенденцию походить один или другой.

Ниль де Beaudrap

Я думаю , что он может быть реализован в терминах стека или очереди. Он не меняет способ снятия (LIFO или FIFO), он меняет порядок добавления дочерних элементов (в данном случае сначала самая низкая степень).

Samm

@NieldeBeaudrap на самом деле это просто структура, чтобы показать, что где-то оба пути одинаковы.