[알고리즘/그래프] 너비 우선 탐색(Breath-first-search, BFS), 깊이 우선 탐색(Depth-first-search, DFS)

깊이 우선 탐색 vs 너비 우선 탐색

너비 우선 탐색(Breath-first-search, BFS)

---

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하여 그래프를 순회한다. 시작 정점을 방문한 뒤, 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문하는식으로 깊이를 더해가며 해당 깊이에 있는 모든 정점을 방문하며 나아가다가 더 이상 방문할 정점이 없을 때 탐색을 종료한다.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• 큐(queue)를 사용하여 구현한다. (방문한 노드들을 차례로 저장한 후 꺼낸다.)

너비 우선 탐색의 동작 방식

1. 루트 노드를 방문한다.
   1. 큐에 방문된 노드를 삽입(enqueue)한다.
   2. 초기 상태의 큐에는 시작 노드만이 저장된다.
2. 큐에서 꺼낸 노드과 인접한 노드들을 차례대로 방문하며 큐에 추가한다.
   1. 큐에서 꺼낸 노드를 방문한다.
   2. 큐에서 꺼낸 노드과 인접한 노드들을 모두 방문한다.
   3. 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
   4. 큐에 방문된 노드를 삽입(enqueue)한다.
3. 큐가 빌 때까지 위 과정을 반복한다.

인접 리스트로 구현한 너비 우선 탐색

public boolean[] visited;
public ArrayList<ArrayList<Integer>> graph;
 
public void bfs(int node) {
  Queue<Integer> queue = new <Integer>LinkedList();

  queue.add(node);
  visited[node] = true;

  while (!queue.isEmpty()) {
    int visitNode = q.poll();

    for (int connectedNode : graph.get(visitNode)) {
      if (visited[connectedNode] == false) {
        queue.add(connectedNode);
        visited[connectedNode] = true;
      }
   }

  ArrayList<Integer> connectableNodeList = graph.get(visitNode);
    for (int i = 0; i < connectableNodeList.size(); i++) {
      int connectedNode = connectableNodeList.get(i);
      if (visited[connectedNode] == false) {
        queue.add(connectedNode);
        visited[connectedNode] = true;
      }
    }
  }
}

인접 행렬로 구현한 너비 우선 탐색

public boolean[] visited;
public int[][] graph = {{}, {2, 3, 8}, {1, 6, 8}, {1, 5}, {5, 7}, {3, 4, 7}, {2}, {4, 5}, {1, 2}};
    
public void bfs(int node) {
  Queue<Integer> queue = new <Integer>LinkedList();

  queue.add(node);
  visited[node] = true;

  while (!queue.isEmpty()) {
    int visitNode = queue.poll();

    for (int i = 0; i < graph[visitNode].length; i++) {
      if (graph[visitNode][i] == 1 && visited[i] == false) {
        queue.add(i);
        visited[i] = true;
      }
    }
  }
}

 

---

깊이 우선 탐색(Depth-first-search, DFS)

---

• 시작 정점으로부터 깊이를 우선적으로 탐색하며 그래프를 순회한다. 2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 깊이 탐색을 통해 방문하여 모든 노드를 탐색한다.
• 모든 경로를 탐색해야하는 경우 사용한다.
• 재귀 호출이나 스택(stack)을 사용하여 구현한다.

깊이 우선 탐색의 동작 방식

1. 루트노드를 방문한다.
2. 루트노드와 인접하고 방문된 적 없는 노드를 방문한다. (가장 깊은 노드까지)
3. 인접하고 방문된 적 없는 노드가 없을 경우 (가장 깊은 노드를 방문한 뒤) 갈림길로 돌아와 다른 방향의 노드를 방문한다.
4. 위 과정을 반복한다.

인접 리스트로 구현한 깊이 우선 탐색

public boolean[] visited;
public ArrayList<ArrayList<Integer>> graph;

public void dfsSimple(int node) { // node == node index
    visited[node] = true;

    for (int connectNode: graph.get(node)) {
        if (visited[connectNode] == false) {
            dfs(connectNode);
        }
    }
}

인접 행렬로 구현한 깊이 우선 탐색

public boolean[] visited;
public int[][] graph;

public void dfs(int node) { 
    visited[node] = true;

    for (int i = 0; i < graph[node].length; i++) {
        if (graph[node][i] == 1 && visited[i] == false) {
            dfs(i);
        }
    }
}