0.그래프 (Graph)
✔️그래프란?
그래프란, 점과 선으로 이루어진 자료 구조를 뜻하는데
아래 그림과 같이 정점(node)와 그 정점을 연결하는 간선(edge)로 이루어진 자료구조의 일종이며,
그래프 탐색이란 처음 node에서 차례대로 모든 node를 방문하는 것을 뜻함
1.깊이 우선 탐색 (DFS, Depth-First Search)
✔️깊이 우선 탐색(DFS)란?
최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없으면 옆으로 이동하는 방법이자 해당 분기를 완벽하게 탐색하는 방식
즉, 갈림길이 나타날 때마다, '다른길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워나가고, 막다른 곳에 도달하면 직전 갈림길로 돌아가 '이 길은 아니다'라는 표식을 남긴다. 결국 목적지를 발견하면 종료
✔️사용 이유
-검색 보다는 모든 노드를 방문하고자 하는 순회 경우에 많이 쓰인다
-BFS보다 간단함 (단, 속도는 BFS에 비해 느림)
-저장 공간의 수요가 비교적 적다 (현 경로상의 노드들만 기억하면 된다)
-목표 노드가 깊은 단계에 있을 경우에 해를 빨리 구할 수 있다.
✔️단점
-해가 없는 경로에서 깊이 빠질 수 있기 때문에, 실제로는 깊이를 설정해 주는 방법이 유용할 수 있다.
-얻어진 해가 최적 해라는 보장이 없음 (해에 다다르기만 하면 탐색 종료기 때문)
✔️구현 방법
(1) 스택 (스택 오버플로우 주의)
1.시작 정점을 스택에 삽입하여 방문 (visted 체크)
2.스택에서 꺼낸 정점이 아직 방문하지 않은 정점이라면, 방문 표시 후 이웃 정점들을 스택에 삽입
3.스택에 담긴 정점이 없을 때까지 2번 과정 반복
(2) 재귀함수
1.파라미터로 넘어온 정점이 이미 방문한 정점일 경우 return 하도록 base condition을 설정
2.파라미터로 넘어온 정점이 방문하지 않은 정점일 경우 방문 표시
3.인접 정점에 대해 재귀적으로 함수를 호출하며 탐색 진행
2.너비 우선 탐색 (BFS, Breadth-First Search)
✔️너비 우선 탐색(DFS)란?
최대한 넓게 이동한 다음 , 더이상 갈 수 없을 때 아래로 이동한다. 시작 노드에서 인접한 노드를 먼저 탐색하는 방법으로
시작 노드부터 가까운 노드를 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용
✔️사용 이유
-답이 되는 경로가 여러 개인 경우에도 최단 경로를 보장할 수 있다.
-최단 경로가 존재한다면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.
✔️단점
-경로가 매우 길 경우에는 탐색 가지가 급격히 증가해 보다 많은 메모리를 필요로 한다.
-해가 존재하지 않는다면 유한 그래프의 경우에는 모든 그래프를 탐색한 후 실패
-무한 그래프일때는 해도 못찾고 끝내지도 못한다.
✔️구현 방법
-큐(Queue)의 FIFO 구조 활용
1.시작 정점을 큐에 삽입
2.큐에서 정점을 하나 꺼내와 방문 표시
3.꺼내온 정점과 인접한 정점 중 아직 방문하지 않은 정점들을 큐에 삽입
4.큐에 저장된 정점이 없을 떄 까지 2~3번 과정을 반복
댓글