BFS(Breadth-First Search), DFS(Depth-First Search)

1. 그래프 탐색 알고리즘

1) 대표적인 알고리즘

① 너비우선탐색(BFS; Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식

② 깊이우선탐색(DFS; Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식

 

2) 예제

- 그래프가 아래 그림처럼 있을 경우, 그래프를 BFS와 DFS로 탐색하는 순서를 알아보자.

 

① BFS : A → B → C → D → E → F

BFS

 

② DFS : A → B → D → C → E → F

DFS

 

 

2. 그래프 표현

- 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 있다.

- 노드들을 key로 만들어주고, 해당 노드에 간선으로 연결된 인접 정점을 values에 추가한다.

key	values
A	B	C
B	A	D
C	A	E	F
D	B
E	C
F	C

 

graph = dict()

graph['A'] = ['B','C']
graph['B'] = ['A','D']
graph['C'] = ['A','E','F']
graph['D'] = ['B']
graph['E'] = ['C']
graph['F'] = ['C']

 

 

3. BFS 알고리즘 구현

- 자료구조 큐를 활용함

- need_visit 큐 : 방문이 필요한 노드들에 대한 정보 포함

- visited 큐 : 방문한 노드들에 대한 정보 포함

 

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

 

 

4. DFS 알고리즘 구현

- 자료구조 스택과 큐를 활용함 → need_visit 스택, visited 큐

 

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

- need_visit.extend(graph[node])를 쓰게 되면, 순회 방향이 반대로 간다.

- 위에서 말한 순회 방향대로 가려면 reversed를 이용해 역순을 시켜줘야 한다.

 

 

5. 시간 복잡도

- 노드 수 : V, 간선 수 : E

- 시간 복잡도 : O(V+E)

 

---

DFS 순회 결과가 이상해서 구글링을 하다가 더 생각하기에 좋은 블로그를 찾았다. 

BFS, DFS 코드가 같았는데 댓글에 사람들이 고치면 좋은 점을 알려주어서 나도 공부하게 되었다..!

(댓글 中)
python에서 list는 자료구조 상 stack과 유사하게 동작하고, 그 결과 pop(0)는 O(N)의 시간 복잡도가 소요된다.
따라서 변수 queue를 선언할 때, 실제 queue처럼 동작할 수 있는 python의 queue를 사용하는게 효율적이다.

위의 댓글말고도 다른 분께서 친절하게 설명하신 게 댓글에 있으니 아래 블로그를 방문하면 좋을 것 같다.

 

https://itholic.github.io/python-bfs-dfs/

[python] 파이썬으로 bfs, dfs 구현해보기

 

 

출처

[1] 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

[2] https://www.fun-coding.org/Chapter18-bfs-live.html

[3] https://www.fun-coding.org/Chapter18-dfs-live.html

[4] https://itholic.github.io/python-bfs-dfs/