Существуют ли правила выбора первой смежной вершины для прохождения графа?

Question

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

[D] <- [C] <- [A] -> [B]

Я собираюсь начать с вершины А. Вершина A имеет две смежные вершины B и C.

Интересно, какую вершину выбрать первым, чтобы пройти?

Это может быть A, C, D, B или A, B, C, D, какой из них правильный? Есть ли правила?

Answer 1

Краткий ответ: Нет.

Поскольку не существует правильного или канонического порядка вершин графа (в общем случае), такого порядка также нет для алгоритма DFS.

График, хранящийся в виде структуры данных в памяти компьютера, всегда имеет некоторый порядок вершин из-за линейного адресного пространства памяти. В зависимости от меток / свойств, которые вы надеваете на свои вершины, вы можете использовать их для установления явных критериев упорядочения, например, их алфавитный или числовой порядок. В целом это может привести к более детерминированным результатам, но не принесет пользы времени выполнения.

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

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

Answer 2

Нет правил. Любой порядок одинаково правильный. Однако иногда инструктор скажет вам пройти узлы в определенном порядке, например в алфавитном порядке; в этом случае, конечно, делайте то, что говорит ваш инструктор. Но без явных инструкций вы можете перебирать смежные вершины в любом порядке.