Глубинный обход ориентированного графа

Question

У меня есть задание, в котором я должен написать метод, который выполняет ДПФ ориентированного графа.Вот направленные ребра:

• Узел 1 -> Узел 2, Узел 3

• Узел 2 -> Узел 4

• Узел 3 -> Узел 5

• Узел 4 -> Узел 5

Из моего пониманияпосле просмотра этого видео выполнение ДПФ приведенного выше графика, начиная с узла 1, приведет к выводу 1, 2, 4, 5, 3. Я считаю, что при рассмотрении ребер 1, 2 естественнопредшествует 3, а затем линейно прогрессирует, пока не достигнет 5. Поскольку 5 не имеет никаких других ребер, кроме соединения с 4, обход «раскручивается» обратно к узлу 1, после чего выводится узел 3.

Тем не менее, присваивание ожидает выхода 1, 3, 5, 4, 2. Где проблема в моей логике?

РЕДАКТИРОВАТЬ: я не уверен, какую часть назначения я неправильно понял, но решение состояло в том, что после печати первого элемента, обход узла добавляет его в стек, но ожидаемый результат - порядок, в котором элементыпокинуть стекПеремещаясь по графику, вы начинаете с узла 1 и вначале переходите к узлу 2 (потому что назначение требует выбора между узлами в их естественном порядке), добавляя узел 2 в стек.Затем вы продолжаете обход узлов, к которым ведет узел 2, приводя ваш стек к 2, 4, 5. Затем, возвращаясь к выбору между 2 и 3, вы добавляете 3 к стеку, выскакиваете из каждого элемента стека и выводитеих, как вы идете.Таким образом, сначала печатается 1, затем выталкивая элементы стека, вы получаете 3, 5, 4, 2.

Answer 1

Нет ничего плохого в вашей логике.Ваш результат так же действителен, как и ожидаемый результат (1).

Мое объяснение этого заключается в том, что при взгляде на грани 1, 2 естественно предшествует 3

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

---

(1) Прочитав ответ Габриэля, я должен признать, что не увидел явной ошибки в «ожидаемом»output ":

Если, начиная с узла 1, мы посетим 3 до 2 и затем перейдем к 5, обратный поиск приведет нас обратно к узлу 1, и оттуда сначала должно быть 2, а затем 4: {1, 3, 5, 2, 4}, а не {1, 3, 5, 4, 2}.

Answer 2

Я верю, что ваша логика верна, и правильный ответ 1,2,4,5,3.Присвоение должно иметь ошибку.

Имейте в виду, что если бы узел 3 был посещен до узла 2, то {1,3,5,2,4} также будет приемлемым ответом.