Blog For Me

그래프 순회 (graph traversal), 그래프 탐색 (graph search) 하나의 정점에서 시작하여 그래프에 있는 정점을 한번씩 방문하여 처리하는 연산 그래프 탐색 방법에는 깊이 우선 탐색(depth first search: DFS), 너비 우선 탐색(breadth first search: BFS) 가 있다. 깊이 우선 탐색 (dfs 탐색) 시작 정점 v를 결정하여 방문 정점 v에 인접한 정점 중에서 (1) 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 2번의 과정을 반복 (2) 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 스택을 pop하여 받은 가장 마지막 장문 정점을 v로 하여 다시 2번 과정을 반복 스택이 공..