DFS/BFS 탐색 알고리즘 (행렬 구현)

 

DFS / BFS 탐색 알고리즘 코드로 구현하기

 

알고리즘은 형태로 구현합니다.

1. Queue/Stack 에 있는 노드를 꺼내 출력한다.
2. 방금 꺼낸 노드의 자식들을 Queue/Stack에 add/push 한다.
3. Queue/Stack이 비어있지 않다면 1번으로 이동

 

 

 

1. 행렬 구현

아래와 같잉 이진트리를 행렬로 표현하면 그림 1의 표의 내용과 같습니다.

그림 1. 이진 트리 행렬로 표현

 

 

 

2. 코드 구현

그림 1의 내용을 하나씩 탐색하는 코드는 아래와 같습니다.

package java_BFS_DFS_basic;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Matrics_DFS_BFS {
	static Stack<Integer> s = new Stack<Integer>();
	static Queue<Integer> q = new LinkedList<Integer>();
	
	public static void bfs(int start, int[][] map, boolean[] visitied) {
		
		// Queue가 빌때까지 반복
		while(!q.isEmpty()) {
			start = q.peek();
			System.out.print((q.poll()+1)+" ");
			// 1. 자식 노드를 모두 Queue에 삽입
			for(int i=0; i<map.length; i++) {
				if(map[start][i] == 1 && !visitied[i]) { q.add(i); visitied[i] = true;}
			}
		}
	}
	
	public static void dfs(int start, int[][] map, boolean[] visitied) {
		//범위 넘어가면 return
		if(start < 0 || start > map.length) {return ;}
		
		// 1. 출력한다.
		System.out.print((s.pop()+1) +" ");
		
		// 2. 자식 노드를 모두 Stack에 삽입
		for(int i=0; i<map.length; i++) {
			if(map[start][i] == 1 && !visitied[i]) { s.push(i); visitied[i] = true;}
		}
		
		// 3. Stack이 빌때까지 반복
		if(!s.isEmpty()) {
			dfs(s.peek(),map,visitied);
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[][] map = {{1,1,1,0,0,0,0},{1,1,0,1,1,0,0},{1,0,1,0,0,1,1},{0,1,0,1,0,0,0},{0,1,0,0,1,0,0},{0,0,1,0,0,1,0},{0,0,1,0,0,0,1}};
		boolean[] visitied; 
		
		System.out.println("DFS 시작");
		visitied = new boolean[map.length];
		s.push(0);
		visitied[0] = true;
		dfs(0,map,visitied);
		System.out.println();
		System.out.println();
		
		System.out.println("BFS 시작");
		visitied = new boolean[map.length];
		q.add(0);
		visitied[0] = true;
		bfs(0,map,visitied);
	}

}

 

 

3. 결과 값

그림 2. 행렬 순회 결과

 

이렇게 해서 BFS DFS 탐색은 끝!