[기초] 그래프의 탐색

그래프의 탐색의 목적 

: 한 정점에서 시작해서 연결된 모든 정점을 한 번씩 방문하는 것. (DFS, BFS)

- 방문 순서를 어떻게 결정하는 것이냐에 따라 DFS, BFS 는 다르다.

 

보편적인 경우에서, 시간 복잡도 측면에서 인접 리스트를 활용하는 것이 더 빠르다.

DFS 와 BFS 1260

연결 요소

위 그래프는 연결요소가 2개이다.

연결 요소는 DFS / BFS 탐색 둘 다 이용해서 구할 수 있다.

DFS 가 시작한다는 것은 연결 요소를 찾았다. 라는 것과 같다.

연결 요소의 개수 11724

이분 그래프