[알고리즘 -2] 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)

그래프를 탐색하는 방법에는 깊이우선탐색(DFS)과 너비우선탐색(BFS)가 있다

 

그래프를 탐색하는 것은 하나의 정점으로 시작해서 모든 정점을 한 번씩 방문하는 것, 즉 방문한 정점은 다시 방문하지 않는다

 

깊이 우선 탐색 (DFS, Depth First Serch)

DFS는 어떤 정점부터 시작해서 다음 분기(branch)로 넘어가기 전에 각 분기마다 가능한 가장 멀리 있는 정점까지 탐색하는 알고리즘

 

- 모든 정점을 방문하고자 하는 경우에 많이 사용한다

- 스택 또는 재귀함수로 구현한다

 

 

 

너비 우선 탐색 (BFS, Breadth First Search)

 

BFS는 어떤 정점부터 시작해서 다음 깊이의 정점로 이동하기 전에 현재 깊이의 모든 정점을 탐색하는 알고리즘

즉, 레벨 별로 탐색한다는 의미이다

 

- 최단 거리를 구하고자 하는 경우에 많이 사용된다

- 큐를 이용해서 구현한다

 

 

 

 

 

DFS vs BFS

 

시간복잡도

인접 리스트로 구현했다면 O(V+E) , 인접행렬로 구현했다면 O(V^2)로 DFS, BFS는 동일하다

DFS	BFS
- 메모리를 덜 쓴다 - 완전탐색의 경우 많이 쓴다 - 코드가 더 짧다 - Stack, 재귀함수로 구현	- 메모리를 더 쓴다 - 그래프 내 최단거리 사용 가능 - 코드가 더 길다 - Queue로 구현

 

 

💻코드로 구현해보기

 

- 컴퓨터에서 그래프를 구현하는 방법에는 인접행렬과 인접리스트가 있는데 그 중에서 인접리스트로 구현해서 탐색할 것이다

 

- 위의 그래프를 DFS의 탐색 순서는 1 → 2 → 4 → 5 → 3 이고, BFS의 탐색 순서는 1 → 2 → 3 → 4 → 5 이다

다음과 같은 결과가 나오도록 코드로 구현해 보았다

 

 

DFS로 탐색하기 (재귀함수)

import java.util.*;
public class Dfs{
	static ArrayList<Integer>[] adjList;
	static int visited[];
	public static void dfs(int u){
		visited[u]=1;
		System.out.print(u+" ");
		for(int v:adjList[u]){
			if(visited[v]==0){ //방문하지 않았을 때 
				dfs(v);
			}
		}
		return;
	}
	public static void main(String[]args){
		int n=5;
		adjList=new ArrayList[n+1];
		visited=new int[n+1];
		
		for(int i=1;i<=n;i++){
			adjList[i]=new ArrayList<>();
		}
		//인접리스트 생성
		adjList[1].add(2);
		adjList[1].add(3);
		adjList[2].add(1);
		adjList[2].add(4);
		adjList[2].add(5);
		adjList[3].add(1);
		adjList[4].add(2);
		adjList[5].add(2);
		
		dfs(1);
	}
}

 

결과는 1 → 2 → 4 → 5 → 3 가 나온 것을 확인 할 수 있다

 

 

BFS로 탐색하기 (Queue)

import java.util.*;
public class Bfs{
	static ArrayList<Integer>[] adjList;
	static int visited[];
	public static void bfs(int u){
		Queue<Integer> queue=new LinkedList<>();
		visited[u]=1;
		queue.add(u);
		while(queue.size()!=0){
			u=queue.poll(); //첫번 째 값 반환하고 제거
			System.out.print(u+" ");
			for(int v:adjList[u]){
				if(visited[v]==0){
					visited[v]=visited[u]+1; //최단거리
					queue.add(v);
				}
			}
		}
		System.out.println();
	}
	public static void main(String[]args){
		int n=5;
		adjList=new ArrayList[n+1];
		visited=new int[n+1];
		
		for(int i=1;i<=n;i++){
			adjList[i]=new ArrayList<>();
		}
		
		adjList[1].add(2);
		adjList[1].add(3);
		adjList[2].add(1);
		adjList[2].add(4);
		adjList[2].add(5);
		adjList[3].add(1);
		adjList[4].add(2);
		adjList[5].add(2);
		
		bfs(1);
		
		System.out.println("1번 부터 5번까지 최단거리 : "+(visited[5]-1));
	}
}

결과는 1 → 2 → 3 → 4 → 5  가 나온 것을 확인 할 수 있다. 또한 최단 거리까지 구할 수 있다