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

수 많은 알고리즘 중 당연히 알고 있어야 하는 기본 알고리즘 중 하나가 DFS와 BFS이다.

오늘은 이 두 가지 알고리즘에 대해 정리를 해보려고 한다.

 

깊이우선"탐색" 과 너비우선"탐색"과 같이 이 알고리즘은 무언가를 탐색하는 것이다.

 

그렇다면 무엇을 탐색하는 것일까?

 

바로 그래프를 탐색하는 알고리즘이다.

 

그렇다면 그래프란 무엇일까?

 

 

---

그래프 (graph)

그래프는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.

 

예를 들어, 지하철 노선도는 많은 역들이 어떻게 연결되어 있는지를 알려주며, 소셜 네트워크 서비스의 인맥 지도는 사람들의 복잡한 친구 관계를 표현한다.

그래프는 선형 자료구조들이나 트리보다 더 일반화 된 자료구조를 제공하고 많은 분야에서 널리 사용되고 있다.

 

 

정점과 간선

그래프는 정점(vertex) 과 간선(edge)의 집합으로 구성되고, 수학적으로는 G = (V, E)와 같이 표시한다.

V(G) 는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다.

정점은 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간선은 이러한 객체 정점들 간의 관계를 의미하는데, 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.

 

정점은 노드(node)라고도 불리며, 간선은 링크(link)라고도 불린다.

 

정점과 간선

 

그래프의 탐색

그래프 탐색은 가장 기본적은 연산으로 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다.

실제로 많은 그래프 문제들이 단순히 정점들을 탐색만으로 해결된다.

 

기본적인 그래프 탐색 방법에는 깊이 우선 탐색과 너비 우선 탐색의 두 가지가 있다.

 

---

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

깊이 우선 탐색 (Depth First Search, DFS)은 스택을 이용한 미로 탐색과 유사하다.

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향을 다시 탐색하는 방법으로 출구를 찾을 수 있었다.

 

1. 그래프에서 깊이 우선 탐색은 먼저 시작 정점에서부터 임의의 인접한 정점으로 깊이 탐색을 진행한다.

2. 이때 방문한 정점은 반드시 방문되었다는 표시를 해야하고, 탐색은 아직 방문하지 않은 인접 정점으로만 가능하다.

3. 만약 더 이상 방문하지 않은 인접 정점이 없으면 가장 마지막에 만났던 정점으로 되돌아간다.

4. 거기서 다시 아직 방문하지 않은 인접 정점을 찾아 다시 동일한 방법의 탐색을 진행한다.

 

 

이 방법은 가장 최근에 만났던 갈림길로 되돌아가야 하므로 스택을 사용하여 구현할 수 있지만,

순환 알고리즘 (재귀)의 형태로 다음과 같이 간단하게 나타낼 수도 있다.

depth_first_search(v)

	v를 방문되었다고 표시;
    for all u ∈ (v에 인접한 정점) do
    	if (u가 아직 방문되지 않았으면)
        	then depth_first_search(u)

 

 

스택에 대해 자세하게 알고 싶다면 다음의 글에서 확인할 수 있다.

https://lucy1215.tistory.com/17

[자료구조] 스택 (Stack)

 

 

 

DFS 진행 방식

다음의 그래프에서 DFS 알고리즘 이용하여 그래프를 탐색하는 과정을 보겠다.

시작정점은 A 으로 선택하였다.

 

 

깊이 우선 탐색의 과정

 

위의 과정으로 실행하게 되면 방문 순서는 A - B - D - C - E - G - H - F가 된다.

 

 

 

 

 

깊이우선탐색(DFS) JAVA 소스코드

