[자료구조] DFS와 BFS

 

 

오늘은 트리자료 구조에서 DFS와 BFS에 대해 알아보겠습니다.

출처 - 나무위키(DFS,BFS)

 

 

 

DFS

 

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

# 재귀함수
def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited

# stack
def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

 

dfs는 재귀함수와 stack으로 구현할 수 있습니다.

dfs란 깊이우선탐색으로, 탐색중인 노드의 인접노드를 파악하여, 인접노드를 탐색노드로 바꿔 반복탐색(재귀)하는 특징이 있습니다.

 

다시말해 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다.
이 말만 들어서는 방법이 안 떠오르니까, 한 번 구체적으로 실행 과정을 적어보겠습니다!

1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
3. 위 과정을 반복한다.

 

 

 

 

BFS

 

from collcetions import deque

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

def bfs_queue(start):
    visited = [start]
    q = deque([start])
    
    while q:
    	node = q.popleft()
        for adj in graph(node):
        	if adj not in visited:
            	q.append(adj)
                visited.append(adj)
    
    return visited

 

bfs란 넓이우선탐색으로 탐색노드와 인접해있는 모든 노드를 순차적으로 탐색합니다. dfs와 다른 점은 dfs는 인접노드가 없을 때까지 깊이우선탐색을 진행하지만 bfs는 인접노드를 전체적으로 순회하며 탐색합니다.

정리해보면 아래 순서로 진행됩니다.

1. 루트 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.