그래프(Graph) BFS의 개념과 구현

Keunjae Song·2020년 9월 1일
자료구조
1

data_structure

목록 보기
8/9
post-custom-banner

이전 글인 그래프(Graph) DFS의 개념과 구현에 이어서 작성하는 글입니다.

이번 글은 BFS(Breadth-First Search, 너비 우선 탐색)에 대해 알아보겠습니다.

BFS - 너비 우선 탐색

개념

너비 우선 탐색은 말 그대로 너비를 우선으로 하여 탐색하는 방법입니다.

아래 그림을 통해 이해하는 것이 쉬울 것 같습니다.

(노드 안에 있는 숫자는 제일 윗쪽 노드부터 너비 우선 탐색을 한다고 가정했을 때의 방문 순서입니다.)

위 이미지로 확인할 수 있듯이, 너비 우선 탐색은 자신과 연결된 노드를 방문하는데 이 때, 깊이 우선 탐색과 달리 무조건 자기 자신과 인접해있던 노드들을 우선적으로 방문합니다.

가장 윗쪽 노드인 1을 방문하고 나서 1과 인접해있던 노드들인 2, 3, 4를 방문하고 그 다음 2와 인접해있던 5를 방문, 3과 인접해있던 6과 7를 방문, 4와 인접해있던 8을 방문합니다.

그리고 마지막으로 7과 인접한 9를 방문합니다.

구현 방법

깊이 우선 탐색은 스택(stack)을 이용하여 구현했다면, 너비 우선 탐색은 큐(queue)를 이용하여 구현합니다.

위와 같은 그래프가 있을 때, 너비 우선 탐색을 구현하는 방법은 아래와 같습니다.

  1. 0부터 너비 우선 탐색을 한다고 했을 때, 먼저 0을 방문하고, 0과 인접한 노드들을 큐에 넣어줍니다.

  2. 그 다음 큐에서 노드를 하나 pop하고 방문한 뒤, 해당 노드와 인접한 노드들을 큐에 넣어줍니다.

    여기서는 1을 pop하고, 2를 새롭게 큐에 넣습니다.

    현재, 0-1까지 방문을 완료한 상태입니다.

  3. 똑같이 큐에서 노드를 하나 pop하고 방문한 뒤, 해당 노드와 인접한 노드들을 큐에 넣어줍니다.

    여기서는 3을 pop하고, 3과 인접한 2와 4를 넣으려 하지만, 2는 이미 큐에 들어갔었으므로 4만 넣어줍니다.

    "한번 스택에 들어갔었던 노드는 다시 스택에 넣지 않는다"가 DFS 구현의 핵심이었듯이, BFS에서는 한번 큐에 들어갔었던 노드는 다시 큐에 넣지 않습니다.

    현재, 0-1-3까지 방문을 완료한 상태입니다.

  4. 3번 과정을 반복합니다.

    여기서는 2를 pop하고, 2와 연결된 1, 3, 4는 이미 큐에 들어갔었던 노드이므로 무시합니다.

    현재, 0-1-3-2까지 방문을 완료한 상태입니다.

  5. 3번 과정을 반복합니다.

    여기서는 4를 pop하고, 4와 연결된 2, 3은 이미 큐에 들어갔었던 노드이므로 무시합니다.

    현재 0-1-3-2-4까지 방문을 완료한 상태입니다.

  6. 3번 과정을 반복하려 하지만 큐가 비어있으므로 탐색을 종료합니다.

이제 이 방법을 그대로 코드로 옮겨보도록 하겠습니다.

구현

전체 코드는 이 곳에서 확인할 수 있습니다.

