[그래프]BFS-기본

BFS(Breadth First Search)는, Edge들을 따라 순회하는 순서가, 바로 밑 자손들을 전부 훑고 난 후, 그 다음 자손들을 훑는 순으로, Graph의 Edge를 따라 순회하는 알고리즘을 말한다.

여기서 유의할 것은, (DFS도 마찬가지지만) BFS라는 것이 'Search'라는 단어가 있어서 목표로하는 버텍스나 엣지를 찾는 알고리즘 처럼 보이지만, BFS는 엣지로 연결된 버텍스들을 골고루 찾아다니게끔 하는 알고리즘이라는 것이다. 다시 말해 BFS는 엣지를 따라서 바로 밑 자손들을 전부 방문하고, 그 다음 자손들을 방문하면서, 모든 엣지들을 돌아다니게끔하는 알고리즘이고, 이러한 특성으로 해서 어떤 버텍스에서 다른 버텍스까지의 최소경로 등을 구할 수 있는 것이다.

BFS 알고리즘의 핵심은, 출발하는 버텍스를 기준으로, 연결된 모든 버텍스를 큐(Queue)에 넣고, 큐에 있는 것을 하나씩 뽑아가면서 다시 그 뽑아진 버텍스와 연결된 모든 버텍스를 큐에 넣어나가는 과정을, 큐가 빌때까지 진행하는 것.

이게 핵심인데, 이 과정에서 1)방문한 버텍스의 상태 3가지(방문전, 방문해서 자손들을 훓는 중, 자손들을 전부 훑었음)를  구분하는 것과, 2)출발점에서 해당 버텍스까지의 도달거리 3)각 버텍스들에 대해 선조 버텍스를 표시하는 정보들이 유용하게 쓰일 수 있고, 구현상에서 이 3가지중 2번과 3번은 필요하지 않으면 도출하지 않아도 된다.

BFS를 슈도코드로 나타내면 다음과 같다.

G=(V,E) : Vertex 집합 V와, Edge 집합 E로 구성된 그래프 G

color[u] : color of Vertex u. {WHITE,GRAY,BLACK}

           WHITE : 초기 상태

           GRAY : 인접 버텍스에 대해 작업 중

           BLACK : 작업 완료

pre[u] : predecessor of Vertex u

d[u] : distance to u from s(root source)

Ajd[u] : u에 인접한 Vertex들

Q : Queue (first-in, first-out)

BFS(G,s)

//초기값 설정

for each vertex u in V[G] - {s}

color[u] = WHITE

d[u] = INFINITE

pre[u] = NIL

//해당 버텍스 s에 대해 값 설정

color[s] = GRAY  //방문했으면 GRAY --> 자손들을 모두 훑었으면 BLACK으로 바뀜

d[s] = 0

pre[s] = NIL

Q = NULL

      ENQUE(Q,s)

      while Q != NULL

      u = DEQUE(Q)

      for each v in Adj[u]  //모든 자손들에 대해

      if color[v] == WHITE  //자손들 중 방문하지 않은 버텍스에 대해서만

      d[v] = d[u] + 1

      pre[v] = u

            ENQUE(Q,v)

color[u] = BLACK     //자손들을 전부 방문했으면 BLACK으로 처리

      

위 슈도코드를 C++로 구현해보면 다음과 같다.

#include <stdio.h>

#include <iostream>

#include <vector>

#include <list>

#include <queue>

#include <limits> //INT_MAX

 

using namespace std;

 

class Graph {

         const int WHITE = 0;

         const int GRAY = 1;

         const int BLACK = 2;

 

         int V;

//BFS에서는 일반적으로 연결된 버텍스만 리스트형태로 관리하는게 편리

         vector<list<int>> adj;       

         vector<int> color;

         vector<int> d;

         vector<int> pre; 

 

public:

         Graph(int V);

         void addEdge(int v, int w);

         void BFS(int s);

         void print_path(int s, int v);

};

 

Graph::Graph(int V) {

         this->V = V;

         adj = vector<list<int>>(V);

}

 

