16. 그래프 순회- BFS, DFS

 그래프의 각 정점을 방문하는 그래프 순회에는 크게 깊이 우선 탐색(Depth-Frist-Search(이하 DFS))과 너비 우선 탐색(Breadth-First_search(이하 BFS))의 2가지 알고리즘이 있다. 

 

 DFS는 주로 스택으로 구현하거나 재귀로 구현하며, 이후에 살펴볼 백트래킹을 통해 뛰어난 효용을 보인다. 반면 BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다.

 

 아래 그림과 같은 순회 그래프를 살펴보자.

 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트의 2가지 방법이 있는데, 이번 포스팅에서는 위 그래프를 인접 리스트로 표현하겠다.

 

 

1. DFS

graph={
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3]
}

def recursive_dfs(v,discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if not w in discovered:
            discovered=recursive_dfs(w,discovered)

    return discovered

print(recursive_dfs(1))
#[1, 2, 5, 6, 7, 3, 4]

def iterative_dfs(start_v):
    discovered=[]
    stack=[start_v]
    while stack:
        v=stack.pop()

        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    
    return discovered

print(iterative_dfs(1))
#[1, 4, 3, 5, 7, 6, 2]

 

2. BFS

graph={
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3]
}

def iterative_bfs(start_v):
    discovered=[start_v]
    queue=[start_v]
    while queue:
        v=queue.pop(0)
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    
    return discovered

print(iterative_bfs(1))
#[1, 2, 3, 4, 5, 6, 7]