[Swift] Breadth-First Search / BFS

BFS (Breadth-First Search)
인접한 노드를 먼저 탐색하는 방식.
O(Vertex+Edge)

bfs

A→B→C→D→E→F→G→H
해당하는 그래프는 아래와 같이 인접 리스트로 나타낼 수 있다.

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

 

너비 우선 탐색은 보통 두 개의 큐로 구현
방문 해야하는 needVisitQueue
방문 한 노드를 저장하는 visitedQueue

1. 처음으로 탐색할 노드의 데이터를 needVisitQueue에 삽입.

visitedQueue = []
needVisitQueue = ["A"]

2. needVisitQueue의 첫번째 값을 추출해서 visitedQueue에 해당 값이 존재하는지 체크.
 - 만약 존재한다면 추출된 값은 버리고 그 다음 첫번째 값을 추출해서 해당 값이 존재하는지 체크.
위 과정을 visitedQueue에서 존재하지 않는 값이 나올 때까지 반복

3. 추출된 값이 visitedQueue에 존재하지 않으면, visitedQueue에 추가.

visitedQueue = ["A"]
needVisitQueue = []

4. 추출된 값에 연결된 간선들을 모두 needVisitQueue에 추가.

visitedQueue = ["A"]
needVisitQueue = ["B", "C"]

 - B가 추출되었을 때

visitedQueue = ["A", "B"]
needVisitQueue = ["C", "A", "D", "E"]

 

5. needVisitQueue가 모두 비었을 경우, visitedQueue에 채워진 값들이 BFS를 통해 탐색된 노드들의 순서.

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

print(BFS(graph, "A"))
print(BFS(graph, "H"))

print bfs

 

 

 

GitHub - kodecocodes/swift-algorithm-club: Algorithms and data structures in Swift, with explanations!