DFS와 BFS의 방문처리 시점이 다른 이유,,

DFS와 BFS를 구현할 때 visited 배열 등을 사용해서 방문 처리를 하는데 아래처럼 방문 처리를 해주는 시점이 다르다.

• DFS (재귀)

    public void dfs(int i) {
		visited[i] = true; //방문한 직후 visited 처리	
		for(int j=1; j<n+1; j++) {
			if(map[i][j] == 1 && visited[j] == false) {
				dfs(j);
			}
		}
	}

• BFS

	public void bfs(int i) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(i);
		visited[i] = true;//시작 노드 큐에 넣어주면서 방문하기 전에 visited 처리		
		while(!q.isEmpty()) {
			int temp = q.poll();
			for(int j=1; j<n+1; j++) {
				if(map[temp][j] == 1 && visited[j] == false) {
					q.offer(j);
					visited[j] = true;//나머지 노드도 방문하기 전에 visited 처리
				}
			}
		}
	}

DFS는 노드를 방문하면서 visited 처리를 하고 BFS는 큐에 넣어준 이후 방문하기 전에 visited 처리를 하는데 왜 처리하는 시점이 다른지 궁금해져서 찾아보았다.

• DFS
  DFS는 다음에 탐색하기 위해 스택에 넣어주는 순서와 탐색을 실행하는 순서가 동일하지 않기 때문에 스택에 넣어주면서 방문하기 전에 visited 처리를 할 경우 visited 처리가 되는 순서가 실제 탐색하는 순서와 다르다고 한다,, (재귀로 구현해도 call stack을 사용하므로 동일할 것으로 생각됨..!)
• BFS
  BFS는 탐색하기 위해 큐에 넣어주는 순서와 실제 탐색하는 순서가 일치하기 때문에 방문하기 전 또는 방문한 후 visited 처리를 해줘도 visited 처리가 되는 순서가 실제 탐색하는 순서와 동일하다고 한다,,!

참고

• DFS 와 BFS의 방문처리 시점은 왜 다를까??
• [Java] DFS, BFS 정리