[알고리즘] 그래프 탐색 01_DFS(깊이 우선 탐색)/BFS(너비 우선 탐색)

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

• 루트 노드(최상위)부터 리프 노드(최하위)까지 탐색한 후, 다시 올라와서 내려가는 방식(깊은 부분을 우선으로 탐색)
• 재귀(Recursion) 함수를 활용할 수 있음
• 스택(Stack)을 활용할 수 있음

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 함

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문

3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복

 

 

1) 재귀 구조로 구현

# DFS_재귀
def dfs_recursive(graph, start, visited=[]):
    visited.append(start) # 방문한 노드 추가

    for node in graph[start]:
        if node not in visited: # 끝까지 갔을 때(깊이)
            dfs_recursive(graph, node, visited) # 깊이 탐색

    return visited

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

print(dfs_recursive(graph,1))

>> [1, 2, 5, 6, 7, 3, 4]

 

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

 

# 역순으로 방문
def dfs_iteration(graph, root):
    # visited = 방문한 꼭지점들을 기록한 리스트
    visited = []
    # dfs는 stack, bfs는 queue개념을 이용한다.
    stack = [root]

    while (stack):  # 스택에 남은것이 없을 때까지 반복
        node = stack.pop()  # node : 현재 방문하고 있는 꼭지점

        # 현재 node가 방문한 적 없다 -> visited에 추가한다.
        # 그리고 해당 node의 자식 node들을 stack에 추가한다.
        if (node not in visited):
            visited.append(node)
            stack.extend(graph[node])
    return visited

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

print(dfs_iteration(graph,1))

>>[1, 4, 3, 5, 7, 6, 2]

 

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

• 루트 노드(최상위)부터 한 단계씩 내려가면서 탐색하는 방식
• 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐(Queue)을 활용할 수 있음
• 재귀(Recursion) 함수를 활용할 수 없음

동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문처리 함

2. 큐에서 노드를 꺼낸 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고, 방문처리 함

3. 더 이상 2번의 과정을 수행할 수 없을때 까지 반복!!

# 너비 우선 탐색, deque
# BFS는 재귀로 돌아가지 않음(큐를 이용하여 반복 구현만 가능)
from collections import deque

def bfs_iteration(graph, root):
    visited = []  # 방문한 노드
    queue = deque([root])  # bfs는 queue 사용

    while (queue):  # queue에 남은 것이 없을 때까지
        node = queue.pop()  # 현재 방문하는 노드
        
        # node를 방문한 적 없다 -> visited에 추가
        # 해당 노드의 자식 노드들을 queue에 추가
        if node not in visited:
            visited.append(node)
            queue.extendleft(graph[node])
            
    return visited

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

print(bfs_iteration(graph,1))

>> [1, 2, 3, 4, 5, 6, 7]