[알고리즘/Java] BFS / DFS

✔ 목차

1. BFS
2. BFS 구현 - Java
3. DFS
4. DFS 구현 - Java
5. 시간복잡도

---

🔎 BFS

너비 우선 탐색 (BFS, Breadth-First Search)

• 시작 정점 방문 후 가까운 정점 우선 방문
• 넓게 탐색하는 방법
• 두 노드 사이 최단 거리, 최단 경로 구할 때 자주 사용
• 장점
  • 최적해 찾음 보장
• 단점
  • 최소 실행보다 오래 걸림

---

💻 BFS 구현 - Java

1. 정점 v 방문한다.
2. 정점 v에 인접한 정점 중 방문하지 않은 정점을 차례로 방문하면서 큐에 넣는다.
3. 인접한 정점 모두 방문했다면 큐에서 dqueue하여 받은 값 정점 v로 설정하고 2를 반복한다.
4. 큐가 공백이라면 탐색 완료한 것이다.

	static boolean[] visit;
    //연결 리스트, 행렬 그래프 중 선택
	static LinkedList<Integer>[] graph;
	static int[][] graph;
    
// 시작 정점 v
	public static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(v); //시작 정점 큐에 넣기
		visit[v] = true; //시작 정점 방문
		
		while(!queue.isEmpty()) {
			int temp = queue.poll(); 
			System.out.println(temp);

			for(int nextV : graph[temp]) {
				if(!visit[nextV]) { 
					queue.add(nextV);
					visit[nextV] = true;
				}
			}
		}		
	}

출력
1 2 3 4 5 6 

---

🔎 DFS

깊이 우선 탐색 (DFS, Dreadth-First Search)

• 시작 정점 방문 후 다음 분기로 넘어가기 전 해당 분기 완벽하게 탐색
• 트리에서 보면 노드 방문 후 자식 노드 우선 방문
• 깊게 탐색하는 방법
• 장점
  • 최선의 경우 빠르게 해를 찾음
• 단점
  • 찾은 해가 최적 해 아닐 가능성 있음
  • 최악의 경우 해 찾는데 가장 오랜 시간 걸림

---

💻 DFS 구현 - Java

1. 정점 v 방문한다.
2. 정점 v에서 인접한 정점 중에 방문하지 않은 정점 w가 있다면 w를 v로 하여 1부터 반복한다(재귀함수 호출).
3. 인접한 정점 모두 방문했다면 스택에서 정점을 꺼내 위를 반복한다.

// 시적 정점 v
	static boolean[] visit;
    //연결 리스트, 행렬 그래프 중 선택
	static LinkedList<Integer>[] graph;
	static int[][] graph;
    
	public static void dfs(int v) {
		visit[v] = true;
		System.out.println(v);
		for(int nextV : graph[v]) {
			if(!visit[nextV]) dfs(nextV);
		}
	}

출력
1 2 4 6 5 3 

---

⏰ 시간복잡도

• BFS DFS 둘의 시간복잡도는 동일하며, 그래프 구현에 따라 시간 복잡가 달라짐
• 연결 리스트로 구현한 그래프: O(n+m)
• 행렬로 구현한 그래프: O(n^2)

구현	시간복잡도
연결리스트	O(n+m)
행렬	O(n^2)

---