グラフのDFS、訪問時のマーク

Question

（リンクされたリスト）グラフのDFSを実装しています。

マイグラフ構造の例：あなたが見ることができるようにhttp://i.imgur.com/Pm9jC.png

、「A」という名前の多くのノードがあります。それらは頂点に関して同じですが、実際にはノードの点で異なります。 DFSを実装するには、ある時点で訪問した「a」をマークする必要があります。これは簡単ですが、ここで私の問題を見ることができれば幸いです。訪問したことを示す「a」がたくさんあります。私はここで何か間違っていることを願っています。

問題： - 最初に「a」とマークし、スタックに押し込みます。訪問先の第1の隣接リンクリスト内のノード「a」を効果的にマークするが、他の隣接リンクリスト内の他のすべてのノード「a」は依然として「訪問していない」とマークされる。 - "a"に最初にアクセスされなかった隣接頂点であるので、 "b"を考慮してください。それを訪問したものとしてマークし、スタックにプッシュします。 - 今、「b」を探しています。 2番目の隣接リンクリストから、 "b"に隣接する頂点は "a"であり、これは参照されていないので、再びスタックにプッシュします。違う！

もちろん、一度にすべての「a」をマークしたmarkVisit（$ vertex）メソッドを書くことはできますが、上記の実装では正しいアプローチはないと思います。ご協力いただきありがとうございます。

Answer 1

markVisit($vertex)が正しいはずです。すでに訪れた頂点を覚えておく必要があります。 DFSはエッジではなく頂点に関係します。