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

BFS - Breadth First Search

깊이 우선 탐색

인접한 노드들을 우선 탐색하는 방식

큐 사용

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)

DFS - Depth First Search

깊이 우선 탐색

탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식

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)

Backtracking