728x90
DFS (Depth-First Search)
- 깊이 우선 탐색
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
동작 방식
- Stack 자료구조 이용
- 탐색 시작 노드를 Stack에 삽입하고, 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리하고,
- 방문하지 않은 인접 노드가 있으면 스택에서 최상단 노드를 꺼낸다.
- 위 2, 3번 과정을 더 이상 실행할 수 없을 때까지 반복한다.
- 방문처리
- 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지않게 체크
- 이를 통해 각 노드를 한 번씩만 처리 가능
- 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5
- Stack에 기초하므로 재귀 함수를 이용하여 간결하게 구현 가능
- 소요시간 : O(N)
public class DFSExamRecursion {
//각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
public static boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
// 각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
public static int[][] graph = {{},
{2, 3, 8},
{1, 7},
{1, 4, 5},
{3, 5},
{3, 4},
{7},
{2, 6, 8},
{1, 7}};
public static void main(String[] args){
int start = 1; // 시작 노드
dfs(start);
}
/*
* dfs 알고리즘을 수행하는 함수
* @param v 탐색할 노드
*/
public static void dfs(int v){
// 현재 노드 방문 처리
visited[v] = true;
// 방문 노드 출력
System.out.print(v + "");
// 인접 노드 탐색
for (int i : graph[v]){
// 방문하지 않은 인접 노드 중 가장 작은 노드를 스택에 넣기
if (visited[i]==false){
dfs(i);
}
}
}
}
BFS ( Breadth First Search )
- 너비 우선 탐색
- 가까운 노드부터 탐색
- 멀리를 우선하는 DFS와는 반대
동작과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 위 1, 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
- 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
- BFS는 Queue 자료구조에 기초한다.
- 소요시간 : O(N)
- 일반적인 경우 실제 수행 시간은 DFS보다 빠르다.
- 재귀 함수로 구현하면 컴퓨터 시스템 동작 상 수행 시간이 느려질 수 있기 때문
public class BFS {
public static void main(String[] args){
//각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
int [][]graph = {{},
{2, 3, 8},
{1, 7},
{1, 4, 5},
{3, 5},
{3, 4},
{7},
{2, 6, 8},
{1, 7}};
//각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
int start = 1; // 시작 노드
// 큐 구현
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌때까지 반복
while(!queue.isEmpty()){
// 큐에서 하나의 원소를 뽑아 출력
int v = queue.poll();
System.out.println(v + " ");
// 인접한 노드 중 아직 방문하지 않은 원소들을 큐에 삽입
for (int i : graph[v]){
if (visited[i] == false){
queue.add(i);
visited[i] = true;
}
}
}
}
}