void Graph::BFS(int s) {

         //vector<int> color = vector<int>(V,0);

         color = vector<int> (V, 0);  //방문여부

         d = vector<int>(V, INT_MAX); //s부터 해당 버텍스까지의 거리

         pre = vector<int>(V, -1); //해당 버텍스의 선조 버텍스 번호

         queue<int> q;

        

         color[s] = GRAY;

         d[s] = 0;

         pre[s] = -1;     

         q.push(s);

 

         list<int>::iterator it;

         while (!q.empty()) {    

                  //큐에서 값을 뽑아낼 때 front() 후 pop() 함에 유의

                  int u = q.front();

                  q.pop();

                  //리스트에 있는 값들을 뽑아낼 때는 iterator를 사용함에 유의

                  for (it = adj[u].begin(); it != adj[u].end(); ++it) {

                           int v = *it;

                           if (color[v] == WHITE) {

                                   color[v] = GRAY;

                                   d[v] = d[u] + 1;

                                   pre[v] = u;

                                   q.push(v);

                           }

                  }                

                  color[u] = BLACK;

                  //printf("%c ", ('r' + u));

         }

}

 

void Graph::addEdge(int v, int w) {

         adj[v].push_back(w);

}

 

int main(void) {

         freopen("graph_basic.txt", "r", stdin);

         setbuf(stdout, NULL);

 

         int C, N;

         int cnt;

         scanf("%d", &C);

         for (int testNum = 1; testNum <= C; ++testNum) {

                  scanf("%d", &N);

                  //Graph g(N);

                  Graph g = Graph(N);

 

                  scanf("%d", &cnt);

                  char c1, c2;

                  int i1, i2;

                  for (int i = 0; i<cnt; ++i) {

                           //scanf를 이용해서 문자를 읽을 때는, 개행문자 CR을 처리하기 위해 getchar()을 한번 해줘야 함에 유의

                           getchar(); 

                           scanf("%c %c", &c1, &c2);

                           i1 = c1 - 'r';  //주어진 문제가 'r'부터 시작되는 알파벳이기에 'r'을 빼준 것임 

                           i2 = c2 - 'r';

                           g.addEdge(i1, i2);

                  }

 

                  g.BFS(1); //1부터 시작하는 BFS

         }

 

}

샘플 입력 파일 (graph_basic.txt)

1

8

20

v r

r v

r s

s r

s w

w s

w t

w x

t w

t x

t u

x w

x t

x y

x u

u t

u x

u y

y u

y x

BFS의 running time

BFS는 연결된 모든 버텍스를 한 번씩 방문하게 된다. 따라서, 런닝타임은 O(V+E)

 

Print Shortest Path

버틱스 s에서 어떤 버틱스 v까지의 최단경로는 BFS에 의해 구할 수 있다. 왜냐하면 BFS알고리즘을 수행하면서 각 버틱스에 대한 '선조'를 저장하게 되어 있는데, v에서부터 시작해서 s까지의 선조를 연결하면, s에서 부터 v까지의 최단거리가되기 때문이다.(물론 최단거리가 되는 path는 여러개가 있을 수 있다.)

위와같은 원리를 이용해서 s에서 v까지의 최단거리를 프린트하는 프로그램을 작성하면 다음과 같다.

슈도코드

PRINT_PATH(G,s,v)

if v == s

print s

else if pre[v] == NIL

print "no path form s to v exists"

else 

PRINT_PATH(G,s,pre[v])

print v

C++ 작성된 코드

void Graph::print_path(int s, int v) {

         if (s == v) {

                  printf("%c ", s + 'r');

         }

         else if (pre[v] == -1) {

                  printf("no path exist\n");

         }

         else {

                  print_path(s, pre[v]);

                  printf("%c ", v + 'r');

         }

}

main함수에서 BFS를 동작시키고 난 후, print_path(1,7)을 하면 "s w x y"가 출력될 것이다.

  g.BFS(1);

  g.print_path(1, 7);

-끝-