Graph

V : vertex (정점)

E : edge (간선)

 

Edge Type

1. directed edge : 유향 간선
2. undirected edge : 무향 간선
3. directed graph : 유향 간선으로 이루어진 그래프
4. undirected graph : 무향 간선으로 이루어진 그래

Termiology

Incident : 간선과 정점이 붙어있는 경우 사 (정점과 간선의 관계)

Adjacent : 인접한 정점들 (정점과 정점의 관계)

Degree : 연결된 간선의 수

Parrel Edge : a - > b / b -> a와 같은 간선

Self - loop Edge : 시작과 끝이 같은 정점을 가리키는 간선

 

Property

1. deg(v)의 합은 2m이다.

-> 중복으로 두 번 세기 때문.

ex) a - b가 있다면 a - > b / b - > a 를 셀 것이다.

 

2. 무향 간선이고, self-loop가 없다면

m <= n (n - 1) / 2 를 만족한다.

Proof) 각각의 정점은 최대 n - 1개의 간선을 가질 수 있기 때문.

 

Edge List Structure

정점 객체 : 정점의 원소, 정점 sequence에서 해당 정점의 주소를 저장

간선 객체 : 간선의 원소, 두 정점, 간선 sequence에서 해당 간선의 주소를 저장

 

incident edges

O(m)이 걸린다.

 

is adjacent to

O(m)이 걸린다.

 

insert vertex

O(1)이 걸린다.

 

insert edge

O(1)이 걸린다.

 

remove vertex

O(m)이 걸린다.

 

remove edge

O(1)이 걸린다.

 

Adjacency List Structure

Space : O(n + m)

=> 정점 원소 개수 n, 간선 개수 m이 필요하고, 추가로 deg(v)만큼의 공간이 필요하나, 이는 O(2m)이므로

결국 O(n + 3m) = O(n + m)의 공간이 필요하다.

 

incident edges

O(deg(v))만큼의 시간이 걸린다.

 

is adjacent to

O(max(deg(v), dev(w))) 의 시간이 걸린다.

만약 degree의 정도를 저장했다면, O(min(deg(v), deg(w)))의 시간이 걸린다.

저장하지 않았더라도 정점을 하나씩 번갈아가며 확인하면 2 * O(min(deg(v), deg(w)))의 시간이 걸리는데,

이는 v 한 번, w 한 번 확인하면 되기 때문이다.

 

insert vertex

O(1) 이 걸린다.

 

insert edge

만약 u - w를 잇는 간선 c가 추가된다면

u의 연결 간선도 하나 추가, w도 하나 추가하므로

O(1)이 걸린다.

 

remove vertex

O(deg(v))의 시간이 걸린다.

 

remove edge

O(1)이 걸린다.

 

Adjacency Matrix Structure

Space : O(n^2)

=> O(n + m) 과 추가로 2차원 배열에 정보를 저장하므로 정점의 개수^2 만큼의 배열 크기가 필요하다.

즉, O(n + m) + O(n^2)이지만, m <= n (n - 1) / 2 이므로 

O(n^2)이다.

 

incident edges

v의 index를 확인하고, 배열에서 해당 index의 행을 찾으면 되므로 O(n)이 걸린다.

 

is adjacent to

배열에 저장되어 있으므로 O(1)의 시간이 걸린다.

 

insert vertex

만약 정점 w를 추가하려면,

배열의 크기도 늘려주어야하므로 O(n^2)이 걸리게 된다.

 

insert edge

만약 u - w를 잇는 간선 c가 추가된다면

배열[u의 index][w의 index]에 값을 추가해주면 되므로 O(1)이 걸린다.

 

remove vertex

정점 v를 삭제하려면

마찬가지로 배열의 크기도 줄여주어야하므로 O(n^2)이 걸리게 된다.

 

remove edge

마찬가지로 배열[u의 index][w의 index]에 값을 삭해주면 되므로 O(1)이 걸린다.