[Swift] 너비우선탐색(BFS) 구현해보기

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다.

자세한 내용은 https://babbab2.tistory.com/106 이곳에서 확인해주세요!

 

너비우선탐색(BFS)

출처 : https://babbab2.tistory.com/106

Breadth-First Search

인접한 노드를 우선하여 탐색하는 방식입니다.

탐색 노드로부터 인접한 노드를 먼저 탐색하고, 다 탐색하면 인접한 노드의 인접한 노드들부터 탐색합니다.

따라서 같은 레벨에 있는 노드들부터 탐색하는 것처럼 보입니다.

 

참고로 왼쪽부터 탐색할지, 오른쪽부터 탐색할지 같은 순서는 중요하지 않습니다.

 

구현

1. 탐색할 그래프 미리 만들어두기

출처 : https://babbab2.tistory.com/106

let graph: [String: [String]] = [
    "A" : ["B", "C"],
    "B" : ["A", "D", "E"],
    "C" : ["A", "F"],
    "D" : ["B"],
    "E" : ["B"],
    "F" : ["C"],
]

위 그림을 인접 리스트방식으로 그래프를 만들었습니다.

 

2. 너비우선 탐색하기

너비우선탐색은 두개의 큐(Queue)로 구현합니다.

 

needVisitQueue : 방문해야하는 노드를 저장하는 큐

visitedQueue : 이미 방문한 노드를 저장하는 큐

 

그리고 아래와 같은 순서로 탐색을 진행합니다.

 

visitedQueue와 needVisitQueue

 

1. 탐색할 노드의 데이터를 needVisitQueue에 넣는다.
2. needVisitQueue의 첫번째 값을 추출해서(FIFO), visitedQueue에 해당 값이 존재하는지 확인한다.
[visitedQueue에 값이 존재하는 경우] - 추출한 값을 버리고 다시 visitedQueue에 존재하는 지 확인 함
[visitedQueue에 값이 없는 경우] - 3번 과정으로 넘어간다.
3. 추출한 값을 visitedQueue에 추가한다.
4. 추출한 값에 연결된 간선들을 모두 needVisitQueue에 추가한다.
5.
[needVisitQueue가 비어있지 않은 경우] - 2번 과정으로 돌아간다.
[needVisitQueue가 비어있는 경우] - visitedQueue에 채워진 값들이 너비우선탐색을 통해 탐색된 노드 순서라고 결론짓는다.

 

위의 과정들을 코드로 구현하기

func BFS(graph: [String: [String]], start: String) -> [String] {
    var visitedQueue: [String] = []
    var needVisitQueue: [String] = [start]
    
    while !needVisitQueue.isEmpty {
        let node: String = needVisitQueue.removeFirst()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitQueue += graph[node] ?? []
    }
    
    return visitedQueue
}

 

너비우선탐색(BFS)의 시간복잡도

일반적으로 노드 수(V), 간선 수(E)라 했을 때의 시간복잡도는 O(V+E)가 된다.

입력 자체를 노드와 간선으로 받기 때문이다.