DFS, BFS 구현 (Python)

DFS - Depth first search

deque를 사용하여 구현

from collections import deque

def dfs(graph, start_node):
    visited = []
    need_visited = deque([])

    need_visited.append(start_node)

    while need_visited:
        node = need_visited.pop()

        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])

    return 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']

print(dfs(graph, 'A'))

재귀를 사용하여 구현

def dfs(graph, start_node, visited = []):
    visited.append(start_node)

    for node in graph[start_node]:
        if node not in visited:
            dfs(graph, node, visited)
    return 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']

print(dfs(graph, 'A'))

BFS - Breadth First Search

구현

from collections import deque

def bfs(graph, start_node):
    visited = []
    need_visited = deque([])
    need_visited.append(start_node)

    while need_visited:
        node = need_visited.popleft()
        
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
    
    return 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']

print(bfs(graph, 'A'))

• DFS는 가장 끝의 데이터를 추출
• BFS는 가장 앞의 데이터를 추출