BFS

너비 우선 탐색 , 시간 복잡도 O(노드수 + 엣지수)

구현 코드

need_visit 큐(방문할)와 visited 큐(방문한)를 생성한다.

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:
    	// pop(0): list의 첫번째 요소 pop 
        node = need_visit.pop(0)
        // 방문 안했다면, 노드(key)의 value 값을 need_visit 큐에 넣어준다
        if node not in visited:
            visited.append(node)
            // extend: list 요소들을 기존 list에 추가한다. 
            // ex) ['A','B'].extend(['C','D']) => ['A','B','C', 'D']
            need_visit.extend(graph[node])
    
    return visited
    
bfs(graph, 'A') // ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

DFS

깊이 우선 탐색 , 시간 복잡도 O(노드수 + 엣지수)

구현 코드

need_visit 스택(방문할)과 visited큐(방문한)를 생성한다.

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 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(graph, 'A') // ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']