[알고리즘] 그래프 탐색 - BFS & DFS

1. BFS와 DFS

대표적인 그래프 탐색 알고리즘이다.

• BFS : 너비우선탐색, 정점들과 같은 레벨에 있는 노드들을 먼저 탐색
• DFS : 깊이우선탐색, 정점의 자식들을 먼저 탐색하는 방식

예제

• BFS 방식: A - B - C - D - G - H - I - E - F - J
  - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함

• DFS 방식: A - B - D - E - F - C - G - H - I - J
  - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

2. 그래프 구현

자바

Hashmap과 ArrayList를 이용해 그래프 표현 가능

* Hashmap

HashMap은 '키'와 '값'을 저장하는 자료 구조로, 내부에서 해쉬 함수를 통해, '키' 에 대한 '값' 을 빠르게 검색할 수 있음

그래프를 자료구조로 작성하기

• hashmap 이용

HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();

graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));
graph.put("B", new ArrayList<String>(Arrays.asList("A", "D")));
graph.put("C", new ArrayList<String>(Arrays.asList("A", "G", "H", "I")));
graph.put("D", new ArrayList<String>(Arrays.asList("B", "E", "F")));
graph.put("E", new ArrayList<String>(Arrays.asList("D")));
graph.put("F", new ArrayList<String>(Arrays.asList("D")));
graph.put("G", new ArrayList<String>(Arrays.asList("C")));
graph.put("H", new ArrayList<String>(Arrays.asList("C")));
graph.put("I", new ArrayList<String>(Arrays.asList("C", "J")));
graph.put("J", new ArrayList<String>(Arrays.asList("I")));

3. BFS 알고리즘 구현

• 큐 2개 사용

import java.util.ArrayList;
import java.util.HashMap;

public class BFSSearch {
    public ArrayList<String> bfsFunc(HashMap<String, ArrayList<String>> grpah, String startNode) {
        ArrayList<String> visited = new ArrayList<String>();
        ArrayList<String> needVisit = new ArrayList<String>();
        
        needVisit.add(startNode);
        
        while (needVisit.size() > 0) {
            String node = needVisit.remove(0);
            
            if (!visited.contains(node)) {
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
        return visited;
    }
}

• ArrayList로 큐 2개 구현
  - visited : 이미 방문한 노드
  • needVisit : 방문해야할 노드(자식노드)
  더 이상 방문할 노드가 없을 때 까지(needVisit.size()>0) 반복
  노드를 방문할 때 마다 needVisit 큐에 자식노드들을 넣어줌

시간 복잡도

노드 수 : V
간선 수 : E
시간복잡도 : O(V+E)

4. DFS 알고리즘 구현

• 큐, 스택 사용

  public class DFSSearch {
     public ArrayList<String> dfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {
         ArrayList<String> visited = new ArrayList<String>();
         ArrayList<String> needVisit = new ArrayList<String>();        
         
         needVisit.add(startNode);
         
         while (needVisit.size() > 0) {
             String node = needVisit.remove(needVisit.size() - 1); // BFS와 이 부분만 다름 (큐 -> 스택)
             if (!visited.contains(node)) {
                 visited.add(node);
                 needVisit.addAll(graph.get(node));
             }
         }
         return visited;
     }
  }

• visited : 큐, 방문한 노드

• needVisit : 스택, 방문해야 할 노드

  스택이므로 나중에 들어간 자식을 계속 타고 들어감

시간복잡도

노드 수 : V
간선 수 : E
시간복잡도 : O(V+E)