[Algorithm] 그래프 Graph - BFS

BFS (Breadth-First Search, 너비 우선 순회)

• BFS 알고리즘은 다음 순서로 노드를 방문
  • L0 : {s}, 여기서 s는 출발 노드
  • L1 : L0과 연결된 모든 이웃 노드들
  • L2 : L1의 이웃들 중 L0에 속하지 않는 노드들 
  • ...
  • Li : Li-1의 이웃들 중 Li-2에 속하지 않는 노드들

---

큐를 이용한 BFS

• 출발 노드를 check(방문 표시)
• 출발 노드를 큐에 넣음

• 큐가 빌 때까지 while문 반복
  • 맨 앞에 있는 노드를 큐에서 꺼냄
  • 꺼낸 큐의 인접한 노드들 중, 아직 방문되지 않은 노드들을 check한 후 큐에 넣음
  • 큐에 인접 노드를 넣는 순서는 중요하지 않음

• 다시 맨 앞에 있는 노드, 여기서는 노드 2를 꺼낸 후 
• 노드 2의 인접한 노드들 중 방문하지 않은 노드들을 큐에 넣음 (빨간 v가 된 노드들)

• 위와 같이 반복

구현

• 그래프 G와 출발 노드 s

BFS(G, s)
   Q <- null;
   Enqueue(Q, s); //출발노드 s를 큐에 넣음
   while Q != null do //큐가 빌 때 까지 반복문 실행 
     u <- Dequeue(Q); //큐에서 노드를 하나 꺼냄
     for each v adjacent to u do //노드 u에 인접한 노드 v에 대해서 반복문 실행
       if v is unvisited then //노드 v가 방문되지 않은 노드라면
         mark v as visited; //방문 표시
         Enqueue(Q, v);//큐에 인접 노드를 넣음

 

---

BFS와 최단경로

• s에서 Li에 속한 노드까지의 최단 경로의 길이는 i (여기서 경로의 길이는 경로에 속한 에지의 개수)
• 입력 : 방향 또는 무방향 그래프 , 그리고 출발 노드
• 출력 : 모든 노드 v에 대해서,
  • d[v] = s로부터 v까지의 최단 경로의 길이 (에지의 개수)
  • π[V] = s로부터 v까지의 최단 경로상에서 v의 직전 노드 (predecessor)

구현

• 그래프 G와 출발 노드 s

BFS(G, s)
   Q <- null;
   for each node u do
     //초기화
     d[u] <- -1;
     π[u] <- null;
   d[s] <- 0;     //s 자기 자신에게 가는 길이이므로 0
   π[s] <- null;  //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]가 -1이면 방문하지 않은 노드
         d[v] <- d[u] + 1;    //최단경로 길이 d[v]는 u까지의 최단경로길이 d[u]를 지나므로 d[u] + 1
         π[v] <- u;           //v의 직전노드는 인접노드인 u
         Enqueue(Q, v);

 

---

BFS 트리

• 각 노드 v와 π[V]를 연결하는 에지들로 구성된 트리 (빨간 에지들)
• BFS 트리 상에서 s에서 v까지의 경로는 s에서 v까지의 최단 경로
• 모든 에지들이 동일한 노드상에 있거나 하나의 layer만을 건넘 (절대 2개의 layer를 건너뛰지 않음)

구현

• 최단 경로 출력하기
• 그래프가 disconnected 상태이면 s에서 v까지 가는 경로가 없을 수 있음

PRINT-PATH(G, s, v)
   if v = s then //s 자기 자신으로 가는 경로
    print s;
  else if π[v] = null then //실제로 s에서 v까지 가는 경로가 없는 경우(최단경로도 없음)
    print "no path from s to v exists";
  else
    PRINT-PATH(G, s, π[v]); //s에서 v직전 노드까지의 경로를 출력한 후
    print v; //v를 추가로 출력