[자료구조] 그래프 자료구조에 대해 알아보자!(노드, 간선, 루트 노드, 깊이, 높이, 차수)

본 포스팅에서는 그래프(graph) 자료구조에 대해 알아봅니다.

그래프 자료구조의 구성

그래프는 그림 1 과 같이 노드(Node)와 간선(Edge)으로 표현됩니다. 이때 노드는 정점(Vertext)이라고도 불립니다. 일반적으로 노드와 간선은 각각 도시와 도시를 잇는 도로를 예시로 많이 표현됩니다. 즉, A 도시(노드)와 B 도시(노드)가 있을 때, A 도시에서 B 도시로 이동하기 위해 도로(간선)를 거친다고 생각하시면 노드와 간선에 대한 이해가 쉬울 것입니다.

 

그림 1.  그래프의 구성: 노드와 간선

 

그래프 탐색?

그래프 탐색이란 하나의 노드에서 시작해서 다른 노드들을 방문하는 것을 의미합니다.

노드 인접?

두 노드가 간선으로 연결되어 있다면, '두 노드는 인접(Adjacent)해 있다'라고 말합니다.

그래프 자료구조 관련 용어 정리

그래프(트리, tree) 자료구조와 관련한 용어를 아래 표 1 과 같이 정리해 보았습니다.

용어	설명
루트 노드(root node)	부모 노드가 없는 최상위 노드
단말 노드(leaf node)	자식 노드가 없는 노드
크기(size)	모든 노드의 개수
깊이(depth)	루트 노드로부터 거리
높이(height)	깊이의 최댓값
차수(degree)	노드별 간선 개수(트리에서는 자식 노드 방향 간선 개수)

 

위의 용어를 아래 그림 2 를 활용하여 알아보겠습니다.

그림 2.  그래프(트리) 자료구조 예시

 

여기서 루트 노드는 부모 노드가 없는 최상단 노드로서 A가 해당합니다. 단말 노드는 자식 노드가 없는 노드로서 F, E, G가 해당합니다. 트리의 크기는 트리에 포함된 모든 노드의 개수이기에 7이 됩니다. 각 노드의 깊이는 F가 루트 노드로부터 가장 멀리 떨어져 있는 3이며 D는 2, B는 1이라고 할 수 있습니다. 트리의 높이는 루트 노드로부터의 거리가 가장 먼, 다시 말해, 깊이의 최댓값을 갖는 F 노드의 깊이인 3입니다. 각 노드의 차수의 경우, 노드 A는 자식 노드가 2개이므로 2가 되며, 노드 C의 자식 노드는 1개이므로 차수 역시 1이 됩니다.

---

포스팅에 오류가 있을 경우 아래에 댓글 남겨주시면 감사드리겠습니다.

 

 

그럼 오늘도 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.