BFS 와 DFS란?

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

너비우선탐색: 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
깊이 우선 탐색: 정점의 자식들을 먼저 탐색하는 방식

BFS DFS 예시

BFS: 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다.

DFS:한 노드의 자식을 타고 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회함

파이썬으로 그래프 표현

파이썬으로 DFS 구현하기

dfs 구현에는 스택을 활용한다.

def dfs(graph, start_node):
    visited, need_visit = [], []
    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])
    return visited

print(dfs(graph,'A'))

파이썬으로 BFS 구현하기

큐를 이용해서 구현한다.

def bfs(graph, start_node):
    visited, need_visit = [], []
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited