[알고리즘] 3-3 DFS / BFS

DFS, BFS 모두 탐색을 위한 알고리즘이다. 같은 모양의 그래프라도 DFS와 BFS는 각각 탐색 순서가 다르다. 

 

1. DFS (깊이 우선 탐색)

특정 노드부터 끝까지 내려갔다가 다시 올라와 옆의 노드로 이동해 또 아래까지, 이걸 반복하여 끝까지 탐색한다. stack 또는 재귀함수로 구현

 

# 재귀함수를 이용한 DFS 활용

def dfs_recur(node, dfs_graph, dfs_list=[]):
    if node in dfs_list :
        return dfs_list
    
    dfs_list.append(node)
    if dfs_graph[node] == []:
        return dfs_list
    else :
        for num in dfs_graph[node] :
            dfs_recur(num, dfs_graph, dfs_list)

    return dfs_list
    
dfs_graph = {
    1: [2,3,4],
    2: [5],
    3: [6],
    4: [],
    5: [7],
    6: [5],
    7: [6],
    }

print(dfs_recur(2, dfs_graph, dfs_list=[]))
#[2, 5, 7, 6],

 

 

2. BFS (너비 우선 탐색) 
맨 첫 노드를 보고 그 다음 단계의 노드들을 모두 보고. 그런식으로 마지막 노드층까지 내려가는 것. BFS는 큐나 링크드리스트로 활용.

# 큐를 활용한 BFS 활용 예시

def bfs_queue(start_node, bfs_graph):
    queue = [start_node]
    visited = [start_node]

    while queue : 
        current = queue.pop(0)
        for num in bfs_graph[current] :
            if num not in visited :
                queue.append(num)
                visited.append(num)

    return visited

bfs_graph = {
    1: [5],
    2: [1,4],
    3: [5],
    4: [5],
    5: [3]
	}
    
print(bfs_queue(2, bfs_graph)) 
# [2, 1, 4, 5, 3]