CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 62).

Presentation on theme: "CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 62)."— Presentation transcript:

1 CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 62)

2 그래프(graph) 연결되어 있는 객체 간의 관계를 표현하는 자료구조 가장 일반적인 자료구조 형태
우리가 배운 트리(tree)도 그래프의 특수한 경우임 전기회로의 소자 간 연결 상태 운영체제의 프로세스와 자원 관계 큰 프로젝트에서 작은 프로젝트 간의 우선 순위 지도에서 도시들의 연결 상태 Slide 2 (of 62)

3 그래프 역사 1800년대 오일러에 의하여 창안 오일러 문제 A,B,C,D 지역의 연결 관계 표현 오일러 정리
모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제 A,B,C,D 지역의 연결 관계 표현 위치: 정점(node) 다리: 간선(edge) 오일러 정리 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재함 따라서 그래프 (b)에는 오일러 경로가 존재하지 않음 Slide 3 (of 62)

4 그래프 정의 그래프 G는 (V, E)로 표시 정점(vertices) 간선(edge) 여러 가지 특성을 가질 수 있는 객체 의미
V(G) : 그래프 G의 정점들의 집합 노드(node)라고도 불림 간선(edge) 정점들 간의 관계 의미 E(G) : 그래프 G의 간선들의 집합 링크(link)라고도 불림 Slide 4 (of 62)

5 그래프의 종류 무방향 그래프(undirected graph) 방향 그래프(directed graph) A B A B
무방향 간선(undirected edge)만 사용 간선을 통해서 양방향으로 갈수 있음 도로의 왕복통행 길 (A, B)와 같이 정점의 쌍으로 표현 (A, B) = (B, A) 방향 그래프(directed graph) 방향 간선(undirected edge)만 사용 간선을 통해서 한쪽 방향으로만 갈 수 있음 도로의 일방통행 길 <A, B> 와 같이 정점의 쌍으로 표현 <A, B> ≠ <B, A> A B A B Slide 5 (of 62)

6 가중치 그래프 가중치 그래프(weighted graph)는 네트워크(network)라고도 함
간선에 비용(cost)이나 가중치(weight)가 할당된 그래프 가중치 그래프 예 정점 : 각 도시를 의미 간선 : 도시를 연결하는 도로 의미 가중치 : 도로의 길이 1200 A B Slide 6 (of 62)

7 그래프 표현의 예 V(G1)= {0, 1, 2, 3},      E(G1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)} V(G2)= {0, 1, 2, 3},      E(G3)= {(0, 1), (0, 2))} V(G2)= {0, 1, 2},         E(G2)= {<0, 1>, <1, 0>, <1, 2>} Slide 7 (of 62)

8 부분 그래프(subgraph) 정점 집합 V(G)와 간선 집합 E(G)의 부분 집합으로 이루어진 그래프
Slide 8 (of 62)

9 그래프 인접 정점(adjacent vertex) 무방향 그래프의 차수(degree)
하나의 정점에서 간선에 의해 직접 연결된 정점 G1에서 정점 0의 인접 정점: 정점 1, 정점 2, 정점 3 무방향 그래프의 차수(degree) 하나의 정점에 연결된 다른 정점의 수 G1에서 정점 0의 차수: 3 무방향 그래프의 모든 차수의 합은 간선 수의 2배 G1의 차수의 합: 10 G1의 간선의 합: 5 Slide 9 (of 62)

10 그래프 방향 그래프의 차수(degree) 진입 차수(in-degree) : 외부에서 오는 간선의 수
진출 차수(out-degree) : 외부로 향하는 간선의 수 G3에서 정점 1의 차수: 내차수 1, 외차수 2 방향 그래프의 모든 진입(진출) 차수의 합은 간선의 수 G3의 진입 차수의 합: 3 G3의 간선 합: 3 Slide 10 (of 62)

