Graphs

개요

그래프는 (V, E) 쌍으로 나타낸다.

 

V는 Vertices로 정점의 set을, E는 Edges로 간선의 collection을 의미한다.

 

둘 모두 position ADT로, 임의의 원소를 저장할 수 있다.

 

 

Edge의 종류

• Directed edge: 순서가 있는 정점 (u, v) 쌍. 각각 origin, destination이라고 한다.
  • Directed graph: 모든 간선이 directed인 그래프
• Undirected edge: 순서가 없는 정점 (u, v) 쌍.
  • Undirected graph: 모든 간선이 undirected인 그래프

 

용어 정리

• endpoints: 어떤 간선에 대해 양 끝에 연결된 두 정점.
• adjacent vertices: 간선으로 직접 연결된 두 정점.
• incident: 어떤 정점과 연결된 모든 간선.
• degree of a vertex: 어떤 정점에 대해 연결된 간선의 수.
• parallel edges: 같은 endpoints를 갖는 간선들.
• self-loop: endpoints가 같은 정점인 간선.
• path
• cycle

 

Path

정점, 간선, ..., 정점의 sequence.

 

모든 간선은 endpoints로 연결되어 있다.

 

Simple path: 같은 정점이나 간선을 두 번 이상 포함하지 않는 path

 

 

Cycle

Circular path로 정리할 수 있다.

 

Simple cycle: 첫 정점을 제외한 같은 정점이나 간선을 두 번 이상 포함하지 않는 cycle.

 

 

그래프의 성질

n, m = 정점의 갯수, 간선의 개수 일 때,

 

1. 모든 정점의 degree의 합은 2m.

증명: 각 간선은 두 번 counted 된다.

 

2. Parallel, self-loop 간선이 없을 때 m ≤ n(n - 1)/2.

증명: 각 정점은 최대 (n - 1)개의 degree를 가진다.

 

 

Graph ADT

정점과 간선은 모두 원소를 담는 position이다.

 

접근 메소드

• e.endVertices(): 두 endvertices 리스트
• e.opposite(v): e의 v의 opposite인 정점
• v.isAdjacentTo(u): u와 v가 adjacent 관계이면 true, 아니면 false
• *v: vertex v의 레퍼런스
• *e: edge e의 레퍼런스

업데이트 메서드

• insertVertex(o): 원소 o를 담는 정점 삽입
• insertEdge(v, w, o): 두 정점 v, w를 잇는 원소 o를 담는 간선 삽입
• eraseVertex(v): 정점 v와 연결된 간선 모두 삭제
• eraseEdge(e=(v, w)): e = (v, w)인 간선 삭제.

Iterable collection 메서드

• neighbors(v): v에 adjacent 한 정점의 리스트
• vertices(): 그래프의 모든 정점 리스트
• edges(): 그래프의 모든 간선 리스트

 

Edge List Structure

Vertex object가 갖는 정보

• element
• reference to position in vertex sequence

Edge object가 갖는 정보

• element
• origin Vertex object
• destination Vertex object
• reference to position in edge sequence

Vertex sequence

• vertex object의 sequence

Edge sequence

• edge object의 sequence

어떤 정점에 대한 incident를 구하는 등의 메서드들이 비효율적이기 때문에 개선이 필요하다.

 

 

Adjacency List Structure (인접 리스트)

Edge List Structure를 상속

 

각 정점에 대한 Incidence sequence

• incident edges로 연결된 정점들에 대한 reference들의 sequence

Augmented edge objects

• end vertices의 incidence sequence position에 대한 reference

 

Adjacency Matrix Structure (인접 행렬)

Edge List Structure를 상속

 

Augmented vertex objects

• 정점에 관한 Integer 키 (index)

2차원 배열 adjacency array

• Adjacent 관계의 정점을 잇는 간선에 대한 reference
• 인접하지 않은 경우 Null

연결되어 있으면 1, 아니면 0으로 나타내는 버전도 있다.

 

 

퍼포먼스

전제조건: n개의 정점, m개의 간선, Parallel 및 Self-loop 간선 X

 

	Edge List (big-O)	Adjacency List (big-O)	Adjacency Matrix (big-O)
공간복잡도	n + m	n + m	n2
v.incidentEdges()	m	deg(v)	n
v.isAdjacentTo(w)	m	min(deg(v), deg(w))	1
insertVertex(o)	1	1	n2
insertEdge(v, w, o)	1	1	1
eraseVertex(v)	m	deg(v)	n2
eraseEdge(e)	1	1	1