[Python] DFS, BFS

DFS 

Depth-First Search

깊이 우선 탐색

 

스택 사용

 

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=" ")

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

 

BFS

Breadth-First Search

너비 우선 탐색

큐 사용 

 

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=" ")

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True