[알고리즘] DFS/BFS - 파이썬, 자바

그래프를 탐색하는 방법인 깊이우선 탐색(DFS), 너비 우선 탐색(BFS)를 알아보자

 

깊이 우선 탐색(DFS)

• 한 지점을 골라서 팔 수 있을 때까지 계속해서 깊게 파다가 아무리 땅을 파도 물이 나오지 않으면, 밖으로 나와 다른 지점을 골라서 다시 깊게 땅을 파는 방법 
• 즉, 루트 노드나 임의 로드에서 출발하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방법으로 탐색하는 방법.
• DFS는 방문한 노드들을 스택 자료구조를 통해 방문했는지 확인한다.
• DFS는 탐색시 해당 노드를 방문했는지 여부를 검사해야 한다. 이를 검사하지 않으면 계속 탐색하게 되어 무한 루프에 빠지게 된다
• 스택(Iterative) 또는 재귀함수(Recursive)로 표현함.
• 재귀함수로 간결하게 구현 가능

 

깊이 우선 탐색(DFS) - 탐색 과정

위의 예제 그래프에서 a를 시작점으로 DFS를 수행하면 다음 과정을 수행한다.

1. A와 인접하고 탐색되지 않은 꼭지점 B와 C가 있다.  B를 탐색한다. ∴ A -B
2. B와 인접하고 탐색되지 않은 꼭지점 D와 E가 있다.  D를 탐색한다. ∴ A -B -D
3. D와 인접하고 탐색되지 않은 꼭지점 G가 있다.  G를 탐색한다.      ∴ A -B -D -G
4. G와 인접하고 탐색되지 않은 꼭지점  I가 있다.  I를 탐색한다.       ∴ A -B -D -G -I
5. I와 인접하고 탐색되지 않은 꼭지점 H가 있다.  H를 탐색한다.       ∴ A -B -D -G -I -H
6. H와 인접하고 탐색되지 않은 꼭지점 E와 F가 있다.  E를 탐색한다. ∴ A -B -D -G -I -H -E
7. E와 인접하고 탐색되지 않은 꼭지점 C가 있다.  C를 탐색한다.       ∴ A -B -D -G -I -H -E -C
8. C와 인접하고 탐색되지 않은 꼭지점 F가 있다.  F를 탐색한다.       ∴ A -B -D -G -I -H -E -C -F

위의 깊이 우선 탐색 과정을 그래프로 나타내면 다음과 같다.

 A - B - D - G - I - H - E - C - F

 

깊이 우선 탐색(DFS) 구현 - 파이썬

DFS - pseudo code (재귀함수 사용)

DFS - pseudo code (스택 사용)

DFS 구현 (재귀함수 사용 - 파이썬)

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

DFS 구현 (재귀함수 사용- 자바)

import java.util.*;

public class Main {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        dfs(1);
    }

}

DFS 구현 (스택 사용- 자바)

// 코드 출처 : https://codingnojam.tistory.com/44

---

너비 우선 탐색(BFS) 

• 여러 지점을 고르게 파보고 물이 나오지 않으면, 파놓은 구덩이들을 다시 좀더 깊게 파는 방법
• 즉, 시작점에서 가장 가까운 노드들을 모두 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회방법
• 두 노드 사이의 최단경로, 임의의 경로를 찾고자 할 때 이 방법을 사용함.
• BFS는 탐색시 해당 노드를 방문했는지 여부를 검사해야 한다. 이를 검사하지 않으면 계속 탐색하게 되어 무한 루프에 빠지게 된다.
• BFS는 방문한 노드들을 저장한 후 꺼내야 한다. 이 때 큐(Queue)자료 구조를 사용하여 구현한다.
• 다익스트라 알고리즘
• 재귀적으로 동작할 수 없다.

 

너비 우선 탐색(BFS) - 탐색 과정

위의 예제 그래프에서 a를 시작점으로 BFS를 수행하면 다음 과정을 수행한다.

1. A와 인접하고 탐색되지 않은 꼭지점 B와 C가 있다. B와 C를 차례로 탐색한다.  ∴ A -B -C
2. B와 인접하고 탐색되지 않은 꼭지점 D와 E가 있다. D와 E를 차례로 탐색한다.  ∴ A -B -C -D -E
3. C와 인접하고 탐색되지 않은 꼭지점 F가 있다. F를 탐색한다.                       ∴ A -B -C -D -E -F
4. D와 인접하고 탐색되지 않은 꼭지점 G가 있다. G를 탐색한다.                     ∴ A -B -C -D -E -F -G
5. E와 인접하고 탐색되지 않은 꼭지점 H가 있다. H를 탐색한다.                     ∴ A -B -C -D -E -F -G -H
6. F와 인접하고 탐색되지 않은 꼭지점이 없다.
7. G와 인접하고 탐색되지 않은 꼭지점  I가 있다.  I를 탐색한다.                     ∴ A -B -C -D -E -F -G -H -I
8. H와 인접하고 탐색되지 않은 꼭지점이 없다.
9. I와 인접하고 탐색되지 않은 꼭지점이 없다.

BFS 탐색 과정을 그래프로 나타내면 다음과 같다.

A - B - C - D - E - F - G - H - I

 

너비 우선 탐색(BFS) 구현

BFS - pseudo code

procedure BFS-iterative(G,v):
  let Q be a queue
  Q.enqueue(v) 
  while Q is not empty
      v = Q.dequeue()
      if v is not labeled as discovered:
          label v as discovered
          for all edges from v to w in G.adjacentEdges(v) do 
              Q.enqueue(w)

BFS 구현 (파이썬)

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

BFS 구현 (자바)

import java.util.*;

public class Main {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // BFS 함수 정의
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드를 방문 처리
        visited[start] = true;
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            System.out.print(x + " ");
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if(!visited[y]) {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        bfs(1);
    }

}

---

DFS vs BFS

출처: http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

 

• BFS가 DFS보다 구현이 조금 더 빠르게 동작함.

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

---

해당 포스트는 다음 교재를 참고하였습니다.

1. C로 배우는 쉬운 자료구조 (개정 3판) - 저. 이지영 (한빛 아카데미)

2. 이것이 코딩 테스트다 with 파이썬 - 저. 나동빈 (한빛 미디어)

---