как выбрать начальную точку в ширину первого поиска?

Question

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

Рассматривая приведенный выше пример, он выбирает вершину A в качестве отправной точки и объясняет, что она имеет глубину 0. В моем понимании она имеет глубину 0, поскольку она имеет 0 градусов (без входящих ребер).

Но что, если график не направлен, как мы вычисляем его глубину?

Если я думаю о нем как о дереве, где A - это root, то это Мне кажется, что я назначаю G как root, и, таким образом, на этот раз глубина G будет равна 0. Таким образом, я стану отправной точкой.

Я смотрел лекции, читал статьи, но не могу понять, как найти Правильно ли мое понимание отправной точки в неориентированном графе и для ориентированного графа (0 глубина => 0 в градусах)?

Заранее спасибо.

Answer 1

Нет, ваше понимание неверно. Потому что нет глубины для графа. На графике мы используем начальную точку, это задается установщиком проблемы.

В графе нет глубины.

Давайте возьмем пример: - Какая глубина узла E является вашим примером

- Если мы пойдем по пути A-> B-> E

, то 2

- Если мы пойдем по пути A -> C -> D-> E

, тогда 3

Если в каком-либо узле нет входящего ребра, и вы не сделали не выбирайте его, тогда он не придет в обход. Таким образом, вы выбираете A в качестве начальной точки (вы сказали, что это «глубина 0»).

И в неориентированном графике вы можете выбрать любой узел в качестве начального узла в соответствии с вашим алгоритмом.

Член глубины используется для Древовидная структура данных. Надеюсь, теперь вы понимаете, о чем я говорю.

И я могу очистить ваше замешательство.