Graph Abstract Data Type ( 그래프 추상 데이터 타입 )
(1) 개요
- 차수(degree) : 정점에 연결된 간선의 수
- 오일러 행로(walk) : 각 정점의 차수가 짝수인 경우에 한해 각 간선을 한번씩 거쳐 출발한
정점으로 되돌아 올 수 있음
(2) 정의
✦ 그래프 G=(V,E)
V: 정점 (set of vertices), 공집합이 아닌 V의 유한집합
E : 간선 (set of edges), 정점을 연결하는 선, 선 V*V의 부분집합
(+) 그래프의 제약 사항
ㄱ. 임의의 정점 v에서 자기 자신으로 이어지는 간선을 가질 수 없음
(u,u) , <u,u>, self-edge, self-loop X
ㄴ. 같은 간선 중복 X (not multigraph)
(+) 그래프는 트리가 될 수 있다.
< 관련 용어 >
✦ 무방향 그래프 (undirected graph) :
간선을 나타내는 정점의 쌍에 순서가 없음. 쌍 (u,v)와 (v,u)는 동일한 간선 표현
✦ 방향 그래프 (directed graph, digraph) :
간선을 나타내는 정점의 쌍에 순서가 있음. <u,v> 로 표현.
이 때, u는꼬리(tail)이고, v는 머리(head)이라고 함
✦ 완전 그래프(complete graph) :
- n개의 정점을 가진 그래프에서 uv인 서로 다른 무순서(undirected) 정점 쌍(u,v)의 수는
n(n-1)2이다.
- n개의 정점과 n(n-1)2개의 간선을 갖는 그래프를 완전 그래프라고 한다.
✦ 인접(adjacent to) :
(u,v)가 E(G)의 한 간선인 경우 → 즉, 정점 u, v에 대해 간선(u,v)가 있을 때 ‘인접’
✦ 부분 그래프(subgraph) :
V(G')V(G) and E(G')E(G)인 그래프 G'을 그래프 G의 부분 그래프라고 한다.
✦ 경로(path) :
- 정점 Vp에서 정점 Vq로 가는 간선들의 나열
- (무방향) 그래프 G에서 (u,i1),(i1,i2), ... ,(ik,v)를 E(G)에 속한 간선들이라 할 때,
정점 u로부터 정점 v까지의 경로는 정점 순서 u,i1,i2, ... ,ik,v 를 말한다.
- 위의 그래프 G가 방향 그래프라면, 경로는 E(G’)에 속한
간선 <u,i1>,<i1,i2>, ... ,<ik,v> 로 구성된다.
(+) 경로 길이 (path length) : 경로 상의 간선의 수
✦ 단순 경로 (simple path) :
- 처음과 마지막을 제외한 모든 정점들이 서로 다른 경로
- 경로 상의 정점이 중복되지 않는 경로
✦ 사이클 (cycle) : 처음과 마지막 정점이 같은 단순 경로 (방향 그래프의 경우, directed cycle)
✦ 연결(connected) : 정점 u 부터 정점 v까지의 경로가 존재하는 경우, 정점 u와 v는 연결
(무방향 그래프의 경우, u,v가 연결이면, v,u도 연결)
✦ 연결 요소(connected component) = 최대 연결 부분 그래프(maximal connected subgraph)
- 그림에서 H는 연결요소.
- 최대라는 말은 연결되어 있으면서, H를 포함하는 또다른 부분 그래프가 G에는 존재하지
않는다는 것을 의미.
✦ 트리(tree) : 사이클 없는(acycle) 연결 그래프
✦ 강력 연결(strongly connected) :
- 방향그래프 V(G)에 속한 서로 다른 두 정점 u,v의 모든 쌍에에 대하여, u에서 v로, v에서 u로의
방향 경로가 존재하는 경우, 강력 연결되었다고 한다.
(+) 강력 연결 요소 (strongly connected component) : 강하게 연결된 최대 부분 그래프
✦ 차수(degree) : 정점에 속한 간선들의 수
- in-degree ( of vertex v) (진입 차수) : 임의의 정점 v가 머리(head)가 되는 간선의 수
(정점으로 들어오는 간선의 수)
- out-degree ( of vertex v) (진출 차수) : 임의의 정점 v가 꼬리(tail)가 되는 간선의 수
(정점으로부터 나가는 간선의 수)
(3) 그래프 표현법인접행렬 (adjacent matrix)
- 그래프 G=(V,E), |V| 1, G의 인접행렬 nn은 2차원 ‘배열’
- 간선 (i,j) 또는 <i,j>가 E(G)에 속하면, a[i][j]=1 (속하지않으면 0)
- 인접 행렬 표현 공간 : n2
(참고) 무방향 그래프는 (j,i) = (i,j) → 행렬의 상위 삼각 또는 하위 삼각만 저장해도 됨
⇒ 표현 공간의 절반 가량을 절약 할 수 있음
- 인접 행렬을 이용하여 임의 정점 i, j에 대해 연결 간선이 존재하는지 확인 할 수 있음
(참고로, 방향 그래프에서 행의 합은 out-degree, 열의 합은 in-degree)
- 그래프 G의 간선 수 파악(또는 연결 여부 파악) : 최소 O(n2)
sparse graph의 경우에는 O(e+n)내에 수행 가능 : e ~ 간선 수, n ~ 행렬 행
e << n 2/2인접리스트 (adjacency list)
- 각 정점에서 속한 간선들은 연결 리스트로 저장
- n개의 정점과 e개의 간선을 갖는
… 무방향 그래프 ⇒ n개의 배열과, 2e개의 체인 노드 필요
- 필요한 공간의 비트수 구하기 위해
배열 : log n, 체인 노드 : log n + log e
순차 리스트 … 정수배열 node[n+2e+1]에 저장
각 정점의 차수는 그 정점에 대한 인접 리스트에 있는 노드의 수를 계산
… 방향 그래프 ⇒ 리스트의 노드 수는 e개
- out-degree 구하기는 쉬우나 in-degree 구하기가 복잡
다른 정점에 인접한 모든 정점들을 자주 찾아야 할 필요가 있을 경우
→ 역인접리스트(inverse adjacency list) : 각 정점마다 하나의 리스트 있음다중리스트 (adjacency multilist) PASS
(+) 가중치 간선 (weight edge)
~ 가중치 간선을 갖는 그래프 : 네트워크 (Network)Elementary Graph Operations (그래프 기본 연산)
- 탐색 (또는 순회) : G(V,E)와 V(G)의 한 정점 V가 주어졌을 때, V에 연결된 모든 정점을 방문
⇒ DFS, BFS 모두 방향/무방향 그래프에 적용 가능깊이 우선 탐색 (DFS, Depth First Search)
(1) 시작 정점 V을 결정하여 방문
(2) 정점 V에 인접한 노드 중에서
ㄱ. 아직 방문하지 않은 노드 W가 존재하는 경우, (V를 Push하고) W 방문하고
W를 V로 설정한 뒤 깊이-우선탐색 다시 시작
ㄴ. 방문 하지 않은 정점이 존재하지 않는 경우, (Pop하여) 가장 마지막 방문 지점을 V로
설정한 뒤 깊이-우선탐색 다시 시작
(3) 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료
(예) 깊이 우선탐색 ~ DFS(0) : 0,1,3,7,4,5,2,6 순으로 방문
< DFS 수행에 따른 스택 변화 >
너비 우선 탐색 (BFS, Breadth First Search)
(1) 시작 정점 V를 결정하여 방문
(2) 정점 V에 인접한 정점들 중에서 방문하지 않은 정점을 차례로 방문하면서
큐에 enQueue함
(3) 방문하지않은 인접한 정점이 없으면 방문했던 정점에서 인접한 정점들을 다시
차례로 방문하기위해 큐에서 deQueue하여 (2)를 방문
(4) 큐가 공백이 될 때 까지 (2)~(3)을 반복
(예) 너비 우선탐색 ~ BFS(0) : 0,1,2,3,4,5,6,7 순으로 방문
<BFS 수행에 따른 큐 변화>Connected Component (결합 요소)
Spanning Tree (신장트리)
- G의 간선들로만 구성되고 G의 모든 정점이 포함된 트리
- 그래프 G가 연결 ... 임의의 정점에서 출발한 DFS 또는 BFS는 G의 모든 정점들을 방문
==> 그래프 G의 간선들을 두개의 집합 T와 N으로 분할
- T(Tree edge) : 탐색 중 사용된 간선
- N(Nontree edge) : 탐색 중 사용되지 않은 간선
- DFS/ BFS를 이용하여 신장트리 만들 수 있음.
(신장트리 예)(예)
- DFS(0) 에 따른 신장 트리
- BFS(0) 에 따른 신장 트리Biconnected Component (이중결합요소)
Minimum Cost Spanning Trees (최소 비용 신장 트리)
(참고) 비용(cost) : (weighted undirected graph에서) 신장트리의 간선들 비용의 합
- 가중치 그래프 상에서 최저의 비용을 갖는 신장트리
- 최소 비용 신장트리 알고리즘 … 모두 greedy method
(1) Kruskal (2) Prim (3) Sollin
→ 가능한 해는 다음 제한 조건을 만족
ㄱ. 그래프 내의 간선들만 사용
ㄴ. 정확하게 n-1 개의 간선만 사용
ㄷ. 사이클을 생성하는 간선 사용 금지Kruskal 알고리즘
=> 전체 간선중에 저비용 간선들로만
- 한 번에 하나씩 T에 간선을 추가하며 최소 비용 신장 트리 구축
- T에 포함될 간선을 비용의 크기 순으로(저비용순으로) 선택
- 각 단계에서 선택된 간선의 집합(T) ... 포레스트
[과정]
(1) 그래프 G의 모든 간선을 가중치에 따라 오름차순 정리
(2) 그래프 G에서 가중치가 가장 작은 간선 삽입. (사이클 형성하는 간선은 제외)
(3) 그래프 G에 n-1개의 간선을 삽입할 때까지 (2) 반복
(4) 그래프 G의 간선이 n-1개가 되면 완성Prim 알고리즘
=> 시작하는 v에서 저비용 간선들로만!
- 한번의 하나의 간선 (kruskal과 동일)
- 그러나, 알고리즘의 각 단계에서 선택된 간선의 집합(T)은 트리를 이룸
( kruskal 은 각 단계에서 선택된 간선의 집합(T) ... 포레스트 )
[과정]
(1) 하나의 정점으로 된 트리 T에서 시작
(2) 최소 비용 간선 (u,v)를 구하여 T{(u,v)}이 트리가 되면 T에 추가
(3) T에 n-1개의 간선이 포함될 때까지 (2) 반복
(4) 추가된 간선이 사이클을 형성하지 않도록, 각 단계에서 (u,v)를 선택할 때,
u 또는 v 중 하나만 T에 속한 것을 선택Sollin 알고리즘 - 각 단계에서 여러 개의 간선 선택 - 한 단계의 시작점에서 선택된 간선들 → n개의 모든 그래프 정점들을 포함한 신장 리스트 [과정] (1) 각 단계에서 포레스트에 있는 각 트리에 대해 하나의 간선을 선택. 이 간선은 오직 하나의 정점만, 그 트리에 속한 최소 비용 간선 (2) 선택된 간선은 구축중인 신장트리에 추가 (3) 오직 하나의 트리만이 존재하거나 더이상 선택할 간선이 없을 때 끝
(7번..ㅠㅠ)
Shortest Paths and Transitive Closure
(용어)
source (시작점/시발점) : 경로의 시작 정점
destination (종점) : 경로의 마지막 정점단일 시작점/모든 종점 : 음이 아닌 간선 비용 ( Single src/ All dest : nonnegative edge costs)
⇒ Dijkstra Algorithm (다익스트라 알고리즘) / 양수 간선비용 알고리즘
[가정]
(1) 정점 v을 포함하여 이미 최단 경로가 발견된 정점의 집합 : S
(2) S에 속하지 않은 w에 대해서 dist[w]는 v 에서 시작하여 S에 있는 정점만을 거쳐
w까지 도달한 최단 경로의 길이
[알고리즘]
(1) 만일 다음 최단 경로가 정점 u까지의 경로라면, v에서 u로의 경로는 오직 S에 속한
정점들만을 지나게 됨
(2) 다음에 생성되는 경로의 종점은 S에 없는 정점들 중에서 최소의 거리 dist[u]를
가진 정점u가 되어야 함
(3) 일단 (2)에서 선택된 정점 u는 S의 원소가 되고, v에서 u로의 최단 경로는 (2)의 선택
과정을 통해서 얻을 수 있다. 이 때, v에서 시작하여 S에 있는 정점만을 통해 현재 S에
속하지 않은 w까지의 최단 경로의 길이는 작아질 수도 있음.단일 시작점/모든 종점 : 일반적인 간선 비용 ( Single src/ All dest : General Weights)
- Dijkstra의 문제점 : 음수 길이 사이클이 존재할 경우 최단 길이 경로가 존재하지 않음.
- 동적 프로그래밍 방법
> 모든 (v와 연결된) u에 대해 distancen-1[u]을 구함
> distancek[u] = min{ distancek-1[u], mini{distancek-1[i] + length[i][u]}}
> v → u 경로가 최대 k개의 간선 포함가능하고, 최단 경로는 k-1개의 포함한다면
⇒ distancek[u] = distancek-1[u]
> v → u 경로가 최대 k개의 간선 포함가능하고, 최단 경로는 k개의 포함한다면
⇒ v → j + <j,u>
… v → j까지의 최단 경로는 k-1개의 간선 포함 → distancek-1[u]
… 그래프에 존재하는 모든 정점 i는 j의 후보
(참고) 위의 표에서 k는 홉(hop).
*** Bellman-Ford 알고리즘
void BellmanFord(int n, int v)
{
for ( int i = 0 ; i < n ; i++ ) dist[i] = length[v][i];
for ( int k = 2; k <= n-1 ; k++)
for (each u such that u!=v and has at least one incoming edge)
for(each < i , u > in the graph)
if(dist[u] > dist[i] + length[i][u])
dist[u] = dist[i] + length[i][u];
}모든 쌍의 최단 경로 (All Pairs Shortest Paths)
- uv인 모든 정점의 쌍 u와 v 간의 최단 경로 구하는 것
- Ak[i][j] = min {Ak[i][j], Ak-1[i][k] + Ak-1[k][j]} , k0
- A-1[i][j] = length[i][j]
*** cycle 허용, 효율 최저
*** Floyd 알고리즘
void allCosts
(int cost[][MAX_VERTICES], int distance[][MAX_VERTICES], int n)
{
int i, j, k;
for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )
distance[i][j] = length[i][j];
for ( k = 0 ; k < n ; k++ )
for ( i = 0; i < n ; i++)
for ( j = 0 ; j < n ; j++)
if(distance[i][k] +distance[k][j] < distance [i][j])
distance[i][j] = distance[k][j] + distance [i][j];
}Transitive Closure (이행적 폐쇄)
- 가중치가 부여되지 않은 방향 그래프 G에서, i와 j의 모든 값에 대해 i부터 j까지의 경로가 존재하는지 결정해야할 때,
⇒ 이행적 폐쇄 (Transitive closure) : 양의 경로 길이
⇒ 반사 이행적 폐쇄 (Relative Transitive closure) : 음이 아닌 경로 길이이행적 폐쇄 행렬 (A+)
- 방향 그래프 G에서 i 에서 j 까지의 경로 길이가 0보다 클 때 A+[i][j]=1이 되는 행렬
- 그렇지 않으면, A+[i][j]=0반사 이행적 폐쇄 행렬 (A*)
- 방향 그래프 G에서 i 에서 j 까지의 경로 길이가 0이거나 0보다 클 때 A+[i][j]=1이 되는 행렬
- 그렇지 않으면, A*[i][j]=0Activity Networks
AOV 네트워크 (Activity On Vertex network)
- [선행자/후속자]
i → j (경로)가 존재할 때, i 는 j 의 선행자 (predecessor) / j 는 i 의 후속자(successor)
- [직속선행자/직속후속자]
<i, j> 가 존재할 때, i 는 j 의 직속 선행자 (immediate predecessor)
/ j 는 i 의 직속 후속자(immdiate predecessor)
- [이행적]
모든 세 쌍 i,j,k에 대해 i·j 이고 j·k ⇒ i·k 가 성립하면, 관계 ·는 이행적(transitive)
- [비반사적]
- [부분 순서]
* topological orderAOE 네트워크 (Activity On Edge network)
- [최장경로] [임계경로] [가장 이른 시간] [가장 이른 시작 시간] [가장 늦은 시간] [임계작업]
이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.
'Computers > Data Structure' 카테고리의 다른 글
| Chapter 8. Hashing (0) | 2013.10.10 |
|---|---|
| Chapter 7. Sorting (0) | 2013.10.10 |
| Chapter 5. Trees (0) | 2013.10.10 |
| Chapter 4. Linked Lists (0) | 2013.10.10 |
| Chapter 3. Stack and Queue (0) | 2013.10.10 |