DFS для графика, Марк по посещению

Question

Я внедряю DFS для (связанного списка) графика.

Пример моей структуры графика: http://i.imgur.com/pm9jc.png

Как видите, есть много узлов под названием «A». Они одинаковы с точки зрения вершины, но на самом деле они отличаются с точки зрения узла. Реализация DFS включает в себя маркировку «A», как это было посещено в какой -то момент. Это кажется легко, но я надеюсь, что вы увидите мою проблему здесь. Есть много «а», чтобы отметить, как посещалось. Надеюсь, я здесь что -то не так.

Проблема: - сначала отметьте «A», как посещалось, и нажмите на стек. Это эффективно отмечает узел «A» в 1 -м смежном связанном списке, связанном с привязанностью к посещению, но все другие узлы «A» в других связанных списках смежности по -прежнему помечены как «не посещаемые». - Затем рассмотрим «B», поскольку это первая неосвобожденная прилегающая вершина к «A». Отметьте его как посещение, и нажмите на стек. - Теперь мы исследуем "B". Из 2 -го связанного списка смежности соседняя вершина к «B» - «А», и этот не заселен, поэтому мы снова толкаем его на стек. Неправильный!

Конечно, я могу написать метод Markvisit ($ Vertex), который отмечает все входы «A», как это посещалось сразу, но я не думаю, что у меня есть правильный подход в моей реализации выше. Спасибо за вашу помощь.

Answer 1

markVisit($vertex) Должен быть правильным, вам нужно помнить, какие вершины вы уже посетили. DFS касается слов, а не краев.