Поиск в глубину - Выполнение DFS на дереве

Question

Я пытаюсь выполнить DFS на минимальном остовном дереве, которое содержит 26 узлов. Узлы имеют имена от «A» до «Z», а дерево не является ненаправленным.

У меня есть пустая функция под названием DFS, которую я пытаюсь написать, которая (я предполагаю) принимает в дереве (2D-массив) startNode (случайно выбранный узел 'M') и endNode (случайно выбранный узел ' Z ').

Вес подключенных узлов определяется в параметре 2D-массива, но как мне на самом деле начать посещать узлы?

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

Нужно ли создавать Node_class для каждого узла в массиве 2d ??

Answer 1

При первом глубинном поиске вам просто нужно убедиться, что вы пересекаете всю длину ребра до листового узла, прежде чем двигаться назад вверх по дереву, чтобы получить следующую ветвь. Я не уверен, что понимаю цель проблемы, но я верю в то, к чему вы стремитесь. Чтобы отследить, какой узел посещен и каково общее расстояние / вес до любого данного узла от начального узла, вам необходимо отслеживать дополнительную информацию, а именно, был ли он посещен или еще нет, и каков самый низкий вес для каждого узла , Предполагая, что вы создаете класс-обертку, который будет нести эти две дополнительные части информации, по умолчанию для посещенных будет ложно, а для веса - бесконечность или какое-то очень большое число. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm