728x90
728x90
🔎 DFS
DFS(Depth-First Search)는 그래프의 깊은 부분부터 우선적으로 탐색하는 알고리즘
노드와 간선으로 이루어진 그래프 구조에서 시작점을 기준으로 인접 노드의 깊은 부분부터
탐색하는 알고리즘 입니다. DFS는 스택자료구조를 이용하여 인접 노드의 방문여부를 체크하고
모든 노드를 방문한 즉, 노드의 깊은부분에 도달하면 스택에서 상단 노드를 pop 하는 방식으로
목표 노드를 탐색합니다.메모리 효율적인 부분에서 그래프는 인접리스트 방식이 더 우월하지만,
특정한 두 노드의 연결정보를 얻기 위해서는 인접행렬방식이 더욱 유리합니다.
🔍 BFS
BFS(Breadth First Search)는 너비우선탐색으로 가까운 노드부터 탐색하는 알고리즘
너비우선탐색인 BFS는 DFS와 다르게 큐(Queue)자료구조를 이용하여 인접노드부터 탐색하는
방법을 사용합니다. 선입선출방법인 큐의 특성대로 인접한 노드를 반복적을 큐에 넣게되면
자연스럽게 가까운 노드부터 탐색하는 알고리즘이 완성됩니다. DFS와 비슷한점은 인접노드를
탐색할때 방문여부를 체크하며 방문하지 않은 노드를 큐에 삽입하고, 인접노드를 모두 방문하였을 때
맨 앞의 인덱스의 노드를 pop하며 다음 범위로 이동한다는 점입니다.
728x90
728x90
'APS' 카테고리의 다른 글
| [Python] 트리(Tree)구조와 이진 탐색 트리 정리 (0) | 2022.10.04 |
|---|---|
| [Python] Hash Table의 충돌 개선을 위한 SHA-1, SHA-256 (0) | 2022.10.04 |
| [Python] Hash Table에 Linear Probing 기법 적용하기 (0) | 2022.09.27 |
| 이진트리(Binary Tree) - 전위순회, 중위순회, 후위순회 (0) | 2021.04.15 |
| 정렬(Sort) 알고리즘_버블 정렬, 카운팅 정렬 (0) | 2021.02.18 |