DFS, BFS

그래프 순회 이론 정리

 

DFS - 깊이 우선 탐색, Stack과 재귀 호출로 구현되며 Back-Tracking과 같이 사용하면 뛰어난 효과

BFS - 너비 우선 탐색, 주로 Queue로 구현하며 최단 경로 문제에서 많이 사용됨(다익스트라 알고리즘)

 

코딩테스트에서 대부분의 그래프 탐색은 DFS로 이루어짐

 

DFS 

- Stack과 재귀 호출로 구현

 

ex) 

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

 

재귀 호출로 구현 

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 w not in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered


print(f'recursive dfs : {recursive_dfs(1)}')
# recursive dfs : [1, 2, 5, 6, 7, 3, 4]

1번->2번->5번->6번->7번->3번->4번 순으로 방문하게 된다

 

Stack 구현

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

print(f'recursive dfs : {iterative_dfs(1)}')
#recursive dfs : [1, 4, 3, 5, 7, 6, 2]

최초의 정점을 stack에 넣고 while문에서 해당 정점과 연결된 자식 node를 전부 넣는다. 

그리고 다시 stack에서 자식을 하나씩 꺼내서 해당 자식의 node를 방문한다. 

 

stack이기때문에 LIFO정책으로 1 다음에는 4가 온다.

 

백트래킹 

- 탐색을 하다가 더 갈 수 없을때 왔던 길을 되돌아가 다른 길을 찾는 방법

- 주로 재귀로 구현되며, DFS와 같이 많이 쓰임

- 한번 방문 후, 가능성이 없으면 표시를 해두고 다시 가지 않도록 하면 성능이 많이 향상된다

 

BFS

- Queue로 구현, 최단경로를 찾는 다익스트라 문제에서 많이 사용됨

- 옆의 node를 먼저 검색한다.

 

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(f'iterative_bfs  : {iterative_bfs(1)}')
# iterative_bfs  : [1, 2, 3, 4, 5, 6, 7]

 

 

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

#recursive dfs
def recursive_dfs(v, discovered=[]):
    discovered.append(v)

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


#iterative dfs
def iterative_dfs(start_v):
    stack =[start_v]
    discovered = []

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

#iterative_bfs
def iterative_bfs(start_v):
    queue = collections.deque()

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