그래프(Graphs)
그래프는 (Vertex, Edge)로 이루어진 쌍이다.
- V는 정점이라고 하는 노드 집합이다. (Vertex 라고 부름)
- E는 정점 쌍들의 집합으로, Edge(간선)라고 부른다.
- 정점과 간선은 위치 및 저장 요소이다.
Edge Types(간선 종류)
1. Directed Edge
- 순서 있는 정점 쌍 (u,v) [ (u,v)와 (v,u)는 다름. 방향성이 존재하기 때문 ]
- 첫번째 정점 u는 원점이다.
- 두번째 정점 v는 목적지이다.
2. Undirected Edge
- 순서 없는 정점 쌍 (u,v) [ (u,v)와 (v,u(는 같음. 방향성이 존재하지 않기 때문]
3. Directed Graph
- 모든 간선이 directed인 경우.
4. Undirected Graph
- 모든 간선이 Undirected인 경우.
그래프 응용 프로그램에는 전류 순환(집적 회로) , 운송 네트워크(고속도로) , 컴퓨터 네트워크(인터넷) , 데이터베이스(ERD)등이 있다.
Terminology
끝 정점(end vertex or endpoints) - U와 V는 a의 끝 정점이다.
Incident - a,d,b는 V에 대해 incident 하다. ( 간선과 vertex가 붙어있을 때)
adjacent - U와 V는 adjacent 하다. ( 하나의 엣지로 연결되었을 때)
Degree(차수) - X의 Degree는 5이다. incident한 간선의 수를 세면 됨.
Parallel edges - h와 i는 parallel edge이다.
self-loop - j는 self loop.
Path - 교차하는 정점과 간선의 순서. 시작 vertex와 끝 vertex로 이루어진다.
Simple Path - 모든 정점과 간선이 구별되는 경로. 즉, 중복되는 vertex가 없는 경우를 말한다.
Ex. P1 = (V,b,X,h,Z)는 simple Path이다.
P2 = (U,c,W,e,X,g,Y,f,W,d,V)는 simple Path가 아니다.
Cycle - 정점과 간선이 교차하는 원형 시퀀스이다. 즉, 시작 vertex로 다시 돌아오는 것을 말한다.
Simple Cycle - 모든 정점과 간선이 중복되지 않도록 순환한다.
Ex. C1 = (V,b,X,g,Y,f,W,c,U,a,V)는 simple cycle이다.
C2 = (U,c,W,e,X,g,Y,f,W,d,V,a,U)는 simple cycle이 아니다.
그래프의 속성
n = 정점의 수
m = 간선의 수
deg(v) = 정점 v의 차수
1. 모든 정점의 차수의 합은 2m이다. ( 각 간선은 두번씩 count 되기 때문이다. )
2. 방향성이 없고(undirected) self-loop가 존재하지 않고, Parallel edge가 없는 그래프에서 m<= n(n-1)/2 이다. (각 정점은 최대 (n-1)의 차수를 가지기 때문이다.
Graph ADT
Vertex & edge - 위치 정보와 요소를 저장한다.
Accessor methods
e.endVertices() - 양 끝 정점 2개를 리턴한다.
e.opposite(v) - 반대편 정점을 찾는데 사용한다.
u.isAdjacentTo(v) - u와 v가 adjacent라면 true를 리턴한다.
*v - 정점 v와 관련된 element를 참조한다.
*e - 간선 e와 관련된 element를 참조한다.
Update methods ( 지우는 기능이 어렵다. )
insertVertex(o) - 정점 저장 요소 o를 삽입한다.
insertEdge(v,w,o) - 간선(v,w) 저장 요소 o를 삽입한다.
eraseVertex(v) - 정점 v(그리고 정점과 incident한 간선)을 제거한다.
eraseEdge(e) - 간선 e를 제거한다.
Iterable Collection methods
v.incidentEdges() - v와 연결된 간선을 모두 리턴한다.
vertices() - 그래프에 모든 정점 목록을 리턴한다.
edges() - 그래프에 모든 간선을 리턴한다.
Edge List Structure
정점 객체
- element
- 정점 시퀀스의 위치를 참조
간선 객체
- element
- 시작 정점 객체
- 도착 정점 객체
- 간선 시퀀스의 위치를 참조
정점 시퀀스
- 정점 객체의 시퀀스
간선 시퀀스
- 간선 객체의 시퀀스
Adjacency List Structure(인접 리스트 구조)
- 간선 리스트 구조
- 각 정점에 대한 Incidence Sequence가 추가됨. (벡터를 많이 사용함)
- 인접한 간선에 대한 간선 객체를 참조하는 시퀀스
- Augmented Edge objects
- 끝 정점의 incidence sequence의 위치를 참조한다.
Adjacency Matrix Structure(인접 행렬 구조)
- 간선 리스트 구조
- Augmented vertex object
- 정점과 연관된 정수 키(인덱스)
- 2D 배열 인접 배열
- 인접 정점에 대한 간선 객체 참조
- 인접하지 않은 정점의 경우 NULL 값
- old fashioned 버전의 경우 간선이 없으면 0 간선이 있으면 1. (요즘 버전에서는 주솟값을 저장)
Performance(성능)
