[python] 파이썬으로 보는 BFS 와 DFS

파이썬으로 알아 보는 BFS와 DFS

1. DFS, BFS 개념

가장 먼저 DFS(깊이 우선 탐색) 과 BFS(너비 우선 탐색) 의 개념에 대해서 알아보자.

먼저 그래프 그림을 보도록 하자.

기본적으로 Tree 형태의 그래프에서 사용하는 개념이다.

왼쪽의 BFS(너비 우선 탐색)은 깊이를 하나씩 내려가면서 그 레벨에 있는 노드를 전부 탐색하고 다음 레벨로 내려가면서 탐색하는 방법이고,

오른쪽의 DFS(깊이 우선 탐색)은 가장 위에 있는 부모 노드의 각 자식 노드의 모든 자식 노드들을 순서대로 탐색하는 방법이다.

 

2. DFS, BFS 구현

위의 그래프를 먼저 코드로 나타내보자

이어진 노드를 전부 표시한다.

graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A'],
    'C': ['A', 'E', 'F'],
    'D': ['A'],
    'E': ['C'],
    'F': ['C']
}

 

DFS부터 구현해보도록 하자.

def dfs(graph, start_node):

    stack = list()
    visit = list()
    
    stack.append(start_node)
    
    while stack:
    	node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(reversed(graph[node]))
            
    return visit

DFS는 스택을 이용하면 된다.

visit -> 방문했던 노드를 저장하는 리스트

stack -> 다음으로 방문할 노드의 리스트

시작 노드를 스택에 넣어주고 while 문에서는 더 이상 방문할 노드가 없을 때까지 loop 를 돌게 한다.

그리고 스택의 맨끝에 있는 노드를 꺼내와서 해당 노드가 visit 리스트에 없다면 리스트에 추가하도록 한다.

 

다음은 BFS를 구현해보도록 하자.

def bfs(graph, start_node):

    queue = list()
    visit = list()
    
    queue.append(start_node)
    
    while queue:
    	node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
            
    return visit

BFS는 큐를 이용한다.

visit -> 방문했던 노드를 저장하는 리스트

queue -> 다음으로 방문할 노드의 목록

시작 노드를 큐에 넣어주고 while 문에서는 더 이상 방문할 노드가 없을 때까지 loop 를 돌게 한다.

그리고 큐의 맨앞에 있는 노드를 꺼내와서 해당 노드가 visit 리스트에 없다면 리스트에 추가하도록 한다.

 

여기서 한가지 의문이 들 수 있다. 왜 BFS는 큐를 사용하고 DFS는 스택을 사용하는 것일까??

두개의 그림으로 알아보자

먼저 DFS

DFS

위에 써있는 알파벳은 pop 되어서 visit 리스트에 들어간 노드이다. 먼저 나중에 스택에 들어간 노드들이 먼저 pop 되기 때문에 점점 더 깊이 탐색하게 된다.

그리고 BFS를 보자

BFS

큐를 사용해서 먼저 들어간 노드들이 먼저 pop 된다. 그렇기 때문에 같은 레벨이 있는 것부터 처리를 하게되는 것이다.

---

분명 저의 코드도 시간 또는 공간 복잡도 면에서 완벽하지 않을 것입니다.

개선할 부분이나 잘못 구현된 부분이 있으면 댓글을 남겨주시면 감사합니다.

이제 다음 글부터 BFS 또는 DFS 에 대한 문제를 풀어보겠습니다.

 

Written by Sheart