BFS, DFS

# BFS

BFS(Breath-First Search)는 너비 우선 탐색으로, 가까운 곳부터 탐색하는 방법입니다. bfs는 큐을 사용해서 구현한다는 특징이 있습니다.

 

A를 시작점으로, A가 먼저 큐에 들어가게 됩니다.

큐에 있는 A 노드를 먼저 방문하게 되고, A에 연결된 노드들을 탐색합니다. 연결된 노드가 B밖에 없기 때문에 B를 큐에 삽입합니다.

그 다음, B노드를 방문하게 되고, B에 연결된 노드들을 탐색하는데 연결된 노드가 C,D,E가 있기 때문에 큐에 삽입해줍니다.

 C노드를 방문하게 되고, C에 연결된 노드들을 탐색하는데 연결된 노드가 B,D,E,F가 있는데 B는 이미 방문한 노드이고, D,E는 큐에 삽입되어 있기 때문에 F만 큐에 삽입해줍니다.

 D노드를 방문하게 되고, D에 연결된 노드들을 탐색하는데 연결된 노드가 B,C,E,G,H가 있는데 B,C는 이미 방문한 노드이고, E는 큐에 삽입되어 있기 때문에 G,H만 삽입해줍니다.

 E노드를 방문하게 되고, E에 연결된 노드들을 탐색하는데 연결된 노드 B,D는 이미 방문한 노드이기 때문에 큐에 삽입하지 않습니다.

같은 방법으로 마지막 노드까지 방문하게 되면 탐색이 끝나게 됩니다.

# BFS 코드 구현 (python)

from collections import deque, defaultdict

def BFS(graph, start):
    result = []
    visited = set()
    queue = deque()
    queue.append(start)
    while queue:
        next_ = queue.popleft()
        result.append(next_) 
        for n in graph[next_]:
            if n not in visited:
                queue.append(next_)
                visited.add(next_)
    return result

result = []                       방문한 노드들을 담는 리스트를 생성해줍니다
visited = set()                방문했던 노드를 재방문하지 않기 위해 set을 사용하여 무한 루프를 방지합니다.
queue = deque()            collections 모듈에 deque를 사용하여 queue의 동작을 구현합니다.
queue.append(start)     BFS함수 실행시 입력했던 첫 노드를  큐에 삽입하면서 시작합니다.
while queue:
    next_ = queue.popleft()       큐는 선입선출의 구조이므로 popleft를 사용해 먼저들어온 데이터를 방문합니다
    result.append(next_)           방문한 노드를 result에 넣어줍니다
    for n in graph[next_]:      
        if n not in visited:                 방문한 노드에 연결된 노드들의 방문 여부를 확인하고
            queue.append(next_)           큐에 연결된 노드들를 삽입합니다
            visited.add(next_)                 방문 여부 체크를 위해서 만들어둔 set에도 넣어줍니다
return result                  모든 노드를 방문하고 큐가 비게되면 결과를 반환합니다

 

 

# DFS

DBS(Depth-First Search)는 깊이 우선 탐색으로, 갈 수 있는 한 최대한 멀리가서 탐색하는 방법입니다. 우리가 배웠던 것중에 preorder, inorder, postorder이 해당합니다. dfs는 스택을 사용해서 구현한다는 특징이 있습니다.

A를 시작점으로, A가 먼저 스택에 들어가게 됩니다.

스택에 있는 A 노드를 먼저 방문하게 되고, A에 연결된 노드들을 탐색합니다. 연결된 노드 B를 스택에 삽입합니다.

B노드를 방문하게 되고, B에 연결된 노드들을 탐색합니다. 연결된 노드 C,D,E를 스택에 삽입합니다.

스택에 가장 위에 있는 E노드를 방문하게 되고, E에 연결된 노드들을 탐색하는데 D노드는 이미 스택에 있기 때문에 추가 동작을 하지 않습니다.

그 다음 D노드를 방문하게 되고, D에 연결된 노드들을 탐색합니다.  스택에 있는 C노드 외에 G, H노드를 스택에 삽입합니다.

그 다음 H노드를 방문하게 되고, 연결된 노드가 없기 때문에 추가 동작을 하지 않습니다

그 다음 G노드를 방문하게 되고, 연결된 노드가 없기 때문에 추가 동작을 하지 않습니다

그 다음 C노드를 방문하고 연결된 노드 F를 스택에 쌓아주고, 마지막으로 F노드를 방문하면서 탐색이 종료됩니다.

# DFS 코드 구현 (python)

def DFS(graph, start):
    result = []
    visited = set()
    stack = []
    stack.append(start)
    while stack:
        next_ = stack.pop()
        result.append(next_)
        for n in graph[next_]:
            if n not in visited:
                visited.add(n)
                stack.append(n)
    return result

DFS 구현 코드는 BFS와 거의 흡사하나, 스택 자료구조는 선입후출의 구조이므로 리스트와 동일하게 동작합니다. 그래서 pop을 사용해 마지막에 들어온 데이터를 먼저 꺼내주면서 동작합니다.

 

 

# 전체 코드

테스트 코드를 포함한 전체코드는 깃허브를 참고해주세요!

GitHub - sonzwon/TIL: Today I Learned