페이스북 혹은 인스타 같은 소셜 네트워크에서 친구 관계는 상호적이다.
이를 구현하기 위해 2차원 배열을 사용한다면 특정 유저의 친구를 찾기 위해 목록 내 관계를 일일히 확인해야 하고, 이는 O(N)이 걸리는 매우 느린 방법이다.
이때 그래프라는 자료 구조를 사용하면 O(1) 시간 만에 찾을 수 있다.
그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다.
소셜 네트워크의 예시에선 한 사람은 한 노드로, 사람 간 친구 관계는 선으로 표현한다.
트리도 그래프의 한 종류다. 두 자료 구조 모두 서로 연결되는 노드로 구성된다.
모든 트리는 그래프지만, 그래프가 모든 트리는 아니다.
트리로 규정되는 그래프는 사이클이 있을 수 없으며, 모든 노드가 서로 연결되어야 한다.
그래프에는 사이클을 형성하는 노드, 즉 서로 순환적으로 참조하는 노드가 있을 수 있다. 반면 트리에는 사이클이 있을 수 없다. 사이클이 있는 그래프는 트리가 아니다.
소셜 네트워크에 방금 가입해 친구가 0명인 회원이 있다면 노드는 존재하지만 연결된 친구가 한 명도 없는 상태이다.
그래프에만 쓰이는 몇 가지 기술 용어가 있다. 흔히 각각의 데이터를 노드라고 부르지만 그래프에서는 각 **노드를 정점(vertext)**이라 부른다.
정점을 잇는 선도 그래프 용어로 간선이라 부른다.
이러한 간선으로 연결된 정점은 서로 **인접한다 (adjacent)**라고 말하며, 인접한 정점을 이웃 neighbor이라고도 부른다.