[자료구조] Graph, Tree

BANSEOK SUH·2021년 4월 22일

자료구조

목록 보기

1/2

그래프(Graph)

프로그래밍에서의 그래프는 흔히 우리에게 알려진 표 형식의 그래프가 아닙니다. 그것은 좀 더 복잡하게 얽히고 섥혀 있는 관계를 보여주는 것입니다. 거미줄 혹은 네트워크 망과 비슷하죠. 아래의 그림과 같습니다.

그래프는 각 점을 선으로 이어주는 모습인 듯합니다. 여기서의 각 점은 정점(vertex)라고 부르고, 선은 간선(edge)이라고 부릅니다.

용어

무향그래프 (undirected graph) : 간선이 있다면, 서로 이어진 두 정점은 서로가 서로에게 이동할 수 있는 그래프입니다.
단방향그래프 (directed graph) : 간선이 있다면, 한 방향으로만 이동할 수 있는 그래프입니다.
진입차수 (in-degree) / 진출차수 (out-degree) : 한 정점의 진입, 진출하는 간선이 몇 개인지를 나타냅니다.
인접 (adjacency) : 두 정점간에 간선이 직접 이어져 있다면, 이 두 정점은 서로 인접합니다.
자기 루프 (self loop) : 한 정점에서 출발해 다른 정점을 거치지 않고 곧바로 자기 자신에게로 진입하는 경우, 자기 루프를 가졌다고 표현합니다.
사이클 (cycle) : 한 정점에서 출발해 다른 정점을 겨처 자기 자신에게로 진입하는 경우, 사이클이 있다고 표현합니다.

그래프 표현 방식

그래프를 표현하는 방식에는 인접 행렬 방식 (Adjacency Matrix)과 인접 리스트 방식 (Adjacency Matrix)이 있습니다.

아래와 같은 그래프가 있다고 가정합시다.

인접 행렬 (Adjacency Matrix)

인접 행렬은 정점들간의 인접함을 표시해주는 행렬로, 2차원 배열의 모습을 가지고 있습니다. 아래 그림과 같습니다.
정점들 간의 간선 여부는 0과 1로 표시합니다.

코드로 표현하면 다음과 같습니다.

// matrix를 크기만큼 0으로 채워 초기화합니다.
let matrix = new Array(3).fill(0).map((el) => new Array(3).fill(0));
// [0, 0, 0]
// [0, 0, 0]
// [0, 0, 0]

// 간선 정보를 입력합니다.
matrix[0][2] = 1; // A -> C
matrix[1][0] = 1; // B -> A
matrix[1][2] = 1; // B -> C
matrix[2][0] = 1; // C -> A

matrix;
// [
//  [0, 0, 1],
//  [1, 0, 1],
//  [1, 0, 0]
// ]

인접 리스트 (Adjacency List)

인접 리스트는 각 정점이 어떤 정점과 인접한 지를 리스트의 형태로 보여줍니다. 아래의 그림과 같습니다.

코드로 표현하면 다음과 같습니다.

let ObjList = {}; // 간선 정보 담을 빈 객체 생성합니다. 배열로도 가능합니다.

// 각 key에 해당하는 value를 빈 배열로 초기화합니다.
for (let i=0; i<3; i++) {
  objList[i] = [];
}

// 간선 정보를 입력합니다.
objList[0].push(1); // A -> B
objList[1].push(0, 2); // B -> A, B -> C
objList[2].push(1); // C -> B

objList;
// {
//  0: [1],
//  1: [0, 2],
//  2: [1]
// }

위의 인접 행렬, 인접 리스트를 사용하여 관련 알고리즘을 해결할 수 있습니다.

트리(Tree)

트리구조는 조금 익숙할 듯합니다. 컴퓨를 사용할 때 흔히 볼 수 있는 디렉토리 구조가 트리 구조와 같습니다. 기본적으로 트리구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조입니다. 아래로 쭈욱 뻗어있기 때문에 사이클이 없습니다.

용어

루트 (Root) : 트리 구조의 가장 상위 노드를 말합니다.
노드 (Node) : 루트로부터 연결되어 있는 각 데이터들을 말합니다.
부모 노드 (Parent Node) : A가 B, C의 하위 노드들을 가지고 있다면, A는 B, C의 부모 노드입니다.
자식 노드 (Children Node) : B, C는 A의 자식 노드입니다.
리프 노드 (Leaf Node) : 자식 노드를 더 이상 갖지 않는 노드를 말합니다.
레벨 (Level) : 이어져 있는 노드의 간격(거리)을 말합니다. ex) 루트: 레벨 1
트리의 높이 (Height) : 루트부터 가장 안쪽에 있는 노드까지의 레벨을 말합니다.
형제 노드 (Sibling Node) : 같은 레벨에 있는 노드를 말합니다.
서브 트리(Sub Tree) : 큰 트리의 내부에 작은 트리를 형성한다면, 그것은 서브트리라고 불립니다.

효율적인 탐색을 위한 트리 구조

효율적인 탐색을 위해 여러 트리의 모습이 발전되었는데, 그 중 가장 간단하고 많이 사용되는 것은 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)입니다.

이진 트리(Binary Tree)

자식 노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 합니다. 데이터의 삽입, 삭제 방법에 따라 아래의 세 종류의 트리로 나뉩니다.

정 이진 트리(Full Binary Tree) : 각 노드가 0개 혹은 2개의 자식 노드를 가집니다.
완전 이진 트리(Perfect Binary Tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 왼쪽이 채워져야 합니다.
포화 이진 트리(Complete Binary Tree) : 정 이진 트리이면서 완전 이진 트리인 경우를 말합니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

이진 탐색 트리 (Binary Search Tree)

모든 왼쪽 자식들은 루트나 부모보다 작은 값, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 트리를 이진 탐색 트리라고 합니다.
숫자로 이루어진 배열을 sort()함수를 사용하여 정렬한 다음 이진 탐색 트리로 알고리즘을 해결할 수 있습니다.

트리 순회 (Tree Treversal)

모든 노드를 한 번씩 방문하는 것을 말합니다. 순회할 때의 순서는 항상 왼쪽부터 오른쪽으로 순회합니다.
트리를 순회할 수 있는 방법은 크게 아래의 세 가지 방법으로 나뉩니다. 그 기준은 루트를 어디에 두느냐, 루트를 어느 시점에 순회를 하느냐에 따라 달라집니다.