[알고리즘] 그래프(1) - 설명

그래프는 네트워크 모델을 추상화한 것이다. 네크워크 모델의 예로는 지하철노선도, SNS등을 예로 들 수 있다.

그래프는 (V, E) 쌍이다. V는 정점(vertex)라 불리는 노드의 집합이고, E는 간선(edge)라 불리는 정점 쌍들의 집합이다

각 정점과 간선은 원소, 즉 정보를 저장한다

그래프는 위와같이 표현될 수 있다

간선의 종류에는 방향간선과 무방향간선이 있다

방향간선은 (u, v)로 표현되며, 두 정점중 첫 정점은 시점(origin), 두번째 정점은 종점(destination)을 나타낸다. (Ex 항공편)

무방향간선은 무순 쌍(u, v)로 표현된다. (Ex 도시간의 거리)

그래프 용어

간선의 끝점 : 간선의 양쪽 끝에 있는 두 개의 정점들

정점의 부착간선 : 정점에 연결된 간선들

정점의 차수 : 정점에 연결된 간선의 수

인접정점 : 간선 한 개를 두고 이웃한 정점

병렬간선 : 양끝점을 공유하는 두개 이상의 간선

루프 : 양끝점이 동일한 간선

경로 : 정점과 간선의 교대열 (Ex P1 - V b X h Z / P2 - U c W e X g Y f W d V)

단순경로 : 모든 정점과 간선이 유일한 경로 P1은 단순경로이지만, P2는 W를 한번더 거치기때문에 단순경로가 아니다

사이클 : 정점과 간선이 교대하는 원형 열

단순사이클 : 모든 정점과 간선이 유일한 사이클

일반적으로 그래프의 정점 수를 n, 간선 수를 m, 정점v의 차수를 deg(v)로 표기한다

그래프는 두가지의 속성을 가진다

1. 그래프 내 모든 정점의 차수의 합은 간선 수의 2배다 - 차수 계산에서 그래프 내 각 간선이 두 번씩 세어지기 때문

2. 루프와 병렬간선이 없는 무방향그래프에서, 그래프 내 간선 수 m의 상한은 n(n-1)/2다 - 각 정점의 최대 차수는 n-1이기 때문

그래프ADT메소드(방향그래프, 무방향그래프 모두포함)

1. 일반메소드

- integer numVertices() : 그래프 내 정점 수를 반환

- integer numEdges() : 그래프 내 간선 수를 반환

- iterator vertices() : 그래프 내 모든 정점을 반환

- iterator edges() : 그래프 내 모든 간선을 반환

2. 접근 메소드

- vertex aVertex() : 그래프 내 아무 한 정점을 반환

3. 질의 메소드

- boolean isDirected(e) : 간선e가 방향간선인지 여부를 반환

4. 반복 메소드

- iterator directedEdges() : 그래프 내 모든 방향간선을 반환

- iterator undirectedEdges() : 그래프 내 모든 무방향간선을 반환

5. 갱신 메소드

- vertex insertVertex(o) : 항목o를 저장한(고립된) 새 정점을 삽입하고 반환

- removeVertex(v) : 정점v와 v의 부착간선을 모두 삭제

- removeEdge(e) : 간선e를 삭제

무방향그래프ADT메소드

1. 접근 메소드

- integer deg(v) : 정점v의 차수를 반환

- vertex opposite(v, e) : 정점v의 간선e에 대한 반대쪽 끝점을 반환

2. 질의 메소드

- boolean areAdjacent(v, w) : 정점v와 w가 인접한지 여부를 반환

3. 반복 메소드

- iterator endVertices(e) : 간선e의 양끝 정점들을 반환

- iterator adjacentVertices(v) : 정점v의 인접정점을 모두 반환

- iterator incidentEdges(v) : 정점v의 부착간선을 모두 반환

4. 갱신 메소드

- edge insertEdge(v, w, o) : 정점v와 w사이에 항목 o를 저장한 무방향간선을 삽입하고 반환

방향그래프ADT메소드

1. 접근 메소드

- vertex origin(e) : 간선e의 시점을 반환

- vertex destination(e) : 간선e의 종점을 반환

- integer inDegree(v) : 정점v의 진입차수를 반환

- integer outDegree(v) : 정점v의 진출차수를 반환

2. 반복 메소드

- iterator inIncidentEdges(v) : 정점v의 진입 부착간선을 모두 반환

- iterator outIncidentEdges(v) : 정점v의 진출 부착간선을 모두 반환

- iterator inAdjacentVertices(v) : 정점v의 진입 인접간선을 모두 반환

- iterator outAdjacentVertices(v) : 정점v의 진출 인접간선을 모두 반환

3. 갱신 메소드

- edge insertDirectedEdge(v, w, o) : 정점 v에서 w로 항목o를 저장한 방향간선을 삽입하고 반환

- makeUndirected(e) : 간선e를 무방향으로 전환

- removeDirection(e) : 방향간선e를 역행

그래프를 구현하기 위한 방법으로는 인접리스트 구조와, 인접행렬 구조를 연결리스트와 배열 구현이 가능하다

그래프ADT 상세 구현 비교

		인접리스트	인접행렬
연결리스트	정점리스트, 간선리스트	동적메모리의 노드의 연결리스트
	정점, 간선	동적메모리 노드
	인접 정보	포인터의 연결리스트	2D포인터배열
	장점	동적그래프에 사용 시 유리
	단점	다수의 포인터 사용으로 복잡
배열	정점리스트, 간선리스트	구조체배열
	정점, 간선	구조체
	인접 정보	첨자의 연결리스트	2D 첨자 배열
	장점	다수의 포인터를 첨자로 대체하여 단순
	단점	동적 그래프에 사용시 불리

그래프ADT 구현 방식에 따른 점근적 성능 비교

구현방식	간선리스트	인접리스트	인접행렬
기억장소 사용량	n+m	n+m	n^2
deg(v)	m	degree of v	n
opposite(v, e)	m	1	1
areAdjacent(v, w)	m	min(deg(v), deg(w))	1
adjacentVertices(v)	m	deg(v)	n
incidentEdges(v)	m	deg(v)	n
insertVertex(o)	1	1	n
insertEdge(v, w, o)	1	1	1
removeVertex(v)	m	deg(v)	n
removeEdge(e)	1	1	1

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사