[알고리즘] BFS(너비 우선 탐색)

🌟 BFS 알고리즘

• 그래프에서 가까운 노드부터 탐색하는 알고리즘
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 구할 때 효율적

➿ BFS 알고리즘의 과정

• 보라색노드는 방문 한 노드
• 파란색노드는 현재 큐에서 꺼내 처리중인 노드

• 0에 방문하여 큐에 집어 넣음

• 큐에서 0을 꺼냄
• 0노드와 근접한 1, 2, 3노드를 차례로 큐에 삽입

• 가장 먼저 큐에 들어온 1을 꺼냄
• 1노드와 근접한 노드 0은 이미 방문 하였기에 큐에 삽입하지 않음

• 큐에 가장 먼저 들어온 2를 꺼냄
• 2노드와 근접한 4노드를 큐에 삽입
• 3노드는 근접하나 이미 방문한 노드이므로 큐에 삽입하지 않음

• 큐에 가장 먼저 들어온 3을 꺼냄
• 3노드와 근접한 0, 2노드는 이미 방문한 노드이므로 큐에 삽입하지 않음

• 큐에 있는 4를 꺼냄
• 4노드와 근접한 2노드는 이미 방문한 노드이므로 큐에 삽입하지 않음

결과적으로 0->1->2->3->4 순으로 탐색하게 된다.

⏳️ BFS 시간 복잡도

노드 수 + 간선 수 만큼의 복잡도를 갖는다.

즉, O(n)

DFS 역시 같은 시간 복잡도를 갖는다.