[Java] DFS & BFS

▶︎ DFS & BFS 구현 순서

그래프 출처

1️⃣ DFS - 깊이 우선 탐색

• 하나의 노드를 방문할 때 해당 노드의 자식노드까지 전부 방문할 때까지 재귀함수로 돌아간다.

• 기본 로직

1. 시작 노드 방문처리
2. for(시작 노드의 자식노드 방문 (값이 존재하고, 방문하지 않은 노드일 경우))
   2-1. 재귀 구현

private static void dfs(int start) {
		check[start] = true;
		sb.append(start + " ");
		
		for (int i = 0; i <= node; i++) {
			if (arr[start][i] == 1 && !check[i]) {
				dfs(i);
			}
		}
		
	}

---

2️⃣ BFS - 너비 우선 탐색

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용

• 기본 로직

1. 큐에 값 삽입
2. 방문 처리
3. while (큐가 존재하는 동안)
   3-0. start = 큐.poll()
   3-1. for (start의 자식노드 방문 (값이 존재하고, 방문하지 않았을 경우))
   3-2. q.add(자식노드)
   3-3. 자식노드 방문처리

private static void bfs(int start) {
		q.add(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			start = q.poll();
			sb.append(start + " ");
			
			for (int i = 0; i <=node; i++) {
				if (arr[start][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}
	}