알고리즘 - DFS(깊이 우선 탐색) / BFS(너비 우선 탐색) Python 코드

그래프 탐색 기법

그래프 : 정점(node)와 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조이고,

그래프를 탐색하는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. 

 

DFS(Depth First Search) : 깊이 우선 탐색

BFS(Breadth First Search) : 너비 우선 탐색

 

 

 

DFS(Depth First Search)

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

 

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서는 느림

 

적용 : 미로, 길 찾기, 경로의 특징을 저장해야 하는 경우

 

 

 

BFS(Breadth First Search)

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

1. 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택

 

적용 : 길찾기, 라우팅, 웹 크롤러, 소셜 네트워크에서 멀리 떨어진 사람 찾기, 그래프에서 주변 위치 찾기

 

 

 

DFS와 BFS의 차이

DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐 이용해서 구현
메모리가 적음	노드가 많을 수록 메모리를 많이 소비
그래프의 깊이(depth)가 깊을 수록 빠름	찾는 노드가 인접할 때 유리

 

 

 

그래프 탐색 예시

출처 : https://hudi.blog/dfs-bfs/

DFS(깊이 우선 탐색)

위 그래프를 DFS 로 탐색하면 1 → 2 → 5 → 8 → 6 → 3 → 4 → 7 의 순으로 탐색을 한다. 

 

 

BFS(너비 우선 탐색)

위 그래프를 BFS 로 탐색하면 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 의 순으로 탐색을 한다. 

 

 

 

Python 으로 나타낸 BFS

#BFS - Breadth First Search
#너비 우선 탐색 : 가까운 노드부터 탐색
#큐 자료구조 사용

from collections import deque


def BFS(graph, start, visited) :
    queue = deque([start])
    
    #현재 노드 방문 처리
    visited[start] = True
    
    #큐가 빌 때까지 반복
    while queue :
        #큐에서 하나의 원소를 뽑아 print
        v = queue.popleft()
        print(v, end = ' ')
        
        #아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v] :
            if not visited[i] :
                queue.append(i)
                visited[i] = True
                
visited = [False] * 9

 

 

 

Python 으로 나타낸 DFS

#DFS - Depth First Search
#깊이 우선 탐색 - 깊은 부분을 우선적으로 탐색
#스택 자료구조 사용

from operator import truediv
visited = [False] * 9

def DFS(graph, v, visited, parent_node=-1) :
    #현재 노드를 방문 처리

    visited[v] = True # assign current node as
    print(v, end = ' ')
    
    for i in graph[v] :
        if not visited[i] :   # if `i' is not visited
            if DFS(graph, i, visited, v) :
                return True
        elif i != parent_node :    # if `i` is visited, and `i` is not a parent_node
            return True
            
    return False