BFS와 DFS

BFS란?

BFS (Breadth-First Search) : 너비 우선 탐색

출처 https://developer-mac.tistory.com/64

 

출발노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이며 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법으로 큐로 구현됨.

다시 말하면 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하여, 먼저 들어온 노드가 먼저 나가게 되어 가까운 노드 부터 탐색하게 됨.

 

- 동작 과정

1) 시작 노드를 큐에 삽입하고 방문 처리

2) 큐에서 노드를 꺼내 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

3) 2번의과정을 더이상 수행할 수 없을 때까지 반복

 

주로 두 노드의 최단 경로를 찾고 싶을 때 사용된다.

 

구현 코드

from collections import deque

graph = [
[]
, [2,3,7]
, [4,6]
, [1,5,7]
, [2,6]
, [3]
, [2,4]
, [1,3]
]

def bfs(graph, start):
    deq = deque([start])
    visited = []
    visited.append(start)

    while deq:
        node = deq.popleft()
        print(node)
        for v in graph[node]:
            if v not in visited:
                deq.append(v)
                visited.append(v)

bfs(graph,1)

** 큐 자료구조에 기초한다는 점에서 간단

** deque 라이브러리를 사용해 간단함.

** 탐색 수행에 O(N) 시간 소요

** 보통 DFS보다 수행시간이 짧음.

 

DFS 란?

출처 https://developer-mac.tistory.com/64

 

DFS (Depth-First Search) : 깊이 우선 탐색

출발 노드에서 다음분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식으로 스택 또는 재귀함수로 구현됨.

 주로

1) 모든 노드를 방문하고자 하는 경우에 이 방법을 선택

2) DFS가 BFS보다 간단함.

3) 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느림

 

구현 코드

#DFS = Depth-First Search

graph = [
[]
, [2,3,7]
, [4,6]
, [1,5,7]
, [2,6]
, [3]
, [2,4]
, [1,3]
]

#재귀함수
def dfs(graph, node, visited):
    if visited[node]==True:
        return
    
    visited[node]=True
    print(node,end='')
    for v in graph[node]:
        dfs(graph, v, visited)

#스택이용
def dfs_stack(grpah, start_node):
    stack = [start_node]
    visited = []
    while stack:
        current_node = stack.pop()
        print(current_node)
        visited.append(current_node)
        for adjacent_node in graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)


if __name__ =='__main__':
    visited =[False for _ in range(8)]
    dfs(graph, 1, visited)
    dfs_stack(graph,1)

 

 

참고 

https://devuna.tistory.com/32

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90