29. 그래프

그래프란?

우리는 그래프라고 하면 수학에서 사용하는 차트를 제일 먼저 생각하게 된다.

이번에 이야기하는 그래프는 차트와는 다르다.

 

그래프는 정점과 간선으로 이루어진 자료구조이다. 정점은 그래프에서 노드를 의미하고, 간선은 정점과 정점을 연결하는 선을 의미한다. 정점과 간선은 우리가 이전에 들어본 적이 있을 것이다. 

이전에 배운 자료구조인 트리도 정점과 간선으로 이루어져 있다. 미리 이야기 하지만 트리는 그래프의 일종이다.

 

그래프는 다양한 분야에서 사용된다. 예를 들어 지도, 인터넷 등 다양한 분야에서 활용된다.

그래프는 노드 간의 연결 관계를 나타내므로, 연결된 객체 간의 관계를 모델링하는데 적합하다.

---

그래프의 종류

그래프는 다양한 종류가 존재한다.

 

무방향 그래프 : 간선이 양방향으로 이어진 그래프이다.

방향 그래프 : 간선이 단방향으로 이어진 그래프이다.

가중치 그래프 : 각 간선이 가중치를 가지는 그래프이다.

완전 그래프 : 모든 정점들이 서로 연결된 그래프이다.

부분 그래프 : 그래프의 일부 정점과 간선으로 이루어진 그래프이다.

신장 트리 : 그래프의 일부 간선을 선택하여 모든 정점을 연결하고 사이클이 없는 트리이다.

 

단순히 이름과 설명으로는 이해하기 어려울 수 있지만, 앞으로 다양한 그래프 알고리즘과 설명을 하면서 추가로 알아보도록 하자.

---

그래프 용어

정점 : 그래프에서 가장 기본적인 단위로, 점으로 표현된다.

간선 : 두 개의 정점을 연결하는  선으로, 선으로 표현된다.

인접 : 두개의 정점이 간선으로 연결되어 있을 때, 인접한 정점이라고 표현한다.

차수 : 하나의 정점이 가지고 있는 간선의 수를 의미한다. 

경로 : 두 개의 정점을 연결하는 간선들의 순서대로 이어진 길

사이클 : 그래프에서 한 정점에서 시작해서 같은 정점으로 돌아오는 경로를 의미한다.

가중치 : 그래프의 간선에 부여된 가중치 값으로, 간선의 길이나 비용을 의미한다.