[DS] 그래프(Graphs)의 종류와 관련 용어

그래프(Graphs)란?

객체 사이의 연결 관계를 나타낼 수 있는 자료 구조입니다.

그래프(graph)는 vertex의 집합과 edge의 집합으로 이루어집니다.

- vertex = {a, b, c, d, e}

- edge = {(a, b), (a, e), (b, c), (c, d), (c, e), (d, e)}

 

 

그래프(graph) 관련 용어(Terminology)

---

Adjacent - 두 vertex 간의 edge가 존재함

Path - 두 vertax 간에 edge로서 연결되는 vertex의 sequence

Length of a path - path를 구성하는 edge 개수

Connected - 두 vertex 간에 path가 존재함

Connected components - 연결된 원소의 그룹

Cycle - 시작과 끝이 동일 vertex인 path

 

 

 

Edge의 표기

---

Graph(= undirected graph)

방향성이 없는 edge를 가진 그래프(graph)

(a, b) = (b, a)

 

 

 

Directed graph(= digraph)

방향성을 있는 edge를 가진 그래프(graph)

<a, b> ≠ <b, a>

 

 

Strongly connected - directed graph에서 양방향 path가 존재

Degree of a vertex - 특정 vertex와 연결된 edge의 수 

indegree - directed graph에서 들어오는(incoming) edge의 수

outdegree - directed graph에서 나가는(outcoming) edge의 수

 

 

 

Graph representations

---

① 방향성이 없는 adjacency matrix

	a	b	c	d	e
a	0	1	0	0	1
b	1	0	1	0	0
c	0	1	0	1	1
d	0	0	1	0	1
e	1	0	1	1	0

방향성이 없기 때문에 표가 좌우대칭이 됩니다.

 

 

② 방향성이 있는 adjacency matrix

	a	b	c	d	e
a	0	1	0	0	0
b	0	0	1	0	0
c	0	0	0	1	0
d	0	0	0	0	1
e	1	0	0	0	0

세로(from) - 다 더하면 indegree의 개수

가로(to) - 다 더하면 outdegree의 개수

 

 

③ Adjacency lists

a	→	b	→	e
b	→	a	→	c
c	→	b	→	d	→	e
d	→	c	→	e
e	→	a	→	c	→	d

관계가 있는 원소들만 표기되고,

연결리스트(linked list)를 이용했습니다.

 

 

④ Adjacency matrix

	a	b	c	d	e
a	0	1	0	0	8
b	1	0	2	0	0
c	0	2	0	4	3
d	0	0	4	0	5
e	8	0	3	5	0

가중치(연결 강도)를 숫자로 표현하고 방향성이 없는 그래프(graph)와 같이 표기합니다.

 

 

 

◡̈