BFS (Breadth-First Search)

---

Keywords

queue, O(V+E), vector

---

Variables

1. int v (vertext), int e (edge)
2. vector <int_> graph

• In C++, vectors are used to store elements of similar data types. However, unlike arrays, the size of a vector can grow dynamically. That is, we can change the size of the vector during the execution of a program as per our requirements. Vectors are part of the C++ Standard Template Library.

3. array isVisited[]
4. queue q

Stages

1. Select the start node for the BFS().
2. Call the BFS(Recursion Function) until the every node is visited.
3. Push the start node into the queue, and change its isVisited state.
4. Configure the BFS as a while process. *(!q.empty())
5. Pop the value in front of the queue.
6. Push the adjacent nodes of the current node into the queue if they are not being visited.
   

Code

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

bool isVisited[9];
vector<int> graph[9];

int bfs(int start) {
  queue<int> q;
  q.push(start);
  isVisited[start] = true;

  while (!q.empty()) {
    int a = q.front();
    q.pop();
    cout << a << ' ';

    for (int i = 0; i < graph[a].size(); i++) {
      int b = graph[a][i];

      if (!isVisited[b]) {
        q.push(b);
        isVisited[b] = true;
      }
    }
  }
}

int main() {
  // Connect 1 and 2
  graph[1].push_back(2);
  graph[2].push_back(1);

  // Connect 1 and 3
  graph[1].push_back(3);
  graph[3].push_back(1);

  // Connect 2 and 4
  graph[2].push_back(4);
  graph[4].push_back(2);

  // Connect 2 and 5
  graph[2].push_back(5);
  graph[5].push_back(2);

  // Connect 4 and 8
  graph[4].push_back(8);
  graph[8].push_back(4);

  // Connect 5 and 9
  graph[5].push_back(9);
  graph[9].push_back(5);

  // Connect 3 and 6
  graph[3].push_back(6);
  graph[6].push_back(3);

  // Connect 3 and 7
  graph[3].push_back(7);
  graph[7].push_back(3);

  bfs(1);
  return 0;
}

References
:https://hongku.tistory.com/156
:https://m42-orion.tistory.com/64
:Elmo image