[알고리즘] BFS, DFS

비선형 자료구조는 선형 자료구조처럼 전후 관계가 1대1이 아니기 때문에 특별한 방법이 필요하다.

이 특별한 방법이 너비 우선 탐색 (Breadth First Search 이하 BFS), 깊이 우선 탐색 (Depth First Search 이하 DFS) 이다.

BFS

루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드들을 차례로 방문하는 방식

특징: Queue를 사용해 방문 순서를 저장한다

public void bfs() { //이진트리를 배열로 구현했을 때 bfs
	if(isEmpty())return;
	//탐색 순서 번호를 큐로 관리
	Queue<Integer> queue = new LinkedList<>();
	queue.offer(1);
	int current;
	while(!queue.isEmpty()) {
		current = queue.poll();
		System.out.println(nodes[current]);
		if(current*2<=lastIndex) queue.offer(current*2);
		if(current*2+1<=lastIndex) queue.offer(current*2+1);
	}
}
public void bfs2() { //이진트리를 링크드 리스트로 구현한 bfs
	if(isEmpty())return;
	//탐색 순서 번호를 큐로 관리
	Queue<Integer> queue = new LinkedList<>();
	queue.offer(1);
	int current, size, level=0;
	while(!queue.isEmpty()) {
		size = queue.size();
		System.out.print("level"+level +":");
		while(--size>=0) {
			current = queue.poll();
			System.out.print(nodes[current]);
			if(current*2<=lastIndex) queue.offer(current*2);
			if(current*2+1<=lastIndex) queue.offer(current*2+1);
		}
		System.out.println();
		++level;
	}
}

DFS

더 이상 자식이 없을 때 까지 내려갔다가 돌아와서 다음을 방문하는 방식

특징: 재귀나 Stack을 사용해서 구현한다.

//재귀
//전위 순회
public void dfs(int current) {
	if(current>lastIndex)return;
	//VLR
	System.out.println(nodes[current]);
	dfs(current*2);
	dfs(current*2+1);
}
//중위 순회
public void dfs2(int current) {
	if(current>lastIndex)return;
	//VLR
	dfs(current*2);
	System.out.println(nodes[current]);
	dfs(current*2+1);
}			
//후위 순회
public void dfs3(int current) {
	if(current>lastIndex)return;
	//VLR
	dfs(current*2);
	dfs(current*2+1);
	System.out.println(nodes[current]);
}
//스택
private static void dfs(int start) {
	Stack<Integer> S =new Stack<>();
	Arrays.fill(visited, false);
	S.push(start);
	int max = start;
	int level = 0;
	int clevel=0;
	while(!S.isEmpty()) {
		int t = S.pop();
		if(!visited[t]) {
			visited[t] = true;
			for (int i = 0; i < map.length; i++) {
				if(map[t][i] && !visited[i])
					S.push(i);
			}
		}
	}
}