Блог

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

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

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

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

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

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