그래프란?
이런 형태로 생긴 것을 그래프라고 합니다.
동그라미 부분을 Vertex(혹은 Node, 정점)라 부르고 정점끼리 이은 선분을 Edge(간선)라고 부릅니다.
그래프의 종류
그래프에는 여러 가지 종류가 있습니다.
위 사진 같은 그래프는 무향 그래프 이면서 비(非)가중치 그래프입니다.
만약 간선마다 가중치가 있다면, 그 그래프는 가중치 그래프가 됩니다.
가중치 그래프는 위와 같은 형태로 생겼습니다.
무향 그래프는 간선이 양방향으로 작용하지만, 유향 그래프(방향 그래프)는 간선이 지정된 방향으로만 작용합니다. 보통 아래 그림처럼 유향 그래프를 교현합니다.
이분 그래프나 완전 그래프와 같은 개념은 나중에 해당 개념이 필요한 알고리즘 설명에서 언급하도록 하겠습니다.
자주 사용하는 용어
무향 그래프와 방향 그래프에서 사용되는 용어를 살펴봅시다.
가장 먼저, 맨 위에서 언급한 정점/간선이라는 용어는 사람에 따라 부르는 호칭이 다소 달라집니다.
- 정점, 노드(node), 버텍스(vertex), 꼭짓점, …
- 간선, 에지(edge), 엣지, 변, …
기초적인 수준에서 많이 언급되는 용어도 몇 개 알아봅시다.
- 차수(degree)
- 한 정점에 이어져 있는 간선의 수를 나타냅니다. 주로 무향 그래프에서 많이 사용합니다.
- 인접(adjacent)
- 두 개의 정점 사이에 간선이 존재한다면, 두 정점은 인접한 정점입니다.
- 입력 차수(in-degree)
- 한 정점으로 들어오는 간선의 수를 나타냅니다. 주로 유향 그래프에서 많이 사용합니다.
- 출력 차수(out-degree)
- 한 정점에서 나가는 간선의 수를 나타냅니다. 주로 유향 그래프에서 많이 사용합니다.
- 사이클(cycle)
- 한 정점에서 출발해 다시 시작 정점으로 돌아오는 경로를 말합니다.
이번에는 글에서는 그래프를 간단하게 소개했습니다.
다음부터는 그래프의 표현 방법, 그래프의 탐색, 그래프의 최단경로 와 같은 그래프 관련 알고리즘을 소개하려 합니다.