11장.그래프

Size: px

Start display at page:

Download "11장.그래프"

현시 엄
6 years ago
Views:

1 T STRUTURS USIN PTR 그래프 1/32

2 그래프 (graph) 란? 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 그래프의예 트리 (tree) 지도, 지하철노선도 전기회로의연결상태 OS의프로세스와자원관계 인맥지도 2/32

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

4 그래프정의 그래프 는 (V, ) 로표시 정점 (vertices) 또는노드 (node) 여러가지특성을가질수있는객체의미 V() : 그래프 의정점들의집합 정점 ( vertex) 간선 (edge) 또는링크 (link) 정점들간의관계의미 () : 그래프 의간선들의집합 간선 ( edge) 2 동일한그래프? /32

5 그래프의종류 간선의종류에따라 무방향그래프 (undirected graph) 간선을통해서양방향으로갈수있음 (, ) 로표현 (, ) = (, ) 방향그래프 (directed graph) 간선을통해서한쪽방향으로만갈수있음 일방통행길 <, > 로표현 <, > <, > 5/32

6 가중치그래프 (weighted graph) 네트워크 (network) 라고도함 간선에비용 (cost) 이나가중치 (weight) 가할당된그래프 가중치그래프예 정점 : 각도시를의미 간선 : 도시를연결하는도로의미 가중치 : 도로의길이 부분그래프 정점집합 V() 와간선집합 () 의부분집합으로이루어진그래프 인천 30 서울 수원 50 대전 1200 제천 청주 대구광주 강릉영주 110 부산 울산 6/32