11 그래프의 경로(path) 무방향 그래프의 정점 s로부터 정점 e까지의 경로 방향 그래프의 정점 s로부터 정점 e까지의 경로
정점의 나열 s, v1, v2, ..., vk, e 나열된 정점들 간에 반드시 간선 (s, v1), (v1, v2), ... , (vk, e) 존재 방향 그래프의 정점 s로부터 정점 e까지의 경로 나열된 정점들 간에 반드시 간선 <s, v1>, <v1, v2>, ... ,<vk, e> 존재 경로의 길이(length) 경로를 구성하는데 사용된 간선의 수 단순 경로(simple path) 경로 중에서 반복되는 간선이 없는 경로 사이클(cycle) 단순 경로의 시작 정점과 종료 정점이 동일한 경로 Slide 11 (of 62)

12 그래프의 경로(path) G1의 0, 1, 2,3은 경로지만 0, 1, 3, 2는 경로 아님
G1의 0, 1, 2, 0과 G3의 0, 1, 0은 사이클 Slide 12 (of 62)

13 그래프의 연결정도 연결 그래프(connected graph) 트리(tree)
그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프 트리의 예 Slide 13 (of 62)

14 그래프의 연결정도 완전 그래프(complete graph) 모든 정점이 연결되어 있는 그래프
n개의 정점을 가진 무방향 완전그래프의 간선의 수: n×(n-1)/2 n=4, 간선의 수 = (4×3)/2 = 6 Slide 14 (of 62)

15 그래프 ADT 그래프에 정점을 추가하려면 insert_vertex 연산 사용
∙객체: 정점의 집합과 간선의 집합 ∙연산: ▪ create_graph() ::= 그래프를 생성한다. ▪ init(g) ::= 그래프 g를 초기화한다. ▪ insert_vertex(g,v) ::= 그래프 g에 정점 v를 삽입한다. ▪ insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v)를 삽입한다. ▪ delete_vertex(g,v) ::= 그래프 g의 정점 v를 삭제한다. ▪ delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v)를 삭제한다. ▪ is_empty(g) ::= 그래프 g가 공백 상태인지 확인한다. ▪ adjacent(v) ::= 정점 v에 인접한 정점들의 리스트를 반환한다. ▪ destroy_graph(g) ::= 그래프 g를 제거한다. 그래프에 정점을 추가하려면 insert_vertex 연산 사용 그래프에 간선을 추가하려면 insert_edge 연산 사용 Slide 15 (of 62)

16 그래프 표현 방법 인접행렬 (adjacent matrix) 방법 인접 행렬의 대각선 성분은 모두 0(자체 간선 불허)
if(간선 (i, j)가 그래프에 존재)    M[i][j] = 1, 그렇지않으면                              M[i][j] = 0. 인접 행렬의 대각선 성분은 모두 0(자체 간선 불허) 무방향 그래프의 인접 행렬은 대칭 Slide 16 (of 62)

17 그래프 표현 방법(cont.) 인접리스트 (adjacency list) 방법 각 정점에 인접한 정점들을 연결리스트로 표현
Slide 17 (of 62)

18 그래프 탐색 그래프의 가장 기본적인 연산 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문
많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결 (예) 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부 (예) 전자회로에서 특정 단자와 다른 단자가 서로 연결되어 있는지 여부 Slide 18 (of 62)

19 깊이우선 탐색(DFS) 깊이 우선 탐색 (DFS: depth-first search)
한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 되돌아가기 위해서는 스택 필요(순환함수 호출로 묵시적인 스택 이용 가능) Slide 19 (of 62)

20 DFS 알고리즘 depth_first_search(v) v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면)then depth_first_search(u) Slide 20 (of 62)

21 DFS 프로그램 Slide 21 (of 62) // 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType *g, int v) { int w; visited[v] = TRUE; // 정점 v의 방문 표시 printf("%d ", v); // 방문한 정점 출력 for(w=0; w<g->n; w++) // 인접 정점 탐색 if( g->adj_mat[v][w] && !visited[w] ) dfs_mat(g, w); //정점 w에서 DFS 새로시작 } // 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 void dfs_list(GraphType *g, int v) { GraphNode *w; visited[v] = TRUE; // 정점 v의 방문 표시 printf("%d ", v); // 방문한 정점 출력 for(w=g->adj_list[v]; w; w=w->link) // 인접 정점 탐색 if(!visited[w->vertex]) dfs_list(g, w->vertex); //정점 w에서 DFS 새로시작 } Slide 21 (of 62)

