[그래프] 그래프의 탐색 (DFS, BFS)

그래프의 탐색

• DFS : 깊이 우선 탐색
• BFS : 너비 우선 탐색

깊이 우선 탐색(DFS; Depth First Search)

• 스택(=선행관계)을 이용하여 그래프를 탐색하는 방법
• 나를 먼저 방문하고, 그 다음으로 인접한 노드를 차례로 방문(단, 방문했던 노드는 방문하지 않음)
• 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아간다.

인접 행렬을 이용한 구현 코드

	private static void dfs(int x) {
		check[x] = true;
		System.out.print(x);
		for(int i=1; i<=n; i++){
			if(a[x][i] == 1 && check[y] == false){
				dfs(i);
			}
		}
	}

인접 리스트를 이용한 구현 코드

	private static void dfs(int x) {
		check[x] = true;
		System.out.print(x);
		for(int y : a[x]){
			if(check[y] == false){
				dfs(y);
			}
		}
	}

너비 우선 탐색(BFS; Depth First Search)

• 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
• 큐에 넣을 때 방문했다고 체크해야 함

인접 리스트(Queue)를 이용한 구현 코드

	private static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		check[start] = true;
		while(!q.isEmpty()){
			int x = q.remove();
			System.out.print((x);
			for(int y : a[x]){
				if(check[y] == false){
					check[y] = true;
					q.add(y);
				}
			}
		}
	}