어떻게 점과 선으로 잇는 자료, 그래프

관계를 점과 선으로 담는다

지금까지는 값을 줄이나 표, 트리에 담는 방법을 보았다. 그런데 어떤 데이터는 값 하나하나보다 값 사이의 관계가 더 중요하다. 누가 누구와 친구인지, 어느 역과 어느 역이 이어져 있는지 같은 것이다.
이럴 때는 줄로 세우기가 어색해요. 그래서 사람을 점으로, 친구 사이를 선으로 그린다. 점은 노드, 선은 간선이라고도 부르며, 점과 선만으로 관계가 그대로 담긴다.

두 사람을 차례로 눌러 선으로 이어 보자. 점은 사람, 선은 친구 관계예요.

점을 잇자 관계가 눈에 보였다. 누가 누구와 이어졌는지는 선만 보면 바로 알 수 있다. 표에 한 줄씩 적은 것보다 훨씬 그림처럼 다가온다.
점은 대상, 선은 관계. 이 둘로 담은 자료를 그래프라고 불러요. 친구처럼 서로 주고받는 관계는 방향 없는 선으로, 누가 누구를 팔로우하는 것처럼 한쪽으로만 향하는 관계는 화살표 선으로 그린다. 그렇다면 이 선을 따라가면 무엇을 알 수 있을까?

선을 타고 친구의 친구로

한 사람에서 시작해 보자. 그 점에 이어진 선을 따라가면 그 사람의 친구가 나온다. 거기서 멈추지 않고 친구의 점에 이어진 선을 또 따라가면 친구의 친구가 나온다.
이렇게 한 칸씩 더 멀리 가면 아는 사람의 아는 사람까지 닿아요. 소셜 서비스가 '알 수도 있는 친구'를 추천하는 것도 이런 방식이다.

한 사람을 누르면 친구가, 다시 누르면 친구의 친구가 차례로 켜져요.

한 번 누르니 친구가, 또 누르니 친구의 친구가 켜졌다. 시작한 사람에게서 얼마나 떨어졌는지는 선을 몇 번 탔는지로 정해진다.
선을 한 번 타면 친구, 두 번 타면 친구의 친구다. 표였다면 이것을 알아내려고 몇 번이고 다시 뒤졌을 거예요. 선을 따라가면 이렇게 쉽다.

이웃을 따라 무리를 둘러본다

한 점에 선으로 바로 이어진 점들을 그 점의 이웃이라고 한다. 한 점에서 이웃으로, 다시 그 이웃의 이웃으로 선을 타고 계속 퍼져 나가 보자.
그러다 보면 더 갈 곳이 없을 때가 온다. 그때까지 닿은 점들이 서로 이어진 한 무리예요. 선으로 이어지지 않은 점은 그 무리에 끼지 못한다. 가까운 이웃부터 한 겹씩 넓혀 가는 이 방법을 너비 우선 탐색이라고 한다.

켜진 무리의 가장자리에 닿은 이웃을 눌러 한 칸씩 퍼뜨려 보자. 이어진 점만 켜져요.

이웃을 따라 퍼지니 이어진 점들이 차례로 켜졌다. 선이 닿는 곳은 모두 둘러볼 수 있었다. 반대로 떨어진 점은 아무리 가도 켜지지 않았다.
선으로 이어졌느냐가 무리를 가르는 것이에요. 이웃 따라가기는 그래프에서는 선만 보면 되니 쉽다. 그렇다면 같은 일을 표로 하면 어떨까?

표로 할까, 그래프로 할까

친구 관계를 표에 적었다고 하자. 친구의 친구를 찾으려면 먼저 표에서 내 친구를 찾아 적고, 그 친구마다 다시 표를 뒤져야 한다. 한 단계 더 갈 때마다 표를 또 훑는 셈이다.
그래프라면 점에서 선을 따라가고, 그 점에서 또 선을 따라가면 끝난다. 관계가 핵심일 때는 그래프가 훨씬 편해요.

같은 "친구의 친구" 질문을 표와 그래프로 풀어 보자. 누르는 횟수가 몇 번 드는지 견주어 봐요.

표로는 같은 답을 찾는 데 누르는 횟수가 훨씬 많이 들었다. 조회를 거듭해야 했기 때문이다. 그래프는 선을 두 번 따라가니 끝났다.
물론 표가 나쁜 것은 아니에요. 한 줄씩 기록하고 모아 보기에는 표가 좋다. 다만 관계를 따라가는 일이라면 점과 선으로 담은 그래프가 훨씬 자연스럽고 빠르다. 지도 앱이 길을 찾을 때도 역과 길을 점과 선으로 놓고, 선마다 거리를 적어 둔 그래프를 쓴다.

정리

한 줄로 모으면 이렇다. 대상을 점으로, 관계를 선으로 담은 것이 그래프다. 한 점에서 선을 따라가면 이웃이 나오고, 이웃을 또 따라가면 친구의 친구가 나온다.
선을 타고 퍼지면 이어진 무리가 보여요. 관계가 핵심인 일에서는 표를 여러 번 뒤질 것을 선만 따라가면 된다. 점=대상, 선=관계, 그리고 이웃 따라가기, 이것이 그래프다.

핵심을 차례로 눌러 되짚어 보자. (점=대상, 선=관계 → 친구의 친구 → 이웃 따라가기 → 관계엔 그래프)

이제 관계를 점과 선으로 담아 선을 따라 누비는 방법을 알았다. 표로는 어색하던 친구의 친구가 그래프에서는 선 두 번이면 닿았다. 자료를 어떤 모양으로 두느냐에 따라 같은 일이 쉬워지기도 어려워지기도 한다.
그런데 데이터베이스에 무언가를 물어보려면 정해진 말로 물어야 해요. 다음 레슨에서는 데이터베이스에 질문하는 언어, SQL을 배운다.