그래프 탐색 기본 (DFS / BFS)

그래프 탐색

참고 영상

https://www.youtube.com/watch?v=gl5RhtU2mF8 

https://www.youtube.com/watch?v=pcKY4hjDrxk  

 

 

 

 

DFS와 BFS

DFS(Depth First Search)는 깊이 우선 탐색, BFS(Breadth First Search)는 너비 우선 탐색이다.
그림으로 알아보면

 

그래프 예시

DFS는 탐색한 곳의 연결된 곳을 계속 찾아들어간다. 즉 1 -> 2 에서 3이 아닌 2와 연결된 4, 5로 탐색한다.
결국 탐색 방향은 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 이다.

이를 잘 생각해보면 마치 stack 개념과 비슷하다.

1과 연결된 2, 3을 stack에 추가하고, 맨 끝인 3을 pop하여 또 3의 연결부를 추가하고.. 이런 개념이다.
그래서 DFS는 stack과 재귀를 이용해 만들 수 있다. (stack과 재귀는 쌍둥이다..!!)

 

##  Stack
def dfs(graph, start):
    need_visited, visited = [], []
    need_visited.append(start)

    while need_visited:
        now = need_visited.pop()
        if now not in visited:
            visited.append(now)
            need_visited.extend(graph[now])

    return visited
    
    ## Recursion
    def dfs_recursive(graph, start, visited = []):
    visited.append(start)

    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    return visited

(https://data-marketing-bk.tistory.com/44 참고)

 

BFS는 처음 탐색한 곳을 모두 탐색한 후, 탐색한 곳에서 연결된 곳을 탐색한다. 즉 1 -> 2 와 3을 탐색한 후, 탐색한 2와 연결된 4, 5를 탐색한다. 결국 탐색 방향은 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 이다.

마찬가지로 이는 Queue 개념과 유사하다. 탐색한 2, 3을 Queue에 저장한 후, 2, 3 부터 확인하고, 2, 3 뒤에 추가로 탐색한 노드를 붙여준다!! 아래는 Queue로 구현한 BFS이다.

def bfs(graph, start):
    visited = []
    need_visited = deque()
    
    need_visited.append(start)
    
    while need_visited:
        node = need_visited.popleft()
 
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
                
    return visited