이번 글에서는 그래프의 개요를 알아보려고 한다.

그래프의 정의

---

노드(Vertex or Node)와 간선(Edge)을 포함하는 비선형 자료구조

그래프는 예를 들어 실생활의 친구 관계 개념을 생각하면 좋다.

위의 그림을 보면 알 수 있듯이, 우리의 친구 관계는 그래프로 표현할 수 있다.

위 그래프에서 각각의 인간(Person)은 A, B, C ...등의 Vertex(Node)로 표현되고, Vertex(Node) 간 Friend라는 관계(Edge)를 가지고 있다.

이러한 그래프의 종류 또한 다양하다.

그래프의 종류

그래프의 종류는 일단 크게 세 가지로 나눠서 생각할 수 있다.

• undirected graph : 무방향 그래프
• directed graph: 방향 그래프
• weighted graph: 가중치 그래프

각각의 그래프의 종류를 살펴보자.

undirected Graph(무방향 그래프)

위의 친구 관계를 나타내는 그래프를 보면 이해가 가능하다.

두 노드 사이에 있는 Edge가 특정 방향을 가지지 않고, 서로를 향해 이중의 방향성을 띄는 그래프를 뜻한다.

directed Graph(방향 그래프)

방향 그래프는 무방향 그래프와 반대의 개념으로 짝사랑 관계로 이해하면 편하다.

위처럼 친구 관계 간에 서로 좋아하는 관계를 위의 방향 그래프로 표현할 수 있다.

방향 그래프는 노드 사이의 Edge가 방향성을 가진다.

weighted Graph(가중치 그래프)

가중치 그래프는 우리 실생활의 지도를 생각하면 좋다.

위 그림처럼 각각의 장소가 노드가 되고, 그 장소 간의 거리가 정해져 있다.

Edge에 가중치가 있다고 표현할 수 있는 것이다.

그래프 이론에서 쓰이는 용어 정리

이해를 돕기 위해 다시 친구 그래프를 보면서 알아보자.

• Vertex(Node)
  - 위 그래프에서 A,G,B 와 같이 간선(친구관계)으로 이어져 있는 "사람"으로 생각하면 된다.
• Edge
  - 위 그래프에서 Friend라고 되어 있는 "사람(Vertex)"을 연결해주는 선으로 생각하면 된다.