DFS/BFS 개념정리

1. DFS(Depth-First Search) : 깊이 우선탐색

=>전체적으로 재귀형식이다. 예제 코드 참고.

큐에 넣어서 구현하는 방식.

최상단 원소를 기준으로 해서 방문하지 않은 인접 노드가 있으면 방문(번호 낮은 인접노드부터)

1-2-7-6

그다음은 8.

돌아가서 3-4-5

 

탐색순서 : 1-2-7-6-8-3-4-5 순으로 깊게 들어가는것을 우선으로 한다.

 

DFS 소스코드 예제

방문하고자 하는 노드번호가 들어왔을때 방문처리true

인접한노드를 for문으로 낮은 인덱스값부터 검사하여 인접하면 방문(dfs재귀)

 

2. BFS(Breadth-First Search) : 너비우선탐색

큐에 넣어서 구현

인접노드중에서 방문하지 않은 노드를 모두 큐에 넣어서(낮은 인덱스부터) 하나씩 뽑으면서 방문하며

방문하지않은 노드를 큐에 계속 넣는다.

 

2를 꺼내서 1과 7중에 방문하지 않은 7을 큐에 넣는다.

그리고 3을꺼내서 4와 5를 큐에 넣는다.

8을 꺼내면 다 방문했기 때문에 아무것도 넣을게 없고,

7을 꺼내면 방문하지 않은 6을 큐에 넣는다.

 

이처럼 순서대로 큐에서 꺼내면서 방문하여 인접노드를 큐에 넣는다.

 

탐색순서 : 1-2-3-8-7-4-5-6

 

java에서 ArrayList는 특정인덱스의 값을 get메소드로 가져올수있다.