그래프 탐색
어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법
•
Graph: Vertex(어떤 것) + Edge(이어지는 것)
그래프 탐색 종류
•
BFS: Breath-first search (너비 우선 탐색)
•
DFS: Depth-first search (깊이 우선 탐색)
BFS
1.
시작점에 연결된 Vertex 찾기
2.
찾은 Vertex를 Queue에 저장
3.
Queue의 가장 먼저 것 뽑아서 반복
시간복잡도: O(V+E)
DFS
1.
시작점에 연결된 Vertex 찾기
2.
연결된 Vertex를 계속해서 찾음
3.
더이상 연결된 Vertex 없을 경우 다음
시간복잡도: O(V+E)