[Algorithm] BFS (Breath-First-Search, 너비 우선 탐색)

그래프 순회

• 그래프에서 임의의 한 정점에서 출발하여 모든 정점을 한번씩 방문하는 작업
• 탐색하는 동안 이미 방문한 정점이 있을 수 있으므로 방문했다는 표시를 하여 중복방문을 피한다.
• 대표적으로 DFS, BFS가 있다.

BFS (Breath-First-Search): 너비 우선 탐색

• 출발노드에서 인접한 노드(형제노드)를 먼저 탐색하는 방식
• 가중치가 없는 그래프에서 최단경로를 찾을 때 사용한다.
• 일반적으로 Queue를 이용하여 구현한다.

동작방식

1. 시작정점을 방문하여 큐에 삽입한다.
2. 큐에서 정점을 꺼내 정점에서 인접한 정점중, 방문하지 않은 정점들을 방문하여 큐에 삽입한다.
3. 모든 정점을 반복할 때까지 반복한다.

Visualize

E노드에서 더이상 간선이 없으므로 그냥 큐에서 꺼내는것으로 끝이다

G노드에서 더이상 간선이 없으므로 그냥 큐에서 꺼내는것으로 끝이다. H노드와 I노드도 마찬가지이다.

 

코드

의사코드

BFS(graph, start_node) {
  Queue q;
  boolean[] visit;
  
  q.add(start_node);
  visit[start_node] = true;
  
  while(!q.isEmpty()) {
    current_node = q.pop();
    for(adjacent_node to current_node) {
      if(!visit[adjacent_node]) {
        visit[adjacent_node] = true;
        q.add(adjacent_node);
      }
    }
  }
}

코드 - Queue (Java)

class BFS_Queue {
  private int[][] graph;
  private boolean[] visit;
  
  public BFS_Queue() {
    this.graph = {
      {0, 1, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 1, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 1, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 1},
      {0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 0, 0, 0},
    };
    this.visit = new boolean[graph.length];
  }
  
  public void bfs(startNode) {
    Queue<Integer> queue = new LinkedList();
    
    queue.add(startNode);
    visit[startNode] = true;
    
    while(!queue.isEmpty()) {
      int currentNode = queue.poll();
      
      for(int i = 0; i < graph[currentNode].length; i++) {
        if(isAdjacentNode(currentNode, i) && !visit[i]) {
          visit[i] = true;
          queue.add(i);
        }
      }
    }
  }
  
  public boolean isAdjacentNode(int currentNode, int targetNode) {
    return graph[currentNode][targetNode] == 1;
  }
}

시간 복잡도

• 인접 리스트: \(O(N+E)\) (\(N\): 정점 개수, \(E\): 간선 개수)
• 인접 행렬: \(O(N^2)\)

참고

2021.04.14 - [Algorithm] - [Algorithm] 그래프 (Graph)

[Algorithm] 그래프 (Graph)

2022.01.08 - [Algorithm] - [Algorithm] DFS (Depth-First-Search, 깊이 우선 탐색)

[Algorithm] DFS (Depth-First-Search, 깊이 우선 탐색)