Tree
Tree는 나무가 자라듯이 하나의 뿌리에서 여러 가지로 퍼지는 듯한 형태를 가지고 있습니다.
Graph구조의 한 종류이며 특수한 케이스로, 사이클이 존재하지 않는 하나의 연결 그래프입니다
Tree의 구조와 특징
Tree는 가장 위의 경로, 뿌리인 Root에서 시작하여 여러 개의 데이터를 간선으로 연결합니다.
연결되는 각 데이터를 Node라고 하며, 각 Node의 관계는 다음과 같습니다.
두 개의 Node가 상하 관계를 가지게 되면 부모/자식 관계가 됩니다. Root인 A는 B와 C의 부모이고, B는 D와 E의 부모가 됩니다.
자식을 가지지 않는 J와 같은 Node는 나무의 잎과 같다고 하여 leaf node라고 부릅니다.
각 Node는 Root에서부터 얼마나 떨어져있는지를 나타내는 수치인 깊이를 가집니다.
B는 Root로부터 1칸 떨어져있어 1의 깊이를 가지게 되며, 같은 깊이를 가진 B와 묶어서 Level 1 로 표현할 수 있습니다.
또한, 같은 부모와 깊이를 가진 Node는 형제 관계가 됩니다.
Node가 깊이를 가지듯이 높이도 가질 수 있습니다. 높이는 Node가 leaf node에서 얼마나 떨어져있는지 나타냅니다.
Graph
Graph는 여러개의 정점이 간선으로 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다.
Graph의 구조와 특징
직접적인 관계를 가진 두 정점은 간선으로 연결되어있습니다.
간접적인 관계를 가진 두 정점은 몇 개의 정점과 간선에 걸쳐 연결됩니다.
인접 행렬
간선 하나로 바로 이어지는 두 정점은 인접하다고 말합니다.
두 정점이 인접한지는 2차원 배열로 나타낼 수 있는데, 위의 사진을 예시로 들면
[1][2] === 1;
[1][3] === 1;
[2][6] === 1;
[1][6] === 0;
이렇게 나타낼 수 있습니다.
인접 리스트
각 정점이 어떤 정점과 인정하는지 리스트(배열)의 형태로 나타냅니다. 각 정점마다 하나의 리스트를 가지고 있습니다.
자주 쓰이는 Graph 용어
-
정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
-
간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
-
인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
-
가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 - 그래프를 뜻합니다.
-
비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
-
무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, - 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
-
진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인- 지를 나타냅니다.
-
인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
-
자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
-
사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.
