[알고리즘] 너비 우선 탐색(Breadth First Search)

설명

• 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 탐색

예제

• graph
  • 
• C++

  • 코드

       #include <iostream>
       #include <queue>
       #include <vector>
            
       using namespace std;
            
       void bfs(vector<int> graph[], bool visited[], const int& startVertex) {
           queue<int> procedure;
           procedure.push(startVertex);
           visited[startVertex] = true;
            
           cout << startVertex << "\n";
            
           while (procedure.empty() == false) {
               const int currentVertex = procedure.front();
               procedure.pop();
            
               for (const auto& iter : graph[currentVertex]) {
                   if (visited[iter] == false) {
                       visited[iter] = true;
                       procedure.push(iter);
            
                       cout << iter << "\n";
                   }
               }
           }
       }
            
       int main() {
           ios::sync_with_stdio(false);
           cin.tie(nullptr);
           cout.tie(nullptr);
            
           const int maxVertex = 10;
            
           vector<int> graph[maxVertex] = {{1, 2}, {3, 4}, {5, 6}};
            
           bool visited[maxVertex] = {
               false,
           };
            
           bfs(graph, visited, 0);
            
           return 0;
       }
    

  • 결과

    0
    1
    2
    3
    4
    5
    6