그래프탐색

1. 기본개념

그래프란 버텍스(Vertext)와 간선(Edge)으로 이루어진 자료구조중의 하나이다.
버텍스는 정점 엣지는 정점과 정점을 연결을 뜻한다.

2. 대표탐색종류

BFS(Breadth-First-Search):너비우선탐색 - 여러명을 한번씩 때리면서 감

DFS(Depth-First-Search):깊이우선탐색 - 한놈만 팬다

예)

BFS는 연재중인 여러웹툰을 보는것
DFS는 한웹툰이 완결될때까지 기다렸다가 한번에 쭉보는것

2-1.　시각자료

이미지출처:https://www.geeksforgeeks.org/difference-between-bfs-and-

위에서 보는바와같이 탐색의 순서는 각각 다르다
BFS: 부모밑의 자식노드를 탐색시 횡적으로 형제를 우선적으로 탐색한다.
DFS: 탐색시 자식의 후손노드들을 우선적으로 종적으로 탐색을 한다.

2-2. 시간복잡도구하기

O(n) = V(Vertext) + E(Edge)(n*V)
E는 각V에 연결되어있는 간선의 최대값을 가지고 구하면 된다.

2-3. 적합한 자료구조

BFS: Queue
DFS: Stack