BFS, DFS

BFS

• 너비우선 탐색
• 너비 우선 탐색(Breadth-first search, BFS)은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
• 정점들과 같은 레벨에 있는 노드들(형제 노드)을 먼저 탐색하는 방식
• 시간복잡도: O(V + E)

구현을 하기 위해서는 두가지 큐가 필요하다

• 방문한 노드를 순서대로 기입한 큐 (A)
• 방문이 필요한 노드들의 정보가 가지고 있는 큐 (B)

첫 노드를 B에 넣고 시작한다.

B에서 꺼낸 노드가 A에 없으면 B에서 꺼낸 후에 방문을 하고 A에 넣는다. 그리고 해당 노드와 연결된 노드를 B에 넣는다.

만약 B에 있는 노드가 이미 방문한 노드이면 아무것도 하지 않고 B에서 꺼낸다.

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']

def bfs(graph, start_node):
    visited = list()  # 방문한 노드
    need_visit = list()  # 방문할 노드

    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


print(bfs(graph, 'A'))

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

DFS

• 깊이 우선 탐색
• 깊이 우선 탐색은 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.
• 정점의 자식들을 먼저 탐색하는 방식

구현을 하기 위해서는 스택 하나와 큐 하나가 필요하다

• 방문한 노드를 순서대로 기입한 큐 (A)
• 방문이 필요한 노드들의 정보가 가지고 있는 스택 (B)

첫 노드를 B에 넣고 시작한다.

B에서 꺼낸 노드가 A에 없으면 B에서 꺼낸 후에 방문을 하고 A에 넣는다. 그리고 해당 노드와 연결된 노드를 B에 넣는다.

만약 B에 있는 노드가 이미 방문한 노드이면 아무것도 하지 않고 B에서 꺼낸다.

 

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']

def dfs(graph, start_node):
    visited = list() #방문한 노드
    need_visit = list() #방문할 노드

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop() #BFS와 다른 점!
        if node not in visited: #방문한 적이 없다면
            visited.append(node) #방문한 노드에 추가
            need_visit.extend(reversed(graph[node])) #꺼낸 노드와 인접한 노드를 넣어줌

    return visited

print(dfs(graph, 'A'))

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