7 그래프표현의예 그래프표현의예 V(1)= {0, 1, 2, 3, (1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3) V(2)= {0, 1, 2, 3, (3)= {(0, 1), (0, 2)) V(2)= {0, 1, 2, (2)= {<0, 1>, <1, 0>, <1, 2> 7/32

8 그래프의용어 인접정점 (adjacent vertex) 하나의정점에서간선에의해직접연결된정점 1 에서정점 0 의인접정점 정점 1, 정점 2, 정점 3 차수 (degree) 하나의정점에연결된다른정점의수 무방향그래프 1 에서정점 0 의차수 : 3 차수의합은간선수의 2 배 방향그래프 진입차수, 진출차수 모든진입 ( 진출 ) 차수의합은간선의수 8/32

9 그래프의경로 (path) 무방향그래프의정점 s 로부터정점 e 까지의경로 정점의나열 s, v1, v2,..., vk, e 반드시간선 (s, v1), (v1, v2),..., (vk, e) 존재해야함 방향그래프의정점 s 로부터정점 e 까지의경로 정점의나열 s, v1, v2,..., vk, e 반드시간선 <s, v1>, <v1, v2>,...,<vk, e> 존재해야함 경로의길이 (length) 경로를구성하는데사용된간선의수 9/32

10 단순경로 (simple path) 경로중에서반복되는간선이없는경로 1, 0, 2, 3은단순경로 1, 0, 2, 0은단순경로아님 사이클 (cycle) 시작정점과종료정점이동일한경로 0, 1, 2, 0 은사이클 /32

11 연결그래프 (connected graph) 모든정점쌍에대한경로존재 2는비연결그래프임 트리 (tree) 그래프의특수한형태로서사이클을가지지않는연결그래프 완전그래프 (complete graph) 모든정점이연결되어있는그래프 n개의정점을가진무방향완전그래프의간선의수 n (n-1)/2 0 3 n=4, 간선의수 = (4 3)/2 = /32

12 그래프 T 데이터정점의집합과간선의집합연산 init(): 그래프를초기화한다. is_empty(): 그래프가공백상태인지확인한다. insert_vertex(v): 그래프에정점 v를삽입한다. insert_edge(u,v): 그래프에간선 (u,v) 를삽입한다. delete_vertex(v): 그래프의정점 v를삭제한다. delete_edge(u,v): 그래프 g의간선 (u,v) 를삭제한다. adjacent(v): 정점 v에인접한모든정점의집합을반환한다. 12/32

13 그래프표현방법 1 : 인접행렬 nxn 의인접행렬 M 을이용 간선 (i, j) 가있으면 M[i][j] = 1, 또는 true 그렇지않으면 M[i][j] = 0, 또는 false 대각선성분은모두 무방향그래프 인접행렬이대칭 /32

14 인접행렬을이용한그래프표현 그래프데이터와기본연산 typedef char Vtxata; int adj[mx_vtxs][mx_vtxs]; int vsize; Vtxata vdata[mx_vtxs]; // 그래프정점에저장할데이터의자료형 // 인접행렬 // 전체정점의개수 // 정점에저장할데이터배열 void init_graph() { int i, j; vsize=0; for(i=0 ; i<mx_vtxs; i++) for(j=0 ; j<mx_vtxs; j++) adj[i][j] = 0; void insert_vertex( char name ) { if (is_full_graph()) error("rror: 정점개수초과 \n"); else vdata[vsize++] = name; void insert_edge(int u, int v, int val) { adj[u][v] = val; void insert_edge2(int u, int v, int val) { adj[u][v] = adj[v][u] = val; 14/32

15 전체프로그램 void main() { int i; init_graph( ); for( i=0 ; i<4 ; i++ ) insert_vertex( ''+i ); insert_edge2(0,1, 1); insert_edge2(0,3, 1); insert_edge2(1,2, 1); insert_edge2(1,3, 1); insert_edge2(2,3, 1); print_graph( stdout, " 그래프 ( 인접행렬 )\n"); 15/32

$그래프파일입출력 전체정점개수 각정점의정보 인접행렬 void print_graph(il *fp, char* msg) { int i, j; fprintf(fp, "%s", msg); fprintf(fp, "%d\n", vsize); for( i=0 ; i<vsize ; i++ ) {.$

16 그래프파일입출력 전체정점개수 각정점의정보 인접행렬 void print_graph(il *fp, char* msg) { int i, j; fprintf(fp, "%s", msg); fprintf(fp, "%d\n", vsize); for( i=0 ; i<vsize ; i++ ) {... void store_graph (char *filename) { IL *fp = fopen(filename, "w"); if( fp!= NULL ) { print_graph( fp, "" ); fclose(fp); void load_graph ( char *filename) { int i, j, val, n; char str[80]; IL *fp = fopen(filename, "r"); if( fp!= NULL ) { init_graph(); fscanf(fp, "%d", &n); for(i=0 ; i<n ; i++ ) {... fclose(fp); 16/32

17 그래프표현방법 2 : 인접리스트 adjacency list 각정점이연결리스트를가짐 인접한정점들을연결리스트로표현 NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL 17/32

18 인접리스트를이용한그래프표현 그래프데이터와기본연산 typedef struct raphnode { int id; struct raphnode* link; Node; typedef char Vtxata; // 정점의 id // 다음노드의포인터 // 그래프정점에저장할데이터의자료형 int vsize; // 정점의개수 Vtxata vdata[mx_vtxs]; // 정점에저장할데이터배열 Node* adj[mx_vtxs]; // 각정점의인접리스트 int is_empty_graph() { return (vsize == 0); int is_full_graph() { return (vsize >= MX_VTXS); void init_graph( ) { void reset_graph() { void insert_vertex( char name ) { void insert_edge( int u, int v ) { 18/32

19 전체프로그램 void main() { load_graph( "graph.txt"); print_graph(" 그래프 ( 인접리스트 )\n"); 19/32

20 그래프탐색 그래프의가장기본적인연산 시작정점부터차례대로모든정점들을한번씩방문 많은문제들이단순히탐색만으로해결됨 도로망예 : 특정도시에서다른도시로갈수있는지여부 전자회로예 : 특정단자와다른단자의연결여부 깊이우선탐색 (S) 너비우선탐색 (S) 20/32

21 깊이우선탐색 (S) S: depth-first search 한방향으로갈수있을때까지가다가더이상갈수없게되면가장가까운갈림길로돌아와서이곳으로부터다른방향으로다시탐색진행 되돌아가기위해서는스택필요 순환함수호출로묵시적인스택이용 depthirstsearch(v) v 를방문되었다고표시 ; for all u (v 에인접한정점 ) do if (u 가아직방문되지않았으면 ) then depthirstsearch(u) 21/32

22 22/32 (a) 에서시작 : -> (d) -> (, 는방문했음 ) (g) 에서는모두방문했음.,,, 순으로되돌아감. 에서는가지않은 가있음. (b) -> ( 는방문했음 ) (e) -> ( 는방문했음 ) (c) -> ( 는방문했음 ) (f) -> ( 는방문했음 ) (i) 에서도모두방문했음.,, 순으로되돌아감. 탐색완료. 방문순서 : (h) -> S 알고리즘

$S 구현 ( 인접행렬 ) int visited[mx_vtxs]; void reset_visited() { int i; for( i=0 ; i<vsize ; i++ ) visited[i] = 0; void S( int v)$

23 S 구현 ( 인접행렬 ) int visited[mx_vtxs]; void reset_visited() { int i; for( i=0 ; i<vsize ; i++ ) visited[i] = 0; void S( int v) { int w; visited[v] = 1; printf("%c ", vdata[v]); for( w=0 ; w<vsize ; w++) if( adj[v][w]!=0 && visited[w]==0) S( w ); 23/32

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

25 S 알고리즘 (a) 에서시작. 큐내용 : (b) ->, 큐내용 : (c) -> 큐내용 : (d) -> 큐내용 : (e) -> 큐내용 : (f) ->, 큐내용 : (g) 에서는모두방문했음. 큐내용 : (h) 에서는모두방문했음. 큐내용 : (i) 에서도모두방문했음. 큐공백상태 -> 탐색완료. 방문순서 : 25/32

26 S 구현 ( 인접리스트 ) void S( int v) { Node *w; init_queue( ); visited[v] = 1; printf("%c ", vdata[v]); enqueue( v ); while(!is_empty()){ v = dequeue(); for( w=adj[v] ; w!=null ; w=w->link ) { if(!visited[w->id]){ visited[w->id] = 1; printf("%c ", vdata[w->id]); enqueue(w->id); 26/32

27 연결성분 최대로연결된부분그래프들을구함 S 또는 S 반복이용 visited[v]=tru; 를 visited[v]=count; 로교체 label 27/32

28 int visited[mx_vtxs]; int label[mx_vtxs]; void labels( int v, int color) { int w; visited[v] = 1; label[v] = color; printf("%c ", vdata[v]); for( w=0 ; w<vsize ; w++) if( adj[v][w]!=0 && visited[w]==0) labels( w, color ); void findonnectedomponent() { int i, count = 0; for( i=0 ; i<vsize ; i++ ) visited[i] = 0; for(i=0; i<vsize ; i++) if( visited[i]==0) labels(i, ++count); printf("\n 연결성분개수 = %d\n", count); for( i=0 ; i<vsize ; i++ ) printf("%c=%d ", vdata[i], label[i]); 28/32

29 신장트리 (spanning tree) Spanning Tree 모든정점들이연결되어야하고사이클을포함하면안됨 신장트리는 n-1개의간선을가짐 최소의링크를사용하는네트워크구축시사용 통신망, 도로망, 유통망등 다양한신장트리가능 (a) 연결그래프 (b) 신장트리의예 (S 에서의간선 ) (c) 신장트리의예 (S 에서의간선 ) 29/32

30 신장트리 (spanning tree) spanningtreeys(v) v 를방문되었다고표시 ; for all u (v 에인접한정점 ) do if (u 가아직방문되지않았으면 ) then (v,u) 를신장트리간선이라고표시 ; spanningtreeys(u); 30/32

31 위상정렬 Topological sort 방향그래프에대해정점들의선행순서를위배하지않으면서모든정점을나열하는것 여러방법이가능 과목번호과목명선수과목 전산학개론 자료구조 컴퓨터개론 없음 이산수학 없음 알고리즘 인공지능 자료구조 알고리즘,, 이산수학 운영체제 운영체제 인공지능,, <,,,,,> <,,,,,> 31/32

32 위상정렬알고리즘 (a) 초기상태 (b) 제거 (c) 제거 (d) 제거 (e) 제거 (f) 제거 toposort() for i 0 to n-1 do if 모든정점이선행정점을가지면 then 사이클이존재하고위상정렬불가 ; 선행정점을가지지않는정점 v 선택 ; v 를출력 ; v 와 v 에서나온모든간선들을그래프에서삭제 ; 32/32

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]