트리구조의 깊이우선탐색, 너비우선탐색

트리구조에 대한 깊이 우선 탐색과 너비 우선 탐색 

BFS는 큐를 이용하여 접속할 노드의 정보를 얻고 먼저 접속한다. 

	package sdk.example;
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* 1 > 2
	* 1 > 3
	* 2 > 4
	* 3 > 4
	* 의 간선을 가지는 그래프를 BFS를 이용하여 처리할
	*
	* @author whitebeard
	*
	*/
	public class BredthFirstSearch {
	public static void main(String[] args) {
	int[][] array = { { 0, 1, 1, 0 },
	{ 1, 0, 0, 1 },
	{ 1, 0, 0, 1 },
	{ 0, 1, 1, 0 } };
	// 방문여부 확인
	int[] visited = new int[4];
	visited[0] = 1;
	// 우선 접근을 위한 큐
	Queue<Integer> queue = new LinkedList<>();
	queue.add(0);
	bfs(array, visited, queue, String.valueOf(0));
	}
	public static void bfs(int[][] array, int[] visited, Queue<Integer> queue, String path) {
	int size = queue.size();
	// 큐에 데이터가 존재하는 만큼 확인
	while(size-- > 0) {
	// 큐의 첫번째 데이터로 접근 가능한 노드를 확인하여 큐에 입력
	int location = queue.poll();
	for(int i = 0; i < array.length; i++) {
	if(array[location][i] == 1 && visited[i] == 0) {
	queue.add(i);
	visited[i] = 1;
	path += String.valueOf(i);
	}
	}
	}
	if(queue.size() != 0)
	bfs(array, visited, queue, path);
	else
	System.out.println(path);
	}
	}

view raw BredthFirstSearch.java hosted with ❤ by GitHub

	package sdk.example;
	/**
	* 1 > 2
	* 1 > 3
	* 2 > 4
	* 3 > 4
	* 의 간선을 가지는 그래프를 DFS를 이용하여 처리할
	*
	* @author whitebeard
	*
	*/
	public class DepthFirstSearch {
	public static void main(String[] args) {
	int[][] array = { { 0, 1, 1, 0 },
	{ 1, 0, 0, 1 },
	{ 1, 0, 0, 1 },
	{ 0, 1, 1, 0 } };
	// 방문 여부 확인
	int[] visited = new int[4];
	visited[0] = 1;
	dfs(array, visited, 0, String.valueOf(0));
	}
	public static void dfs(int[][] array, int[] visited, int location, String path) {
	System.out.println(path);
	for(int i = 0; i < array.length; i++) {
	// 방문 가능하면 우선적으로 접근
	if(array[location][i] == 1 && visited[i] == 0) {
	visited[i] = 1;
	dfs(array, visited, i, path + String.valueOf(i));
	}
	}
	}
	}

view raw DepthFirstSearch.java hosted with ❤ by GitHub