3-2. 그래프에서의 BFS

그래프 순회

 

 

순회(traversal)

• 그래프의 모든 노드들을 방문하는 일
• BFS (Breadth-First Search , 너비우선순회)
• DFS (Depth-First Search, 깊이우선순회)

너비우선순회(BFS)

 

• BFS 알고리즘은 다음 순서로 노드들을 방문
• L0 = {s}, 여기서 s는 출발 노드
• L1 = L0 의 모든 이웃 노드들
• L2 = L1 의 이웃들 중  L0에 속하지 않는 노드들....
• 첫번째로 거리=1인 노드들 / 두번째로 거리=2인 노드들 동심원 형태로 

 

 

 

큐를 이용한 너비우선순회

• 출반 노드를 체크한다. (체크는 이미 방문된 노드라는 표시)
• 출발 노드를 큐에 넣어준다.
• 큐가 empty가 아닌동안 while문을 돌면서 반복한다.
• 큐에서 노드를 꺼내고 그 노드의 인접노드 중 아직 방문하지 않은 노드들은 체크하고 큐에 넣는다.
• 순서는 중요하지 않음
• 이런 방법으로 큐가 비어있는 상태가 될때까지 반복한다.
• 최종적으로 노드를 방문한 순서는 1, 2, 3, 4, 5, 7, 8, 6 이 된다.
• 유일한건 아님 유일큐에 인접노드를 삽입하는 순서에 따라 달라지기 때문이다.

 

 BFS(G, s)
   Q <- null;
   Enqueue(Q, s);
   while Q != null do
     u <- Dequeue(Q);
     for each v adjacent to u do
       if v is unvisited then
         mark v as visited;
         Enqueue(Q, v);

 

BFS와 최단경로

• s에서 Li에 속한 노드까지 최댄 경로의 길이는 i이다.
  • 여기서 경로의 길이는 경로에 속한 엣지의 수를 의미한다.
• BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.
• 입력 : 방향 혹은 무방향 그래프 G = (V, E), 그리고 출발노드 s
• 출력 : 모든 노드 v에 대해서
  • d[v] = s로 부터 v까지의 최단 경로의 길이(엣지의 개수)
  • π[V] = s로 부터 v까지의 최단경로상에서 v의 직전 노드(predecessor)

 BFS(G, s)
   Q <- null;
   for each node u do
     d[u] <- -1;
     π[u] <- null;
   d[s] <- 0;     //distance from s to s is 0
   π[s] <- null;  //no predecessor of s
   Enqueue(Q, s);
   while Q != null do
     u <- Dequeue(Q);
     for each v adjacent to u do
       if (d[v] == -1) then
         d[v] <- d[u] + 1;    //distance to v
         π[v] <- u;           //u is the predecessor of v
         Enqueue(Q, v);

 

시간복잡도

• while문이 알고리즘의 시간복잡도를 결정한다.
• 기본적으로 while문이 한번 돌 때마다 큐에서 노드 하나씩 꺼내므로 while문은 최대 n번 돈다.
• for문은 u의 degree() 만큼 돈다.
• 리스트를 인접 행렬로 구현하느냐, 인접리스트로 구현하느냐에 따라 for문의 시간복잡도가 달라진다.
• 인접행렬로 구현했을 때는  while문의 시간복잡도는 O(n^2)이 된다.
• 인접 리스트로 구현했을 때는 전체 그래프에서 보면, for 문은 결국 모든 노드들의 degree() 만큼 돌 것
• 인접리스트에서 그것은 2m이다. => O(n+m)
• 결과적으로 인접 리스트의 최악의경우 m이 n이 되므로 최악의 경우가 아닌 이상 인접 리스트로 구현하는 것이 좀 더 효율적이다.

 

BFS 트리

• 각 노드 v와 π[v]를 연결하는 엣지들로 구성되는 트리
• BFS 트리에서 s에서 v까지의 경로는 s에서 v까지 가는 최단 경로
• 어떤 엣지도 동심원의 2개의 layer를 건너가지 않는다.

 

• 그래프가 disconnected 이거나 혹은 방향 그래프라면 BFS에 의해서 모든 노드가 방문되지 않을 수도 있음
• BRS를 반복하여 모든 노드 방문