깊이 우선 탐색 DFS

18장 그래프로 뭐든지 연결하기

페이스북 혹은 인스타 같은 소셜 네트워크에서 친구 관계는 상호적이다. 이를 구현하기 위해 2차원 배열을 사용한다면 특정 유저의 친구를 찾기 위해 목록 내 관계를 일일히 확인해야 하고, 이는 O(N)이 걸리는 매우 느린 방법이다. 이때 그래프라는 자료 구조를 사용하면 O(1) 시간 만에 찾을 수 있다. 18.1 그래프 그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. 소셜 네트워크의 예시에선 한 사람은 한 노드로, 사람 간 친구 관계는 선으로 표현한다. 18.1.1 그래프 대 트리 트리도 그래프의 한 종류다. 두 자료 구조 모두 서로 연결되는 노드로 구성된다. 모든 트리는 그래프지만, 그래프가 모든 트리는 아니다. 트리로 규정되는 그래프는 사이클이 있을 수 없으며,..