[자료구조]그래프, 트리 개념&예시

1. 그래프

그림과 같이 여러개의 정점(노드)과 그 정점들을 연결하는 간선(edge)로 이루어진 자료구조이다.

크게 방향 그래프와 무방향 그래프로 나뉘는데, 방향그래프는 간선에 방향이 정해져 있어 해당 방향으로만 이동할 수 있는 그래프이다.

 

그래프에서는 다음과 같은 용어들을 사용한다.

인접 : 간선에 의해 어느 두 정점이 직접적으로 연결되어있는 경우 인접했다고 표현한다.

차수 : 하나의 정점에 연결된 간선의 개수를 나타낸다.

사이클 : 그래프 내부에 어느 한 정점에서 시작하여 다시 그 정점으로 돌아오는 경로가 있는 경우 이를 사이클이라고 부른다.

 

활용 예시)

네비게이션 : 교통 상태를 그래프로 표현하여 최적의 길을 도출해낼 수 있다.

전자회로 설계 : 각 부품을 정점으로 하여 회로를 살계할 수 있다.

데이터베이스 관리 : 관계형 대이터베이스를 다루는 경우, 이를 그래프로 표현하여 쉽게 다룰 수 있다.

 

 

2. 트리

그래프 중에서 사이클이 없는 방향그래프를 트리라고 한다.

계층 구조를 가지고 있으며, 어느 노드의 상위노드를 부모, 하위노드를 자식이라 부른다.

 

또한 다음과 같은 용어들을 사용한다.

루트(root)노드 : 가장 위에 있는 최상위 노드

레벨 : 트리의 깊이를 나타내는 용어로 루트를 level0으로 놓으면 그 자식노드들을 1에 위치한다.

잎 : 자식이 없는 말단 노드

서브 트리 : 트리의 일부분만 가져와 또 다른 트리를 만든 것

 

활용 예시)

파일 시스템 : 파일 위치를 트리 구조를 이용하여 저장하고, 이를 이용하여 접근할 수 있다.

텍스트 자동완성 : 자동완성 알고리즘은 트리구조를 이용하여 확률을 계산한다.

텍스트 압축 : 여러 압축 방법 중 Huffman방식은 트리를 사용하여 각 문자에 대한 코드를 생성한다.

 

 

그래프를 탐색하는 방법  ▶ 그래프 탐색 방법, 예시(DFS, BFS)