[알고리즘] 깊이 우선 탐색 DFS Depth First Search

DFS 깊이 우선 탐색

• 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 Node들의 자식을 타고 내려가며 순회함
• DFS 방식 : A -> B -> D -> E -> F ->C -> G -> H -> I -> J

---

구현 코드

# 그래프 생성하기
graph = dict()

graph['A'] = ["B", "C"]
graph['B'] = ["A", "D"]
graph['C'] = ["A", "G", "H", "I"]
graph['D'] = ["B", "E", "F"]
graph["E"] = ["D"]
graph["F"] = ["D"]
graph["G"] = ["C"]
graph["H"] = ["C"]
graph["I"] = ["C", "J"]
graph["J"] = ["I"]

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    need_visit.append(start_node)
    
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited
bfs(graph, 'A')

['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

시간복잡도

노드수와 간선의 수로 결정됨

• 노드 수: V
• 간선 수: E
• while에서 V+E 만큼 수행됨
• \( O(V+E) \)