Я реализую DFS для графа (связанный список).
Пример структуры моего графа: http://i.imgur.com/Pm9jC.png
Как вы можете видеть, есть много узлов с именем "a",Они одинаковы с точки зрения вершины, но на самом деле они разные с точки зрения узла.Реализация DFS предполагает пометку «a» как посещенную в какой-то момент.Это кажется легким, но я надеюсь, что вы можете увидеть мою проблему здесь.Есть много "а", чтобы отметить как посещенные.Я надеюсь, что я делаю что-то здесь не так.
Проблема: - Сначала пометьте «a» как посещенное и поместите его в стек s.это эффективно помечает узел "a" в 1-м связанном списке смежности как посещенный, но все другие узлы "a" в других связанных списках смежности по-прежнему помечаются как "не посещенные".- Затем рассмотрите «b», поскольку это первая не посещенная смежная вершина с «a».пометить его как посещенный и положить его в стек s.- Сейчас мы исследуем "б".Из 2-го связанного списка смежности, смежная вершина с "b" - это "a", а эта не посещается, поэтому мы снова помещаем ее в стек.Неправильно!
Конечно, я могу написать метод markVisit ($ vertex), который помечает все вхождения «a» как посещенные одновременно, но я не думаю, что у меня есть правильный подход в моей реализации выше.Спасибо за вашу помощь.