그래프 기초(의미, 분류, 구현 방법)

기초소개

그래프는 자료구조의 일종으로, 배열과 달리 데이터간의 관계를 나타낼 수 있는 자료구조입니다. 형태에 따라 각기 다른 특성을 가지고 있기 때문에 여러 세부 분류로 나뉘기도 합니다. 

 

그래프란?

데이터에 해당하는 정점과 정점을 이으며 정점끼리의 관계를 나타내는 간선으로 이루어진 자료구조입니다.

 

위 그림처럼 생긴 자료구조입니다.

이 그래프는 무엇을 나타내는 그래프일까요?

정점을 사람, 간선을 친구 관계로 표현한다면 집단에서 친구인 사람들을 표현하는 그래프가 됩니다.

정점을 도시, 간선을 길으로 생각한다면 지도처럼 도시 사이를 이동하는 경로를 표시하는 그래프가 됩니다.

이처럼 정점과 간선을 적절히 설정한다면 그래프가 많은 것들을 나타내도록 할 수 있습니다.

 

간선의 방향

방향은 일방 통행 도로처럼 간선에서 정해진 방향으로만 이동할 수 있다는 것을 의미합니다.

 

 

위 그래프에서 0번 정점은 5번 정점으로 이동할 수 있지만, 5번 정점은 0번 정점으로 이동하지 못합니다.

그렇다면 아래 그래프처럼 방향이 표시되지 않은 그래프는 무엇일까요?

 

간선에 방향이 없다고 생각할 수도 있지만, 보통은 익숙한 방식으로 구현하기 위해 간선이 정점 사이에 두 개 존재한다고 생각합니다. 즉, 위 그래프에서는 0번 정점에서 5번 정점으로 가는 간선도, 5번 정점에서 0번 정점으로 가는 간선도 존재한다고 여깁니다. 

 

간선의 가중치

가중치는 간선에 주어지는 값입니다. 

주로 거리, 비용 등을 나타내기 위해 사용합니다. 

 

그래프에서 가중치가 주어지지 않은 경우에는 가중치가 없다고 생각합니다. 

 

그래프의 구현

인접 행렬/인접 리스트 두 가지 구현 방식이 있습니다.

 

인접 행렬

행/열의 수가 그래프의 정점 수와 같은 표를 만들고, 표의 a행 b열을 a번 정점에서 b번 정점으로 가는 간선이라고 생각하는 구현 방식입니다. 각 칸마다 true/false로 간선의 유무를 표시하거나, 칸의 값이 0이라면 간선이 없고 아니라면 칸의 값을 해당 간선의 가중치로 생각하기도 합니다.

두 정점 사이에 간선이 있는지 알아내는 것은 빠르지만, 특정 정점에 연결되어 있는 간선들을 모두 살펴보는 작업에는 비효율적인 방식입니다. 

인접 행렬의 예시

인접 리스트

각 정점마다 리스트를 가집니다. 리스트에는 해당 정점에서 나가는 간선의 정보를 저장합니다. 

두 정점 사이에 간선이 있는지 알아보려면 해당 정점의 리스트를 모두 뒤져야 하지만, 

특정 정점에서 갈 수 있는 모든 정점을 탐색하는 작업은 빠르게 할 수 있습니다.

후자가 더 자주 수행되는 작업인 만큼 주로 인접 리스트를 활용하여 그래프를 구현합니다.

C++에서는 vector STL을 이용하여 쉽게 구현할 수 있습니다.

 

인접 리스트의 예시(간선 정보: 도착 정점, 가중치)

 

그래프 용어

그래프는 다양한 성질과 속성이 있는 만큼 여러 용어를 사용하여 그래프를 나타내고 분류합니다.

 

• 유향/무향 그래프 : 각각 방향이 있는/방향이 없는 그래프를 말합니다.
• 가중치 그래프 : 가중치가 있는 그래프를 의미합니다.
• 완전 그래프 : 모든 정점들이 다른 모든 정점들과 간선으로 이어져 있는 형태의 그래프입니다.
• 컴포넌트, 연결 요소 : 그래프에서 모든 정점들이 한 덩어리로 연결되어 있을 필요는 없습니다. 각 덩어리를 컴포넌트 혹은 연결 요소라고 합니다.
• 연결 그래프 : 연결 요소가 하나뿐인 그래프입니다.
• 사이클 : 한 정점에서 출발하여 간선을 따라가다 다시 출발 정점으로 도착하는 경로입니다.
• 트리 : 사이클이 없는 연결 그래프를 의미합니다. 매우매우 중요한 자료구조입니다.
• 차수, degree : 각 정점과 연결되어 있는 간선의 수를 의미합니다.
• indegree : 각 정점으로 들어오는 방향인 간선의 수를 의미합니다.
• outdegree : 각 정점에서 나가는 방향인 간선의 수를 의미합니다.