이전 글인 그래프(Graph) DFS의 개념과 구현을 미리 읽고 오셨다면 바로 BFS 함수 구현 부분으로 가셔도 좋을 것 같습니다.

  • Node 클래스

    class Node
{
public:
  int data_;                    // 노드가 가지고 있는 데이터
  std::list<Node*> adjacent_;   // 인접한 노드 정보를 담고 있는 링크드리스트
  bool marked_;                 // 큐 or 스택에 들어갔었는지 여부
public:
  // 생성자
  // 인자로 온 data로 data_를 초기화하고, marked_는 false로 초기화
  Node(int data) :
  data_(data), marked_(false)
  {
  }
};

  • Tree 클래스

    class Graph
{
public:
  std::vector<Node*> nodes_;  // node들을 담고 있는 vector
public:
  // 생성자
  // 인자로 온 size만큼 nodes_를 resize하고, 0부터 size-1까지의 데이터들을 가지는 노드들을 만듦
  Graph(int size)
  {
    nodes_.resize(size);
    for(int i = 0; i < size; i++)
    {
      nodes_[i] = (new Node(i));
    }
  }
 
  // 간선 생성
  // 인자로 오는 노드의 인덱스 n1, n2에 해당하는 노드끼리 서로 링크드리스트에 추가
  void AddEdge(int n1, int n2)
  {
    nodes_[n1]->adjacent_.push_back(nodes_[n2]);
    nodes_[n2]->adjacent_.push_back(nodes_[n1]);
  }
  
  // 노드 방문
  // 노드의 데이터를 출력
  void visit(Node* node)
  {
    std::cout << node->data_ << " ";
  }
}

  • BFS 함수 - Tree 클래스 멤버 함수

    void bfs(int start)
{
  std::queue<Node*> q;    // 방문할 노드들을 담아놓는 큐
  
  // 맨 처음 방문할 노드와 인접한 노드들을 큐에 넣고, 맨 처음 방문할 노드 방문
  Node* root = nodes_[start];
  root->marked_ = true;
  for(auto n: root->adjacent_)
  {
    q.push(n);
    n->marked_ = true;
  }
  visit(root);

  // 큐가 빌 때(empty)까지 반복
  while(!q.empty())
  {
    // 큐에서 노드를 pop(dequeue)
    Node* node = q.front();
    q.pop();
    // 인접한 노드들이 아직 큐에 들어간 적이 없다면 push
    for(auto n: node->adjacent_)
    {
      if(n->marked_ == false)
      {
        q.push(n);
        n->marked_ = true;
      }
    }
    visit(node); // pop한 노드 방문
  }

  std::cout << std::endl;
}

  • 사용 방법 - main 함수

    위와 같은 형태의 그래프를 만들고 너비 우선 탐색을 진행해보았습니다.

    int main(void)
{
  /*
   *   0
   *  /
   * 1 -- 3    7
   * |  / | \ /
   * | /  |  5
   * 2 -- 4   \
   *           6 - 8
   */
  Graph g(9);
  g.AddEdge(0, 1);
  g.AddEdge(1, 2);
  g.AddEdge(1, 3);
  g.AddEdge(2, 3);
  g.AddEdge(2, 4);
  g.AddEdge(3, 4);
  g.AddEdge(3, 5);
  g.AddEdge(5, 6);
  g.AddEdge(5, 7);
  g.AddEdge(6, 8);

  std::cout << "BFS" << std::endl;
  g.bfs(0);	// 0부터 방문
}

  • 출력 결과

    BFS
0 1 2 3 4 5 6 7 8

    1. 0 → 1을 방문합니다.

    2. 1과 인접한 2와 3을 방문합니다.

    3. 2와 인접한(3과 인접한, 두 가지 다 가능합니다.) 4를 방문합니다.

    4. 3과 인접한 5를 방문합니다.

    5. 5와 인접한 6, 7을 방문합니다.

    6. 마지막으로 6과 인접한 8을 방문합니다.

profile
Keunjae Song
이전 포스트

그래프(Graph)란?

다음 포스트

그래프(Graph) DFS의 개념과 구현

post-custom-banner

0개의 댓글