22 너비우선 탐색(BFS) 너비 우선 탐색(BFS: breadth-first search) 너비우선탐색 알고리즘
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 큐를 사용하여 구현됨 너비우선탐색 알고리즘 breadth_first_search(v) v를 방문되었다고 표시; 큐 Q에 정점 v를 삽입; while (not is_empty(Q)) do Q에서 정점 w를 삭제; for all u ∈ (w에 인접한 정점) do if (u가 아직 방문되지 않았으면) then u를 큐에 삽입; u를 방문되었다고 표시; Slide 22 (of 62)

23 Slide 23 (of 62)

24 BFS 프로그램(인접행렬) void bfs_mat(GraphType *g, int v) { int w; QueueType q;
init(&q); // 큐 초기화 visited[v] = TRUE; // 정점 v 방문 표시 printf("%d ", v); // 정점 출력 enqueue(&q, v); // 시작 정점을 큐에 저장 while(!is_empty(&q)){ v = dequeue(&q); // 큐에 정점 추출 for(w=0; w<g->n; w++) // 인접 정점 탐색 if(g->adj_mat[v][w] && !visited[w]){ visited[w] = TRUE; // 방문 표시 printf("%d ", w); // 정점 출력 enqueue(&q, w); // 방문한 정점을 큐에 저장 } Slide 24 (of 62)

25 BFS 프로그램(인접리스트) void bfs_list(GraphType *g, int v) { GraphNode *w;
QueueType q; init(&q); // 큐 초기화 visited[v] = TRUE; // 정점 v 방문 표시 printf("%d ", v); // 정점 v 출력 enqueue(&q, v); // 시작정점을 큐에 저장 while(!is_empty(&q)){ v = dequeue(&q); // 큐에서 정점 추출 for(w=g->adj_list[v]; w; w = w->link) //인접 정점 탐색 if(!visited[w->vertex]){ // 미방문 정점 탐색 visited[w->vertex] = TRUE; // 방문 표시 printf("%d ", w->vertex); // 정점 출력 enqueue(&q, w->vertex); // 방문한 정점을 큐에 삽입 } Slide 25 (of 62)

26 연결 성분 최대로 연결된 부분 그래프들 DFS 또는 BFS 반복 이용
DFS 또는 BFS 탐색 프로그램의 visited[v]=TRUE; 를visited[v]=count; 로 교체 void find_connected_component(GraphType *g) { int i; count = 0; for(i=0; i<g->n; i++) if(!visited[i]){ // 방문되지 않았으면 count++; dfs_mat(g, i); } Slide 26 (of 62)

27 신장 트리(spanning tree) 그래프내의 모든 정점을 포함하는 트리
모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안됨 n개의 정점을 가지는 그래프의 신장트리는 n-1개의 간선을 가짐 최소의 링크를 사용하는 네트워크 구축 시 사용: 통신망, 도로망, 유통망 등 신장트리 알고리즘 depth_first_search(v) v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then (v,u)를 신장트리 간선이라고 표시; depth_first_search(u); Slide 27 (of 62)

28 신장 트리 Slide 28 (of 62)

29 최소비용 신장트리 (MST: minimum spanning tree)
네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 MST의 응용 도로 건설 - 도시들을 모두 연결하면서 도로의 길이를 최소가 되도록 하는 문제 전기 회로 - 단자들을 모두 연결하면서 전선의 길이를 가장 최소로 하는 문제 통신 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 배관 - 파이프를 모두 연결하면서 파이프의 총 길이를 최소로 하는 문제 Slide 29 (of 62)

30 Kruskal의 MST 알고리즘 탐욕적인 방법(greedy method) 주요 알고리즘 설계 기법
각 단계에서 최선의 답을 선택하는 과정을 반복함으로써 최종적인 해답에 도달 탐욕적인 방법은 항상 최적의 해답을 주는지 검증 필요 Kruskal MST 알고리즘은 최적의 해답임이 증명됨 Slide 30 (of 62)

31 Kruskal의 MST 알고리즘 MST는 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않아야 함
각 단계에서 사이클을 이루지 않는 최소 비용 간선 선택 그래프의 간선들을 가중치의 오름차순으로 정렬 정렬된 간선 중에서 사이클을 형성하지 않는 간선을 현재의 MST 집합에 추가 만약 사이클을 형성하면 그 간선은 제외 Slide 31 (of 62)

32 Slide 32 (of 62)

33 Kruskal의 MST 알고리즘 union-find 알고리즘 두 집합들의 합집합 만듬 원소가 어떤 집합에 속하는지 알아냄
a와 b가 같은 집합에 속함 a와 b가 다른 집합에 속함 Slide 33 (of 62)

34 union-find 프로그램 Slide 34 (of 62) int parent[MAX_VERTICES]; // 부모 노드
int num[MAX_VERTICES]; // 각 집합의 크기 void set_init(int n) // 초기화 {int i; for(i=0;i<n;i++){ parent[i] = -1; num[i] = 1; } int set_find(int vertex) // vertex가 속하는 집합 반환 {int p, s, i=-1; for(i=vertex;(p=parent[i])>=0;i=p) ; // 루트 노드까지 반복 s = i; // 집합의 대표 원소 for(i=vertex;(p=parent[i])>=0;i=p) parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정 return s; void set_union(int s1, int s2) // 두 개의 원소가 속한 집합을 합함 if( num[s1] < num[s2] ){ parent[s1] = s2; num[s2] += num[s1]; else { parent[s2] = s1; num[s1] += num[s2]; Slide 34 (of 62)

35 Kruskal의 MST 프로그램 Slide 35 (of 62) #include <stdio.h>
#define MAX_VERTICES 100 #define INF 1000 // 프로그램 10.7의 union-find 프로그램 삽입 // ... // 히프의 요소 타입 정의 typedef struct { int key; // 간선의 가중치 int u; // 정점 1 int v; // 정점 2 } element; // 프로그램 8.5 중에서 최소 히프 프로그램 삽입 // 정점 u와 정점 v를 연결하는 가중치가 weight인 간선을 히프에 삽입 void insert_heap_edge(HeapType *h, int u, int v, int weight) { element e; e.u = u; e.v = v; e.key = weight; insert_min_heap(h, e); } // 인접 행렬이나 인접 리스트에서 간선들을 읽어서 최소 히프에 삽입 // 현재는 예제 그래프의 간선들을 삽입한다. void insert_all_edges(HeapType *h){ insert_heap_edge(h,0,1,29); insert_heap_edge(h,1,2,16); insert_heap_edge(h,2,3,12); insert_heap_edge(h,3,4,22); insert_heap_edge(h,4,5,27); insert_heap_edge(h,5,0,10); insert_heap_edge(h,6,1,15); insert_heap_edge(h,6,3,18); insert_heap_edge(h,6,4,25); Slide 35 (of 62)

36 Kruskal의 MST 프로그램(cont.)
void kruskal(int n) { int edge_accepted=0; // 현재까지 선택된 간선의 수 HeapType h; // 최소 히프 int uset, vset; // 정점 u와 정점 v의 집합 번호 element e; // 히프 요소 init(&h); // 히프 초기화 insert_all_edges(&h); // 히프에 간선들을 삽입 set_init(n); // 집합 초기화 while( edge_accepted < (n-1) ) // 간선의 수 < (n-1) e = delete_min_heap(&h); // 최소 히프에서 삭제 uset = set_find(e.u); // 정점 u의 집합 번호 vset = set_find(e.v); // 정점 v의 집합 번호 if( uset != vset ){ // 서로 속한 집합이 다르면 printf("(%d,%d) %d \n",e.u, e.v, e.key); edge_accepted++; set_union(uset, vset); // 두개의 집합을 합친다. } // main() kruskal(7); Slide 36 (of 62)

37 Kruskal의 MST 알고리즘 복잡도 Kruskal 알고리즘은 대부분 간선들을 정렬하는 시간에 좌우됨
사이클 테스트 등의 작업은 정렬에 비해 매우 신속하게 수행됨 네트워크의 간선 e개를 퀵정렬과 같은 효율적인 알고리즘으로 정렬한다면 Kruskal 알고리즘의 시간 복잡도는 O(e*log(e))가 된다 Slide 37 (of 62)

38 Prim의 MST 알고리즘 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나감
시작 단계에서는 시작 정점만이 신장 트리 집합에 포함됨 신장 트리 집합에 인접한 정점 중에서 최저 간선으로 연결된 정점 선택하여 신장 트리 집합에 추가함 이 과정은 신장 트리 집합이 n-1개의 간선을 가질 때까지 반복 간선 (a, b)=29 간선 (f, e)=27 간선 (f, e) 선택 정점 e가 신장 트리 집합에 추가됨 Slide 38 (of 62)

39 Prim의 MST 알고리즘 Slide 39 (of 62)

40 Slide 40 (of 62)

41 Prim의 MST 프로그램 #include <stdio.h> #define TRUE 1 #define FALSE 0
#define MAX_VERTICES 7 #define INF 1000L int weight[MAX_VERTICES][MAX_VERTICES]={ { 0, 29, INF, INF, INF, 10, INF }, { 29, 0, 16, INF, INF, INF, 15 }, { INF, 16, 0, 12, INF, INF, INF }, { INF, INF, 12, 0, 22, INF, 18 }, { INF, INF, INF, 22, 0, 27, 25 }, { 10, INF, INF, INF, 27, 0, INF }, { INF, 15, INF, 18, 25, INF, 0 }}; int selected[MAX_VERTICES]; int dist[MAX_VERTICES]; // 최소 dist[v] 값을 갖는 정점을 반환 int get_min_vertex(int n) { int v,i; for (i = 0; i <n; i++) if (!selected[i]) { v = i; break; } for (i = 0; i < n; i++) if ( !selected[i] && (dist[i] < dist[v])) v = i; return (v); Slide 41 (of 62)

42 Prim의 MST 프로그램(cont.) void prim(int s, int n) { int i, u, v;
for(u=0;u<n;u++) dist[u]=INF; dist[s]=0; for(i=0;i<n;i++){ u = get_min_vertex(n); selected[u]=TRUE; if( dist[u] == INF ) return; printf("%d ", u); for( v=0; v<n; v++) if( weight[u][v]!= INF) if( !selected[v] && weight[u][v]< dist[v] ) dist[v] = weight[u][v]; } // main() prim(0, MAX_VERTICES); Slide 42 (of 62)

43 Prim의 MST 알고리즘 복잡도 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 Prim의 알고리즘은 O(n2)의 복잡도를 가진다. 희박한 그래프 O(e*log(e)) 인 Kruskal의 알고리즘이 유리 밀집한 그래프 O(n2) 인 Prim의 알고리즘이 유리 Slide 43 (of 62)

44 최단 경로(shortest path) 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로 간선의 가중치는 비용, 거리, 시간 등 정점 0에서 정점 3으로 가는 최단 경로 문제 인접행렬에서 간선이 없는 노드쌍의 가중치는 ∞ 임 0,4,1,2,3이 최단 경로 최단경로 길이는 =11 Slide 44 (of 62)

45 Dijkstra의 최단경로 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로 찾음 집합 S
시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합 distance 배열 최단경로가 알려진 정점들만을 이용한 다른 정점들까지의 최단경로 길이 distance 배열의 초기값(시작 정점 v) distance[v] = 0 다른 정점에 대한 distance 값은 시작정점과 해당 정점간의 가중치 값 매 단계에서 가장 distance 값이 작은 정점을 S에 추가 Slide 45 (of 62)

46 Dijkstra의 최단경로 알고리즘 distance 값이 가장 작은 정점을 u라고 하자. 그러면 시작 정점 v에서 정점 u까지의 최단거리는 경로 ①이 된다. 정점 w를 거쳐서 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정해보자. 그러면 정점 v에서 정점 u까지의 거리는 정점 v에서 정점 w까지의 거리 ②와 정점 w에서 정점 u로 가는 거리③을 합한 값이 된다. 그러나 경로 ②는 경로 ①보다 항상 길 수 밖에 없다. 왜냐하면 현재 distance 값이 가장 작은 정점은 u이기 때문이다. 따라서 매 단계에서 distance 값이 가장 작은 정점들을 추가해나가면 시작 정점에서 모든 정점까지의 최단거리를 구할 수 있다. Slide 46 (of 62)

47 Dijkstra의 최단경로 알고리즘 새로운 정점이 S에 추가되면 distance값 갱신 Slide 47 (of 62)

48 Dijkstra의 최단경로 알고리즘 // 입력: 가중치 그래프 G, 가중치는 음수가 아님.
// 출력: distance 배열, distance[u]는 v에서 u까지의 최단 거리이다. shortest_path(G, v) S←{v} for 각 정점 w∈G do distance[w]←weight[v][w]; while 모든 정점이 S에 포함되지 않으면 do u←집합 S에 속하지 않는 정점 중에서 최소 distance 정점; S←S∪{u} for u에 인접하고 S에 있는 각 정점 z do if distance[u]+weight[u][z] < distance[z] then distance[z]←distance[u]+weight[u][z]; Slide 48 (of 62)

49 Dijkstra의 최단경로 알고리즘 Slide 49 (of 62)

50 Dijkstra의 최단경로 알고리즘 Slide 50 (of 62)

51 Dijkstra의 최단경로 프로그램 Slide 51 (of 62) #include <stdio.h>
#include <limits.h> #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 7 // 정점의 수 #define INF // 무한대 (연결이 없는 경우) int weight[MAX_VERTICES][MAX_VERTICES]={ // 네트워크의 인접 행렬 { 0, 7, INF, INF, 3, 10, INF }, { 7, 0, 4, 10, 2, 6, INF }, { INF, 4, 0, 2, INF, INF, INF }, { INF, 10, 2, 0, 11, 9, 4 }, { 3, 2, INF, 11, 0, INF, 5 }, { 10, 6, INF, 9, INF, 0, INF }, { INF, INF, INF, 4, 5, INF, 0 }}; int distance[MAX_VERTICES]; // 시작정점으로부터의 최단경로 거리 int found[MAX_VERTICES]; // 방문한 정점 표시 // int choose(int distance[], int n, int found[]) { int i, min, minpos; min = INT_MAX; minpos = -1; for(i=0;i<n;i++) if( distance[i]< min && ! found[i] ){ min = distance[i]; minpos=i; } return minpos; Slide 51 (of 62)

52 Dijkstra의 최단경로 프로그램(cont.)
void shortest_path(int start, int n) { int i, u, w; for(i=0; i<n; i++) // 초기화 {distance[i] = weight[start][i]; found[i] = FALSE; } found[start] = TRUE; // 시작 정점 방문 표시 distance[start] = 0; for(i=0; i<n-2; i++){ u = choose(distance, n, found); found[u] = TRUE; for(w=0;w<n; w++) if(!found[w]) if( distance[u]+weight[u][w]<distance[w] ) distance[w] = distance[u]+weight[u][w]; // void main() shortest_path(0, MAX_VERTICES); Slide 52 (of 62)

53 Dijkstra의 최단경로 알고리즘 복잡도
네트워크에 n개의 정점이 있다면, Dijkstra의 최단경로 알고리즘은 주반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n2)의 복잡도를가진다. Slide 53 (of 62)

54 Floyd의 최단경로 알고리즘 모든 정점 사이의 최단경로를 찾음 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성
인접 행렬 weight 구성 i==j이면, weight[i][j]=0 두개의 정점 i,j 사이에 간선이 존재하지 않으면, weight[i][j]=∞ 정점 i,j 사이에 간선이 존재하면, weight[i][j]는 간선 (i, j)의 가중치 배열 A의 초기 값은 인접 행렬 weight임 floyd(G) for k ← 0 to n - 1 for i ← 0 to n - 1 for j ← 0 to n - 1 A[i][j] = min(A[i][j], A[i][k] + A[k][j]) Slide 54 (of 62)

55 Floyd의 최단경로 알고리즘 Ak [i][j] A-1→A0 → A1 → … → An-1순으로 최단 경로 구해감
Ak-1까지 구해진 상태에서 k번째 정점이 추가로 고려되는 상황을 생각하자 0부터 k까지의 정점만을 사용하여 정점 i에서 정점 j로 가는 최단 경로는 다음의 2가지의 경우로 나뉘어진다. 정점 k를 거치지 않는 경우: Ak[i][j] 는 k보다 큰 정점은 통과하지 않으므로 최단거리는 여전히 Ak-1[i][j]]임 정점 k를 거치는 경우: i에서 k까지의 최단거리 Ak-1[i][k]에 k에서 j까지의 최단거리 Ak-1[k][j]를 더한 값 Slide 55 (of 62)

56 Floyd의 최단경로 프로그램 int A[MAX_VERTICES][MAX_VERTICES]; void floyd(int n)
{ int i, j, k; for(i=0; i<n; i++) for(j=0; j<n; j++) A[i][j]=weight[i][j]; for(k=0; k<n; k++) if (A[i][k]+A[k][j] < A[i][j]) A[i][j] = A[i][k]+A[k][j]; } Slide 56 (of 62)

57 Floyd의 최단경로 알고리즘 복잡도 네트워크에 n개의 정점이 있다면, Floyd의 최단경로 알고리즘은 3중 반복문을 실행되므로 시간 복잡도는 O(n3) 이 된다 모든 정점쌍의 최단경로를 구하려면 Dijkstra의 알고리즘 O(n2)을 n번 반복해도 되며, 이 경우 전체 복잡도는 O(n3) 이 된다 모든 정점쌍의 최단경로를 구하는데 있어 두 알고리즘 모두 동일한 O(n3)의 복잡도를 가지지만 Floyd의 알고리즘은 매우 간결한 반복구문을 사용하므로 Dijkstra의 알고리즘 보다 효율적이다 Slide 57 (of 62)

58 위상정렬(topological sort)
방향 그래프에서 간선 <u, v>가 있다면 정점 u는 정점 v를 선행함 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열 선수 과목은 과목들의 선행 관계 표현함 위상 순서(topological order) (0,1,2,3,4,5) , (1,0,2,3,4,5) (2,0,1,3,4,5)는 위상 순서가 아님 왜냐하면 2번 정점이 0번 정점 앞에 오기 때문 과목번호 과목명 선수과목 전산학개론 없음 1 이산수학 2 자료구조 3 알고리즘 분석 0, 1, 2 4 운영체제 5 인공지능 2, 3, 4 Slide 58 (of 62)

59 위상정렬 알고리즘 Input: 그래프 G=(V,E) Output: 위상 정렬 순서 topo_sort(G)
for i←0 to do if( 모든 정점이 선행 정점을 가지면 ) then 사이클이 존재하고 위상 정렬 불가; 선행 정점을 가지지 않는 정점 v 선택; v를 출력; v와 v에서 나온 모든 간선들을 그래프에서 삭제; Slide 59 (of 62)

60 위상정렬의 예 Slide 60 (of 62)

61 위상정렬 프로그램 void topo_sort(GraphType *g) { int i; StackType s;
GraphNode *node; // 모든 정점의 진입 차수를 계산 int *in_degree = (int *)malloc(g->n* sizeof(int)); for(i = 0; i < g->n; i++) // 초기화 in_degree[i] = 0; for(i = 0; i < g->n; i++){ GraphNode *node = g->adj_list[i]; // 정점 i에서 나오는 간선들 while ( node != NULL ) { In_degree[node->vertex]++; node = node->link; } Slide 61 (of 62)

62 위상정렬 프로그램(cont.) // 진입 차수가 0인 정점을 스택에 삽입 init(&s);
for(i = 0; i < g->n; i++){ if( in_degree[i] == 0 ) push(&s, i); } // 위상 순서를 생성 while(!is_empty(&s)){ int w; w = pop(&s); printf("%d", w); node = g->adj_list[w]; // 각 정점의 진입 차수를 변경 while (node != NULL) { int u = node->vertex; in_degree[u]--; // 진입 차수를 감소 if(in_degree[u] == 0) push(&s, u); node = node->link; // 다음 정점 free(in_degree); return; // 반환값이 1이면 성공, 0이면 실패 Slide 62 (of 62)