[자료구조] 그래프 (Graph)

그래프란?

---

그래프는 정점(vertex: V)과 정점들을 연결하는 간선(edge: E)으로 구성된 자료구조이다. 예를 들어 지하철 노선도를 그래프라고 할 수 있다.

3개의 정점과 간선으로 구성된 그래프

그래프는 트리와는 달리 순환이 발생해도 된다. 순환이 발생하지 않는 무방향 연결 그래프를 트리라고 할 수 있다. 트리도 그래프의 한 종류인 것이다.

 

 그래프 용어 정의

---

• 노드 또는 정점 (Node or Vertex): 그래프의 기본 단위로 각 노드는 데이터를 포함할 수 있다.
• 간선 또는 변 (Edge): 두 노드를 연결하며 방향이 있을 수도 있고 없을 수도 있다.
• 정점의 차수 (Degree): 하나의 정점에 근접하는 변의 개수를 말한다. 모든 정점의 차수의 합은 변의 개수의 2배이다. 그리고 그래프에서 차수가 홀수인 정점의 개수는 짝수이다.
• 내차수 또는 진입 차수 (in-degree): 한 정점을 끝점으로 하는 화살표의 개수
• 외차수 또는 진출 차수 (out-degree): 한 정점을 시작점으로 하는 화살표의 개수
• 인접 (adjacent): 두 정점이 인접한다는 것은 그 두 정점 사이를 연결하는 변이 존재한다는 것이다.
• 근접 (incident): 어떤 변이 어떤 두 정점과 근접하다면 그 변은 그 두 정점을 연결한다.

 

그래프의 종류

무향그래프

• 무향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프이다. 노드 A와 노드 B가 간선으로 연결되어 있으면, A에서 B로도 이동할 수 있고 B에서 A로도 이동할 수 있다.

유향그래프

• 유향 그래프 (Directed Graph): 간선에 방향이 있는 그래프이다. 노드 A에서 노드 B로 간선이 있으면 A에서 B로 이동할 수 있지만, 반대 방향으로 간선이 없는 경우에는 B에서 A로는 이동할 수 없다.

가중치 그래프

• 가중치 그래프 (Weighted Graph): 간선에 가중치(또는 비용)가 부여된 그래프이다. 가중치는 간선의 비용, 길이, 시간 등을 나타낼 수 있다. 최단 경로 문제, 최소 비용 문제 등에 활용한다.
• 비가중치 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프이다.

위키백과-연결그래프

• 연결 그래프 (Connected Graph): 임의의 서로 다른 두 꼭짓점이 연결된 그래프이다. 즉, 연결되어 있지 않은 외딴 노드가 없는 그래프를 말한다.
• 비연결 그래프 (Disconnected Graph): 연결되지 않은 그래프이다. 즉, 하나 이상의 노드 쌍 사이에 경로가 존재하지 않는 그래프를 말한다.

다중 그래프

• 단순 그래프 (Single Graph): 그래프에서 두 정점 사이에 오직 하나의 변이 있는 그래프이다.
• 다중 그래프 (Multi Graph): 그래프에서 두 정점 사이에 두 개 이상의 변이 있는 그래프이다.

4차 완전 그래프: 차수가 4이므로 4차이다

• 완전 그래프: 무향 그래프의 모든 정점의 쌍 사이에 간선이 존재하는 그래프이다. 즉, 각 꼭지점이 다른 모든 꼭지점들과 연결되는 그래프를 말한다. n개의 정점을 갖는 완전 그래프 K는 n(n-1)/2 개의 간선을 갖는다.

3차 정규 그래프

• 정규 그래프: 모든 정점의 차수가 같은 그래프이다. 모든 꼭지점의 차수가 k인 그래프를 k차 정규그래프라고 한다.

이 외에도 다양한 그래프들이 존재한다.

 

그래프의 표현

---

• 인접 행렬 (adjancy matrix)을 이용한 방법

인접 행렬

• 그래프의 연결 관계를 2차원 배열로 나타내는 방법이다.
• 만약 가중치가 있는 그래프라면 인접 행렬의 값에 1 대신에 가중치의 값을 직접 넣어주면 된다.
• 무향 그래프에 대한 인접 행렬은 대칭 행렬이다.
• 장점은 간선의 수가 많을수록 매우 적합하고, 정점의 번호가 주어지면 배열의 접근만으로 바로 찾을 수 있다.
• 반면에, 단점은 간선의 수가 적다면 적합하지 않고 항상 𝑂(|𝑉|2)만큼의 기억 공간을 사용한다.

 

• 인접 리스트 (linked list)를 이용한 방법

인접 리스트

• 각 정점에 대해 포인터가 주어지고, 그 점으로부터 연결된 정점들을 차례로 연결 리스트 (linked list)로 표시한다.
• 그래프를 구성하는 모든 정점에 대해 헤드 포인터를 부여하고, 연결 선이 있는 모든 정점을 헤드 포인터로부터 연결시켜 표현하는 방법이다.
• 장점은 인접 리스트는 |𝑉|개의 연결 리스트에 실제 간선의 수만큼 원소가 들어있으므로 전체 𝑂(|𝑉| + |𝐸|)의 기억 공간을 사용한다는 점이다.
• 단점은 어떤 정점을 찾을 때 처음부터 검색해야 한다는 점이다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!