자료 구조 그래프

그래프란?

그래프는 정점과 간선으로 구성하는 자료구조를 뜻한다.

그래프의 예시

 

그래프와 관련된 용어 정리

정점 (Vertex)  : 

Node라는 용어를 사용하기도 한다.

위 사진에서 숫자가 있는 동그라미 즉, 각 지점을 의미한다.

 

간선 (Edge or Link) :

보통 Edge라고 한다.

두 정점끼리의 연결된 선을 의미한다.

화살표 표시가 된 선도 있고, 없는 것도 있는데, 둘 다 간선이다.

 

가중치 :

간선 위에 표시된 숫자이다.

보통 간선을 타고 이동할 때, 얼마나 중요한지 순서를 나타냈다고 보면 된다.

비용 같은 것들을 예시로 들 수 있다.

가중치가 없는 그래프들은 모두 가중치가 동일한 그래프이다.

 

Directed Graph (유향 그래프) :

위 사진에서 오른쪽 그래프처럼 간선에 방향성이 있는 그래프이다.

 

Undirected Graph (무향 그래프) :

위 사진에서 왼쪽 그래프처럼 화살표가 없는 그래프이다.

화살표가 없다는 것은 이동을 하지 못하는 것이 아니라 '양방향 이동 가능'을 뜻한다.

 

Self-Loops :

 한 정점에서 다시 그 정점으로 바로 돌아오는 간선을 의미한다.

(ex. (v1,v1) . 여기서 v1은 정점이다.)

 

Adjacency (인접) : 

Directed Graph (유향 그래프)에서 간선으로 연결된 인접 정점을 뜻한다.

(ex. 위 사진에서 정점 2는 정점1에 인접하다고 할 수 있다.)

 

Degree (차수) : 

정점에 연결 되어 있는 간선의 수라고 생각하면 된다.

 

유향 그래프에서는 외차수와 내차수로 나누어 진다.

외차수는 나가는 간선, 내차수는 들어오는 간선이다.

(ex. 위 사진에서 정점 2는 외차수가 3이고, 내차수가 2이다.)

 

무향 그래프에서는 외차수와 내차수로 나누지 않고, 그냥 차수라고 표현한다.

(ex. 위 사진에서 정점 4는 차수가 4이다.)

 

Path (경로) :

한 정점에서 다른 정점으로까지 이동할 수 있는 경로를 의미한다.

두 정점 사이의 경로는 하나만 있는 게 아니라, 여러 가지가 존재가능하다.

(ex. 위 유향그래프에서 정점 2에서 정점 5로 바로 가는 경로가 있으나, 4를 거쳤다가 가는 경로도 존재한다.)

 

Simple Path (고유 경로) :

경로이지만, 경로를 이루는 정점들이 모두 다른 경우를 의미한다.

(ex. <2,4,5>는 고유 경로이다.)

 

Cycle (순환) : 

한 정점에서 출발하여서 간선을 타고 이동하면 다시 동일한 정점으로 돌아올 수 있는 경로를 의미한다.

(ex. <2,4,5,2>는 순환이다.)

 

An acyclic graph (비순환 그래프) :

그래프에 Cycle(순환)이 없는 경우를 의미한다.

 

Connected Graph (연결 그래프) : 

무향 그래프이며, 모든 쌍의 정점들이 경로로 연결이 가능한 그래프이다.

 

Forest (숲) : 

그래프 중에서 순환이 없고, 방향성이 없으면 숲이라고 한다.

서로 연결되지 않은 트리들의 집합

 

Tree (트리) : 

숲 중에서 연결 그래프의 속성을 만족하면 된다.

 

Dag : 

Tree에서 방향성의 속성이 생긴 것. 순환이 없는 그래프.

 

그래프의 종류

 

1. 유향 그래프 vs 무향 그래프

설명 생략

 

2. 가중치 그래프

간선에 가중치가 할당된 그래프

 

3. 사이클 그래프 vs 비순환 그래프

Cycle (순환) 의 유무에 따른 그래프

 

4. 완전 그래프

 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프

 

5. 연결 그래프 vs 비연결 그래프

모든 정점들이 다 연결되어 있으면 연결 그래프, 하나의 정점이라도 연결되지 않으면 비연결 그래프

 

6. 신장 트리와 최소 신장 트리 (Spanning Tree)

신장 트리 : 그래프의 모든 정점이 연결되면서, 트리의 속성을 만족하는 그래프 (순환 x, 방향성 x)

최소 신장 트리 :  간선의 가중치 합이 최소인 신장 트리

신장 트리는 여러 종류가 있을 수 있다.

 

그래프의 구현 방법

1.인접 리스트

각 정점에 대한 N개의 배열을 만들고, 각 정점과 인정한 노드를 할당된 각 배열에 저장한다.

 

장점:

정점들의 연결 정보를 탐색할 때 O(N)시간이면 가능하다.

필요한 만큼의 공간만 사용하기 때문에 공간 사용 적음

 

단점 : 

특정 두 점이 연결되어있는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다. O(간선의 개수) 시간 소

구현이 어려움

2. 인접 행렬

N개의 정점이 있다면 모든 정점들의 정보를 N^2의 배열에다가 넣는 것이다.

정점간 연결이 되어있다면 1을 집어 넣고, 아니면 0을 집어넣는다.

 

장점 :

두 정점에 대한 연결 정보를 조회할 때 O(1)의 시간복잡도면 가능하다.

구현이 쉽다.

 

단점 : 

대입할 때 O(N^2)의 시간복잡도가 소요된다.

2차원 배열로 인한 공간이 매우 낭비된다.