트리는 방향 그래프인가? 무방향 그래프인가?

질문의 배경

최근 면접스터디를 진행 중인데요. 자료구조와 알고리즘 파트를 진행하면서 트리와 그래프의 차이, 이진 탐색 트리와 완전 이진 트리에 대한 질문이 나오면서 얘네한테 방향성이랄 것이 있는지에 대한 토론을 했답니다.

명확하게 결론이 날 줄 알았는데 구글링을 해 보니 그렇지 않았습니다.

한 다섯 개 정도의 블로그에서는 방향이 있다고 하고, 네 개 정도 블로그에서는 방향이 없다고 하더라고요. 진짜에요

이럴 수가… 아니 이런 Mr.애매모호가 싫어서 컴퓨터공학 왔다고

결론을 후다닥 말씀드리도록 하겠습니다.

트리는 방향 그래프로 볼 수도 있고, 무방향 그래프로 볼 수도 있다.

이딴 게 결론?

입니다.

정말 열받는 부분이죠?

이유에 대해 알아봅시다.

 

 

그래프 이론에서의 “트리”

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

출처는 위키백과입니다.

파파고를 돌려 보았어요.

그래프 이론에서 트리(tree)는 임의의 두 꼭짓점이 정확히 하나의 경로로 연결된 무방향 그래프 또는 동등하게 연결된 비순환 무방향 그래프이다.

그러니까 그래프 이론에서의 트리는 무방향 그래프가 맞습니다.

하지만 저는 수학과가 아니라 컴퓨터공학과라서 그냥 tree가 아니라 완전 이진 트리, 이진 탐색 트리, 레드 블랙 트리…등등등의 트리가 궁금합니다.

그럼 컴퓨터과학의 자료구조로써의 트리도 그래프 이론의 트리일까요?

 

컴퓨터과학의 자료구조 “트리”

잠깐. 컴퓨터과학에서의 트리가 뭘까요?

제가 생각하는 컴퓨터과학에서의 트리는 여러분이 생각하는 대충 그러한 자료구조입니다. 부모 노드와 자식 노드가 있고, 루트 노드가 존재하고, 층수(level)가 있고…

사실 이러한 유형의 "컴퓨터과학에서의 트리"는 그래프 이론에서의 트리가 아닙니다.

굳이 모양이 비슷한 친구를 데려와 보자면 루트 트리와 비슷하지만, 똑같지도 않습니다. “일반적으로” 루트 트리의 형태를 띠기는 합니다.

그래프 이론에서의 루트 트리는 방향이 존재합니다. 루트 쪽이든 반대쪽이든…

컴퓨터과학의 자료구조 트리에는 부모와 자식 노드가 존재하죠.

이 관계를 방향이 있는 간선으로 “일반적으로” 간주하여 트리는 방향 그래프의 일종이다, 라고 할 수 있습니다.

그러니까 컴퓨터과학에서 자료구조의 일종인 트리는 방향 그래프입니다.

---

MST?

그런데 개발자가 다루는 트리는 다 자료구조에서의 트리니까 방향 그래프다,라고 생각하면 아차 싶은 부분이 있습니다.

MST입니다.

알고리즘을 공부할 때 종종 등장하는 문제 유형이죠.

최소 스패닝 트리, Minimum Spanning Tree, 크루스칼과 프림 알고리즘을 이용해 구할 수 있는 이 트리의 정의는 다음과 같습니다.

주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

오 트리네요. 그럼 이 친구도 방향이 있을까요?

없습니다. MST는 무방향 그래프입니다.

MST의 트리는 그래프 이론에서의 트리입니다.

하 진심…

 

 

이제 블로그 글들이 방향이다 무방향이다로 꼬이게 된 이유를 대충 알게 되셨습니다.

정리해 볼까요.

1. 그래프 이론에서의 트리는 무방향
2. 컴퓨터과학의 자료구조인 트리는 방향
3. MST는 그래프 이론에서의 트리를 말하는 것(즉 무방향 노사이클 그래프)

용어를 사용할 때는 항상 맥락을 파악합시다.