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

설명

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

예제

• graph
  • 
• C++

  • 코드

    #include #include #include 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