[Algorithm] BFS 구현

BFS : Breadth-First Search (너비 우선 탐색) 이란?

- 그래프 전체를 탐색하는 하나의 방법으로써, 현재 정점으로부터 가까운 정점들을 먼저 방문한다.

 

- DFS와 다르게 깊게 파고 드는 것이 아니라, 인접한 정점부터 넓게 탐색한다.

 

-  queue(큐)를 이용해서 구현할 수 있다.

 

- ex) 1을 큐에 넣고 빼면서 1과 인접한 2와 3을 큐에 넣는다. (이런 방식으로 계속 반복)

---

🏷️ 변수 설명

변수와 input은 DFS 설명한것과 다를 바가 없다.

https://jaslime.tistory.com/24

 

🏷️ 코드 예시

[Parameters]

int v, e; // 정점의 개수, 간선의 개수
vector<vector<int>> graph; // 인접 리스트
vector<bool> visited; // 정점 방문 여부 저장

 

[Method]

// BFS 함수
void bfs(int start)
{
    queue<int> q;
    vector<bool> visited(n + 1, false); // BFS 전용 방문 배열

    q.push(start);
    visited[start] = true;

    while (!q.empty())
    {
        int current = q.front();
        q.pop();
        cout << current << " "; // 방문한 노드 출력

        for (int neighbor : graph[current])
        {
            if (!visited[neighbor])
            {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

//방법 2
 while(!q.empty()){
        // 큐에 값이 있을경우 계속 반복 실행
        // 큐에 값이 있다. => 아직 방문하지 않은 노드가 존재 한다. 
        int current = q.front();
        q.pop();
        printf("%d ", current);
        for(int i=0; i< a[current].size(); i++){
            int neighbor = a[current][i];
            if(!visit[neighbor]){
                // 방문하지 않았다면..
                q.push(neighbor);
                visit[neighbor] = true; 
            }
        }
    }