Search
🌑

그래프 탐색

태그
algorithm

그래프 탐색

어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법
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)