알고리즘> 그래프> 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS)

먼저 그래프를 소스코드로 표현하자

그래프를 탐색하는 두 가지 방법이 있다.

너비우선탐색과 깊이우선탐색이다...

 

 

 

 

너비 우선 탐색 Breadth First Search(BFS)

정점과 같은 레벨에 있는 노드들을 탐색하는 방식이다.

이것을 소스코드로 표현하면

 

시간 복잡도는?

노드수(V) + 간선수(E)

O(V+E)

 

 

 

 

깊이 우선 탐색 Depth First Search(DFS)

정점의 자식들을 먼저 탐색하는 방식이다.

이것을 소스코드로 표현하면

 

차이점은 스택을 쓴 것밖에 없다...