dfs1

• 

  210708 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS, Breadth - First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 즉 깊게 보다 넓게를 우선시한 탐색 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 활용함 BFS의 과정 시작 정점 방문 깊이 1인 모든 노드 방문 깊이 2인 모든 노드 방문.... (반복) 더 이상 방문할 곳 없으면 탐색 마침 노드 방문 세부 과정은 (큐에서 꺼낸) 노드를 방문하였을 경우 큐에서 꺼낸 노드 방문 큐에서 꺼낸 노드와 인접한 노드들 모두 방문 방문한 노드들 큐에 삽입, 더 이상 없다면 큐에서 노드 꺼냄 이런 과정을 반복한다 예시 시간복잡도 : 인접 행렬 사용시 : O(노드수 +간선수) 인접 리스트 사용시 : O(노드수^2) 깊이 우선 탐색(DFS, Dep.. 미가공 필기(알고리즘) 2021. 7. 9.