[자료구조] 그래프 탐색 알고리즘: DFS/BFS

 

1. 탐색

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 일컫음

• 대표적인 그래프 탐색 알고리즘 : DFS , BFS

2. DFS(Depth-First Search)

• 깊이 우선 탐색

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘을 의미함

• 스택 자료구조 or 재귀함수 활용

• 꼭 이진트리일 필요가 없음!

1. 탐색 시작 노드를 스택에 삽입 후, 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

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

def dfs(graph, v, visited):     visited[v] =True     print(v, end=' ')     for i in graph[v]: #2,3,8 (그래프 안의 값들 (인접한 노드들을 의미))         if not visited[i]:             dfs(graph,i,visited)

graph=[     [],     [2,3,8], #1번노드와 인접한 노드들     [1,7], #2번 노드와 연결된 노드     [1,4,5],     [3,5],     [3,4],     [7],     [2,6,8],     [1,7] ]  visited= [False]*9  dfs(graph,1,visited)

3. BFS(Breath-First Search)

• 너비 우선 탐색

• 가까운 노드부터 우선적으로 탐색하는 알고리즘

• 큐 자료구조를 활용

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

2. 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후, 방문 처리

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