[코딩 + 알고리즘 완주반] 20일차. 너비 우선 탐색(Breadth-First Search ), 깊이 우선 탐색(Depth-First Search)

# 너비 우선 탐색 (BFS)

정점들과 같은 레벨에 있는 노드들을 먼저 탐색

 

# 깊이 우선 탐색 (DFS)

정점의 자식들을 먼저 탐색하는 방식

 

# BFS 알고리즘 구현

자료구조 큐 활용

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]) # 현재 정점과 연결되어 있는 노드들 need_visit에 추가
    
    return visited

# BFS 시간복잡도 

노드 수 : V

간선 수 : E

시간 복잡도  : O(V+E)

 

# DFS 알고리즘 구현

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

# DFS 시간복잡도 

노드 수 : V

간선 수 : E

시간 복잡도  : O(V+E)