Public class DFS_Study {

    // 방문처리에 사용할 배열선언
    static boolean[] visited = new boolean[8];
    
    // 그림예시 그래프의 연결상태를 2차원 배열로 표현
    // 인덱스가 각각의 노드번호가 될 수 있게 0번 인덱스는 아무것도 없는 상태라고 생각한다.
    static char[][] graph = {{}, {2,3}, {1,4}, {1,4}, {2,3,6}, {3,7,8}, {7,8},{6,7}};
    
    public static void main(String[] args) {
    	dfs(1);
    }
    
    static void dfs(int node) {
    	// 방문 처리
        visited[node] = true;
        
        // 방문 노드 출력
        System.out.print(node + " -> ");
        
        // 방문한 노드에 인접한 노드 찾기
        for(int next : graph[node]) {
        	// 인접한 노드가 방문한 적이 없다면 dfs 수행
        	if(!visited[next]) {
            	dfs(next);
            }
        }
    }
}

 

 

 

 

---

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

너비 우선 탐색(Breadth First Search, BFS) 은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례로 저장하고, 들어간 순서대로 꺼낼 수 있는 자료구조가 필요하다. 바로 큐 (Queue)가 사용된다.

 

1. 즉, 정점들이 방문될 때마다 큐에 인접 정점을 삽입하고,

2. 더 이상 방문할 인접 정점이 없는 경우 큐의 맨 앞에서 정점을 꺼내 그 정점과 인접한 정점들을 차례대로 방문한다.

3. 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 공백 상태가 될 때까지 계속한다.

 

 

큐에 대해 자세하게 알고싶다면 다음의 글에서 확인할 수 있다.

https://lucy1215.tistory.com/26

[자료구조] 큐 Queue, 덱 Deque

 

 

 

 

다음은 BFS의 유사 코드이다.

breadth_first_search(v)
	
    v를 방문되었다고 표시;
    큐 Q에 정점 v를 삽입;
    while (not is_empty(Q)) do
    	Q에서 정점 w를 삭제;
        for all u ∈ (w에 인접한 정점) do 
        	if (u가 아직 방문되지 않았으면)
            	then u를 큐에 삽입;
                	 u를 방문되었다고 표시;

 

 

 

 

BFS 진행 방식

DFS에서 다뤘던 그래프를 이번에는 BFS을 이용하여 탐색하는 과정을 보도록 하겠다.

너비 우선 탐색의 과정

위의 과정으로 실행하게 되면 방문 순서는 A - B - C - D - E - F - G - H가 된다.

 

너비 우선 탐색의 특징은 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색을 진행한다는 것이다.

여기서 거리란 시작정점으로부터 어떤 정점까지의 경로 중 가장 짧은 경로의 길이를 뜻한다.

 

즉, 너비 우선 탐색은 거리가 d인 정점들을 모두 방문한 다음, 거리가 (d+1)인 정점들을 모두 방문하게 된다.

거리가 0인 시작 정점으로부터 거리가 1인 모든 정점, 거리가 2인 모든 정점, 거리가 3인 모든 정점 등의 순서대로 방문한다.

 

 

 

 

너비우선탐색(BFS) JAVA 소스코드

Public class BFS_Study {

    // 방문처리에 사용할 배열선언
    static boolean[] visited = new boolean[8];
    
    // 그림예시 그래프의 연결상태를 2차원 배열로 표현
    // 인덱스가 각각의 노드번호가 될 수 있게 0번 인덱스는 아무것도 없는 상태라고 생각한다.
    static char[][] graph = {{}, {2,3}, {1,4}, {1,4}, {2,3,6}, {3,7,8}, {7,8},{6,7}};
    
    public static void main(String[] args) {
    	bfs(1);
    }
    
    static void bfs(int start) {
    	
        // BFS에 사용할 큐를 생성해준다.
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // 큐에 BFS를 시작 할 노드 번호를 넣어준다.
        queue.offer(start);
        
        // 시작노드 방문처리
        visited[start] = true;
        
        // 큐가 빌 때까지 반복
        while(!queue.isEmpty()) {
        	int next = queue.poll();
            
            // 큐에서 꺼낸 노드와 연결된 노드들 체크
            for(int i=0;i<graph[next].length;i++) {
            	int temp = graph[next][i];
                
                // 방문하지 않았으면 방문처리 후 큐에 넣기
                if(!visited[temp]) {
                	visited[temp] = true;
                    queue.offer(temp);
                }
            }
        }
   }
    }
}