3번째 주제 그래프입니다.
여기서는 간단한 Graph와 BFS DFS에 대해 보도록 하겠습니다.
그래프
노드와 엣지로 이루어짐
그래프를 표현하는 방식에는
인접 행렬 (Adjacent Matrix)와
인접 리스트 (Adjacent Matrix)가 있습니다.
코드 구현
그래프 순회(탐색)
그래프를 순회하면서 모든 노드를 빠짐없이 탐색하는 것.
BFS와 DFS 방식이 있습니다.
DFS를 먼저 살펴보면
DFS는 시작 노드의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색을 해 가다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길이 있는 노드로 돌아와서 다른 방향의 노드로 탐색을 계속 진행하여 모든 노드를 방문하는 순회 방법입니다.
-> 새로 탐색한 것을 먼저 방문하고, 그게 없는 경우 마지막에 만났던 갈림길을 방문하는 자료구조 = 스택(후입선출)으로 구현이 가능합니다.
스택 외에도 재귀를 이용하여 DFS가 구현이 가능합니다.
(Stack과 동일한 원리로 순서대로 쌓아두는 것)
BFS
BFS는 인접한 노드를 모두 차례대로 탐색한 후에 방문했던 노드를 시작으로 다시 인접한 노드를 탐색하는 것.
-> 즉 선입선출의 구조를 가지게 됩니다. => Queue 사용
'알고리즘 > 자료구조' 카테고리의 다른 글
| [알고리즘][자료구조] Tree (트리) (0) | 2021.05.01 |
|---|---|
| [알고리즘][자료구조] Linked List (링크드 리스트) (0) | 2021.05.01 |