TIL 47일차_자료구조: 그래프와 트리

흔히 자료구조 중 스택,큐,그래프,트리 이 4가지가 가장 기본이 되고,
각종 테스트나 입사 면접문제로도 자주 출제된다.

왜냐? 중요하니까!

이들이 중요한 이유는 현실의 대다수, 또는 모든 것을 표현하는 개념이기 때문이다.
오늘은 그래프와 트리에 대해서 알아보자.

그래프와 트리?

그래프

그래프는 개체간의 "관계" 를 다룬다.
현실에서도 수많은 개체가 상호작용하는데 이들이 연결되어 있을 때, 이 개체의 노드를 엣지로 이을 수 있고,
이것이 곧 그래프이다.

트리

트리는 계층을 표현한다.
정점인 루트노드부터 시작해서 말단인 리프노드까지 분기한다.

그래프와 트리

그래프와 트리는 분명 비슷하다.
왜냐하면, 트리의 부모노드와 자식노드의 계층관계도, 결국 그래프에서 말하는 "관계" 라고 할 수 있기 때문이다.

그렇다면 위의 사진처럼, 트리는 그래프의 하나일 뿐일까?
트리는 다음의 특징들을 가진 그래프라고 할 수 있다.

가중치가없다.
사이클이 없다.
두 정점간 최단경로가 단 하나뿐이다.
간선의 개수는 정점의 개수에서 1을 뺀 값이다.
트리는 그래프의 특별한 케이스이며, "최소 연결 트리"라고도 불린다.
루트 노드 개념이 있고, 부모-자식 개념도 있다.
자기 자신을 돌 수 없음은 물론이고 loop 순환도 불가능하다.
부모-자식 관계의 흐름은 상하이다.
트리의 순회는 전위, 중위, 후위 순환으로 이어지고, 이것들은 모두 그래프의 DFS, BFS 안에 있다.
트리는 계층 모델이다.

그러나 트리는 그래프가 갖고있지 않은 특징을 갖는다.
바로 위에서 말한 계층이다.

그래프는 개체간의 관계만 규정하지, 그들의 계층관계까지 고려하지는 않는다.
그래서 실제로 위에서 언급한 트리의 특징을 모두 갖는 그래프는
계층관계는 갖지 않으므로, "루트없는트리(unrooted tree)" 라고 한다.

따라서 위의 사진처럼 트리를 그래프에 속하기만한, 두집합의 개념으로 이해하면 조금은 부족하다.
트리는 그래프와 현실의 계층이라는 개념과의 교집합으로 보는 것이 정확할 것이다.

확실히, 트리는 그래프에 속하기에 관계를 표현한다.
그러나 여기에 계층이라는 개념을 포함하여, 일반 그래프와 달리 계층관계까지 표현할 수 있는 것이다.