Graph searching (1) 썸네일형 리스트형 자료구조 - DFS & BFS (Graph Searching) Graph Searching 그래프에서 두 노드 사이에 path를 찾기 위해서는 두 노드사이의 edge들을 찾아서 연결되는지 확인을 해야 하는데 이러한 동작을 하는 방식으로 대표적으로 DFS와 BFS가 있다. DFS DFS는 깊이 우선 방식으로 모든 노드들을 다 방문할 때 현재 노드에서 edge를 통해 갈 수 있는 모든 노드들을 stack에 저장을 한다. 그리고 stack에 pop을 하여 pop이 된 위치에서 갈 수 있는 모든 노드들을 바로 stack에 append 해준다. 만약 이전에 방문했던 노드가 있다면 해당 노드는 다시 방문할 필요가 없으므로 이전에 방문을 하였는지 따로 확인할 수 있는 mark가 필요하다. 이렇게 stack의 모든 노드들이 없어지거나 원하는 노드에 방문할 때까지 반복을 하여 만약.. 이전 1 다음
