2015-1 12. 그래프와관련알고리즘 2015 년 5 월 28 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr)
그래프 (Graph) 그래프의응용예 Outline 미로찾기 인터넷라우터에서의패킷 forwarding 그래프의구현 그래프탐색 Depth First Searching Breadth First Searching 그래프노드간의최단거리경로산출 Shortest path: Dijkstra s Algorithm ch12-2
그래프 (graph) 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 우리가배운트리 (tree) 도그래프의특수한경우임 전기회로의소자간연결상태 운영체제의프로세스와자원관계 큰프로젝트에서작은프로젝트간의우선순위 지도에서도시들의연결상태 ch12-3
미로찾기 (1) 그래프의응용예 (1) 아래그림으로표현된미로에서지정된입구 (v0) 에서지정된출구 (v20) 로찾아갈수있는길이있는가? 만약출구로찾아갈수있는길이있다면, 최단경로? 0 1 2 3 4 0 v0 (start) v1 v2 v3 v4 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 3 v15 v16 v17 v18 v19 4 v20 (end) v21 v22 v23 v24 ch12-4
미로찾기 (2) 출구로찾아갈수있는경로 최단경로 0 1 2 3 4 0 v0 (start) v1 v2 v3 v4 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 Path by obtained by Depth First Search Path by obtained by Breadth First Search 3 v15 v16 v17 v18 v19 4 v20 v21 v22 v23 v24 (end) ch12-5
그래프의응용예 (2) 인터넷라우터에서의패킷 Forwarding 0 1 2 3 4 Dest Next hop for Destination Addr Addr Router Addr 0 1 2 3 4 0 0 1 1 1 1 1 0 1 2 2 2 2 1 1 2 3 3 3 2 2 2 3 4 4 3 3 3 3 4 ch12-6
복잡한 network topology 에서의패킷전달 각라우터위치에서의목적지주소로최단경로를통하여패킷을전달하기위한 next hop 은? 820 5M Seattle 0 San Francisco 1 380 5M 2 Los Angels 745 10M 688 10M 381 10M 6 Phoenix 1144 20M 828 Rapid city 10M 4 657 Salt Lake City 10M 389 3 521 50M 50M Denver 5 816 10M 1067 50M 920 50M 780 100M Minneapolis Boston 7 19 409 Detroit 834 10M Chicago 10M 14 640 211 5M 13 286 18 297 5M New York 10M 534 102 237 5M 861 St. Louis 10M 17 845 50M Washington 12 10M 285 D.C. 632 10M Memphis 11 394 10M Dallas 5M 16 Atlanta 8 454 393 100M 10M 473 246 10M 661 5M 352 9 10 10M 10M 861 Houston New Orleans10M 15 611 10M ch12-7 Miami
그래프정의 그래프 G는 (V, E) 로표시 정점 (vertex) 여러가지특성을가질수있는객체의미 V(G) : 그래프 G의정점들의집합 노드 (node) 라고도불림 간선 (edge) 정점들간의관계의미 E(G) : 그래프 G의간선들의집합 링크 (link) 라고도불림 ch12-8
그래프로표현하는것들 도로망 영역간인접관계 ch12-9
그래프의종류 무방향그래프 (undirected graph) 무방향간선 (undirected edge) 만사용 간선을통해서양방향으로갈수있음 도로의왕복통행길 (A, B) 와같이정점의쌍으로표현 (A, B) = (B, A) 방향그래프 (directed graph) 방향간선 (undirected edge) 만사용 간선을통해서한쪽방향으로만갈수있음 도로의일방통행길 <A, B> 와같이정점의쌍으로표현 <A, B> <B, A> A A B B ch12-10
가중치그래프 (Weighted Graph) 가중치그래프 (weighted graph) 는네트워크 (network) 라고도함 간선에비용 (cost) 이나가중치 (weight) 가할당된그래프 A 1200 B 가중치그래프 예 정점 : 각도시를의미 간선 : 도시를연결하는도로의미 가중치 : 도로의길이 ch12-11
그래프표현의예 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(G2)= {(0, 1), (0, 2))} V(G3)= {0, 1, 2}, E(G3)= {<0, 1>, <1, 0>, <1, 2>} ch12-12
부분그래프 (subgraph) 정점집합 V(G) 와간선집합 E(G) 의부분집합으로이루어진그래프 그래프 G1 의부분그래프들 그래프 G1 ch12-13
그래프관련용어 (terminology) (1) 인접정점 (adjacent vertex) 하나의정점에서간선에의해직접연결된정점 G1에서정점 0의인접정점 : 정점 1, 정점 2, 정점 3 무방향그래프의차수 (degree) 하나의정점에연결된다른정점의수 G1에서정점 0의차수 :3 무방향그래프의모든차수의합은간선수의 2배 G1의차수의합 : 10 G1의간선의합 : 5 ch12-14
그래프관련용어 (terminology) (2) 방향그래프의차수 (degree) 진입차수 (in-degree) : 외부에서오는간선의수 진출차수 (out-degree) : 외부로향하는간선의수 G3에서정점 1의차수 : 내차수 1, 외차수 2 방향그래프의모든진입 ( 진출 ) 차수의합은간선의수 G3의진입차수의합 : 3 G3의진입차수의합 : 3 G3의간선합 : 3 ch12-15
그래프의경로 (path) 무방향그래프의정점 s (start) 로부터정점 e (end) 까지의경로 정점의나열 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) 경로를구성하는데사용된간선의수 단순경로 (simple path) 경로중에서반복되는간선이없는경로 사이클 (cycle) 단순경로의시작정점과종료정점이동일한경로 ch12-16
그래프의경로 (path) G1의 0, 1, 2, 3은경로지만 0, 1, 3, 2는경로아님 G1의 1, 0, 2, 3은단순경로이지만 1, 0, 2, 0은단순경로아님 G1의 0, 1, 2, 0과 G3의 0, 1, 0은사이클 ch12-17
그래프의연결정도 연결그래프 (connected graph) 무방향그래프 G에있는모든정점쌍 (vertices pair) 에대하여항상경로존재 G2는비연결그래프임 트리 (tree) 그래프의특수한형태로서사이클을가지지않는연결그래프 트리의예 ch12-18
그래프의연결정도 완전그래프 (complete graph) 모든정점이연결되어있는그래프 n개의정점을가진무방향완전그래프의간선의수 : n (n-1)/2 n=4, 간선의수 =(4 3)/2 = 6 ch12-19
그래프 Abstract Data Type (ADT) 객체 : 정점의집합과간선의집합 연산 : 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 연산사용 ch12-20
그래프표현방법 (1) 인접행렬 인접행렬 (adjacent matrix) 방법 if( 간선 (i, j) 가그래프에존재 ) adjmtrx[i][j] = 1, 그렇지않으면 adjmtrx[i][j] = 0. 인접행렬의대각선성분은모두 0( 자체간선불허 ) 무방향그래프의인접행렬은대칭 ch12-21
그래프표현방법 (2) 인접리스트 인접리스트 (adjacency list) 방법 각정점에인접한정점들을연결리스트로표현 ch12-22
그래프의 C 프로그램 /* Graph.h (1) */ #ifndef GRAPH_H #define GRAPH_H #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits> #define MAX_NAME_LENGTH 10 #define PLUS_INF INT_MAX/2 enum VertexStatus {UNEXPLORED, VRTX_NOT_VISITED, VRTX_VISITED, VRTX_NOT_SELECTED, VRTX_SELECTED}; enum EdgeStatus {EDGE_UNEXPLORED, DISCOVERY, BACK, CROSS, EDGE_NOT_FOUND, EDGE_VISITED}; enum BFS_PROCSS_STATUS {NOT_SELECTED, SELECTED}; enum DFS_DONE {NOT_DONE, DONE}; ch12-23
/* Graph.h (2) */ typedef struct Vertex { int ID; char vname[max_name_length]; VertexStatus vtxstatus; Vertex(int id, char name[]); } Vertex; typedef struct VertexListNode { Vertex *pv; VertexListNode *pnext; VertexListNode *pprev; } VertexListNode; typedef struct VertexList { VertexListNode *pfirst; VertexListNode *plast; int num_vertices; } VertexList; /* Graph.h (3) */ typedef struct Edge { Vertex *pv1; Vertex *pv2; int dist; EdgeStatus edgestatus; Edge(Vertex *pv1, Vertex *pv2, int dist); } Edge; typedef struct EdgeListNode { Edge *pe; EdgeListNode *pnext; EdgeListNode *pprev; } EdgeListNode; typedef struct EdgeList { EdgeListNode *pfirst; EdgeListNode *plast; int num_edges; } EdgeList; ch12-24
/* Graph.h (4) */ typedef struct Graph { Vertex **vrtxptrarr; // vertex array EdgeList *adjlstarr; // adjacency list array int num_vertices; int **ppdistmtrx; Graph(int num_nodes); } Graph; void insertvertex(graph *pgrp, Vertex *pvtrx); void insertedge(graph *pgrp, Edge *pedge); void incidentedges(graph *pgrp, Vertex *pvrtx, EdgeList *pedges); void printvrtx(vertex *pv); void printedge(edge *pe); void printedges(edgelist el); void printgraph(graph *pgrp); void printlist(vertexlist *pvtl); void printlistreverse(vertexlist *pvtl); void initlist(vertexlist *pvtl); void printdistmtrx(int **distmtrx, int num_nodes); void printdist(int num_nodes, int *dist, int round); void listpushback(vertexlist *pvtl, Vertex *pv); void listpopback(vertexlist *pvtl); void listpushback(edgelist *pel, Edge *pe); void listinsertinorder(edgelist *pel, Edge *pe); #endif ch12-25