(リンクされたリスト) グラフの DFS を実装しています。
私のグラフ構造の例: http://i.imgur.com/Pm9jC.png
ご覧のとおり、「a」という名前のノードが多数あります。頂点に関しては同じですが、ノードに関しては実際には異なります。DFS の実装には、「a」をある時点で訪問済みとしてマークすることが含まれます。これは簡単に思えますが、ここで私の問題を確認していただければ幸いです。訪問済みとしてマークする「a」がたくさんあります。ここで何か間違ったことをしているといいのですが。
問題: - 最初に "a" を訪問済みとしてマークし、それをスタック s にプッシュします。これにより、最初の隣接リンク リスト内のノード "a" が訪問済みとして効果的にマークされますが、他の隣接リンク リスト内の他のすべてのノード "a" は依然として "未訪問" としてマークされます。- 次に、「a」に隣接する最初の未訪問の頂点である「b」を検討します。訪問済みとしてマークし、スタック s にプッシュします。- 今は「b」を探っています。2番目の隣接リンクリストから、「b」に隣接する頂点は「a」であり、これは未訪問であるため、再度スタックにプッシュします。違う！
もちろん、「a」のすべての出現を一度に訪問済みとしてマークする markVisit($vertex) メソッドを作成することはできますが、上記の実装では正しいアプローチを持っているとは思いません。ご協力いただきありがとうございます。