let graph : [String : [String]] = [
"A" : ["B", "C"],
"B" : ["A", "D", "E"],
"C" : ["A", "F"],
"D" : ["B"],
"E" : ["B"],
"F" : ["C"],
]
깊이 우선 탐색
인접한 노드들을 우선 탐색하는 방식
큐 사용
func BFS(graph: [String: [String]], start : String) -> [String]{
var visited: [String] = []
var needVisit: [String] = [start] // 큐
while !needVisit.isEmpty{
let node : String = needVisit.removeFirst() // 큐의 pop
if visited.contains(node) {continue}
visited.append(node)
needVisit += graph[node] ?? []
}
return visited
}
시간 복잡도 : O(V+E)
깊이 우선 탐색
탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식
func DFS(graph: [String: [String]], start : String) -> [String]{
var visited: [String] = []
var needVisit: [String] = [start] // 스택
while !needVisit.isEmpty{
let node : String = needVisit.removeLast() // 스택의 pop
if visited.contains(node) {continue}
visited.append(node)
needVisit += graph[node] ?? []
}
return visited
}
시간 복잡도 : O(V+E)