[알고리즘] BFS(Breadth First Search), DFS(Depth-First Search)

대표적인 그래프 탐색 알고리즘

• 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
• 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

사진 출처 : 패스트 캠퍼스 알고리즘 / 기술면접  올인원 패키지

BFS(Breadth First Search)

- 너비 우선 탐색으로써 같은 레벨에 있는 노드들을 왼쪽에서부터 모두 탐색한 후에 다음 레벨로 넘어가는 것이다.

- A - B - C - D - G - H - I - E - F - J 순서이다.

 

코드로 나타내어보자

• 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음

사진 출처 : 패스트 캠퍼스 알고리즘 / 기술면접  올인원 패키지

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

• need_visit 큐와 visited 큐, 두 개의 큐를 생성해서 방문한것과 방문이 필요한 노드들로 나눈다.

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0) //그냥 pop은 맨 뒤의 것이 나오기 때문
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

 

시간복잡도

• 노드 수: V
• 간선 수: E
• 라고 할때 일반적인 시간복잡도는 O(V + E) 이다.

 

DFS(Depth-First Search)

- 깊이 우선 탐색으로써 가장 왼쪽에 있는 노드들 부터 다 방문후에 가장 깊은 노드의 오른쪽 부터 먼저 방문해 가면서 위로 올라가는 것이다.

- A - B - D - E - F - C - G - H - I - J 순서이다.

DFS

• need_visit 스택과 visited 큐, 두 개의 자료 구조를 생성

BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS 는 스택과 큐를 활용한다는 차이가 있음

 

 

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node][::-1])
    
    return visited

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])// 이건 A C I J H G B D E F 순서이다.
    
    return visited

시간복잡도

• 노드 수: V
• 간선 수: E
• 라고 할때 일반적인 시간복잡도는 O(V + E) 이다.