[자료구조] 그래프- 깊이우선탐색(dfs)와 너비우선탐색(bfs) 구현

** '파이썬 알고리즘 인터뷰(박상길 저)' 내용을 참고하여 작성하였습니다.

 

그래프: 객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조

 

오일러 경로: 모든 간선을 한번씩 방문(= 한붓 그리기)

해밀턴 경로: 모든 정점을 한번씩 방분

 

그래프 순회: 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정

그래프 순회에는 깊이우선탐색(Depth-First Search)와 너비우선탐색(Breadth-First Search)가 있다.

일반적으로 DFS가 BFS에 비해 더 널리 쓰인다.

 

<그래프 구현>

DFS - 스택이나 재귀로 구현. 백트래킹을 통해 뛰어난 효용을 보인다.

BFS - 큐로 구현한다. BFS는 재귀로는 구현 불가능.

 

* 백트래킹: 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기해 정답을 찾아가는 범용적인 알고리즘

 

 

☆☆☆<파이썬을 통한 그래프 구현>☆☆☆

 

그래프의 예시 :

위의 그래프를 딕셔너리를 활용한 테이블로 표현하면 다음과 같아진다.

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

 

 

<DFS>

1. 재귀를 통해 구현 ☆☆☆☆☆☆

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]

 

2. 스택을 이용한 반복구조로 구현 ☆☆☆☆

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]

스택을 이용한 반복구조의 탐색순서를 보면 재귀 방법과 조금 다름을 알 수 있다. 재귀와 반대로 뒤에서부터 탐색한다.

 

 

<BFS>

큐를 이용한 반복구조로 구현

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]