그래프 용 DFS, 방문한 것으로 표시

Question

(연결 목록) 그래프 용 DFS를 구현 중입니다.

내 그래프 구조의 예 : 당신이 볼 수 있듯이 http://i.imgur.com/Pm9jC.png

, "A"라는 이름의 많은 노드가 있습니다. 그것들은 꼭지점의 관점에서 같지만 노드의 측면에서 실제로 다릅니다. DFS를 구현하는 것은 어떤 시점에서 "a"를 방문하는 것과 관련이 있습니다. 이것은 쉬운 것처럼 보이지만 당신이 내 문제를 여기에서 볼 수 있기를 바랍니다. 방문한 것으로 표시 할 많은 "a"가 있습니다. 내가 여기서 뭔가 잘못하고 있기를 바란다.

문제 : - 먼저 "a"라고 표시 한 다음 스택에 밀어 넣습니다. 이는 효과적으로 방문한 첫 번째 인접 링크 목록의 노드 "a"를 표시하지만 다른 인접 링크 목록의 다른 모든 노드 "a"는 여전히 "방문하지 않음"으로 표시됩니다. - 그런 다음 "b"를 "a"에 대해 처음으로 방문한 인접 꼭지점으로 간주하십시오. 그것을 방문한 것으로 표시하고 스택 위로 밀어 넣습니다. - 이제 우리는 "b"를 탐색 중입니다. 두 번째 인접 링크 목록에서 "b"에 인접한 정점은 "a"이며이 위치는 방문하지 않으므로 스택에 다시 밀어 넣습니다. 잘못된!

당연히, 내가 한 번에 방문한 모든 "a"를 표시하는 markVisit ($ vertex) 메서드를 작성할 수는 있지만 위의 구현에서 올바른 방법이 없다고 생각합니다. 당신의 도움을 주셔서 감사합니다.

Answer 1

markVisit($vertex)이 정확해야합니다. 이미 방문한 정점을 기억해야합니다. DFS는 모서리가 아닌 정점과 관련이 있습니다.