•학습목차 1. 그래프 ... - dblab.duksung.ac.kr

1 < C >1 10 . 1. 2. 3. < C >21. graph? chart?< C >3 K enigsberg . (A,B,C,D) a f ? .. cdeabfgAKneiphofCBDcabdegfCABDK nigsberg < C >41. : G = (V,E) , V,E .V(G) : (set of vertices)E(G) : (set of edges), , V X V (undirected graph) .- (undirected, unordered). (vi,vj) = (vj,vi) . (directed graph) . - (directed, ordered). <vi,vj> <vj,vi> < C >5.

2 0132G10123465G2210G3 1) G1V(G1) = {0,1,2,3}E(G1) = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} G2V(G2) = {0,1,2,3,4,5,6}E(G2) = {(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)} G3V(G3) = {0,1,2}E(G3) = {<0,1>,<1,0>,<1,2>} < C >60132H14567H2 2) G4V(G4) = {0,1,2,3,4,5,6,7}E(G4) = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),(4, 5),(5,6),(6,7)}G4< C >7 1) .(no self loop)no edge from a vertex, i, back to itself, no (vi,vi) or <vj,vi>2) .(not multigraph)no multiple occurrences of the same edge0122103(a)(b) a) self loops, b) multigraph< C >8 (1) (complete graph).

3 3 3 , 4 6 . n ? .* n n(n-1)/2* n n(n-1)(2) (adjacent)- a, b (a,b) , a b (adjacent) .(3) (incident)- a, b (a,b) , (a,b) a b (incident) .< C >9 ) (v0,v1) : - v0 v1 (adjacent) .- (v0,v1) v0 v1 (incident) . ) <v0,v1> : - v0 v1 (adjacent) . - v1 v0 (adjacent) .- <v0,v1> v0 v1 (incident) .< C >10(4) (subgraph) G of G :-V(G ) V(G) and-E(G ) E(G)00123120312(i)(ii)(iii)(iv)(a) G1 210210100(i) (ii)(iii)(iv)(b) G3 0132G1210G3< C >11(5) (path) : vp vq - vp, v1, v2, v3, , vn, vq vp vq.

4 (vp,vi)), (v1,v2), ,(vn,vq)- .<vp,v1>, <v1,v2>, ,<vn,vq>(6) : -(vp,vi1),(vi1,vi2), ,(vin,vq) n+1 .(7) (simple path)- , .(8) (cycle)- , . - (directed cycle) .(9) (connected)- v0 v1 G v0 v1 .. < C >12(10) (connected component)- , . connected component .(maximal connected subgraph)0132H14567H2G4 (11) (tree).

5 1 .. < C >13(12) ( strongly connected, strongly connected component in a directed graph)- : vi, vjin V(G) vito vj vjto vi .- (strongly connected component in a directed graph) , vi, vjin V(G) vito vj vjtovi .(maximal subgraph that is strongly connected)2134 102G3 (strongly connected components)(13) (degree of vertex)- (incident) - in-degree (of vertex v) : - out-degree (of vertex v) : Q/A < C >14 (1)Vertex edge ?

6 (2) .(3)5 ?(4)6 1 ?< C >152. (1) (adjacency matrix)- G = (V,E), |V| = n( 1) .adj_mat[i][j] = 1 : if (vi, vj) (adjacent)0 : - = (space complexity) : S(n) = n2- (symmetric) . G1, G3, and G401 2 3001 1 1110 1 1211 0 1311 1 001 2001 0110 1200 0012345670 011100001 101100002 110100003 111000004 000001005 000010106 000001017 000000100132G1210G30132H14567H2G4< C >16(2) (adjacency lists)n .. n .#define MAX_VERTICES 50struct list_node {int vertex;struct list_node * link;};typedef struct list_node node;typedef node * node_ptr;node_ptr graph[MAX_VERTEX];vertex link< C >172132031031020123graph vertex link120012 G1 G30123456710005456333267 G422110132G1210G30132H14567H2< C >18 1: (inverse) 012101G3 2: 2.

7 Tailheadcolumn link for headrow link for tail012012000 (headnodes) G3 (2) (adjacency lists)210G3< C >19 3: (weighted edges)- (weights) ..1) 2) - .Q/A < C >20 (1) (2) < C >213. : . traversal ( )insert ( )delete ( )isempty ( )isfull( ) = + .. (traversal) . 1 . (insert), (delete).

8 < C >22- (traversal) .- .- . DFS (Depth First Search) - . (preorder tree traversal) BFS (Breath First Search) - .(level order tree traversal) (graph traversals)< C >233. 0123456710011223235777744656(b) G (adjacency lists)V0V1V2V3V4V5V6V7(a) G< C >24(1) - (depth first search) : . , ..1 : .2.

9 2 . 3 .3 : 2) . : - .- visited[MAX_VERTICES] . FALSE TRUE#define FALSE 0#define TRUE 1short int visited[MAX_VERTICES];< C >25 01234567 visitedV0V1V2V3V4V5V6V7 : : (1) - (depth first search)V0V1V0V3V1V0V7V4V3V1V0V7V3V1V0V7 < C >26/* (depth first search) *//* v */void dfs(int v) {node_ptr w;visited[v] = TRUE; /* 1 */printf( %5d , v);for(w = graph[v]; w; w = w->link) /* 2 */if(!visited[w->vertex])dfs(w->vertex); }* (depth first search) -> (time complexity) : O(e), e (depth first search)< C >27(2) - (breadth first search).

10 1 1 ..1 : . 2 : .. 3 .3 : 2 . : - .- visited[MAX_VERTICES] . FALSE TRUE#define FALSE 0#define TRUE 1short int visited[MAX_VERTICES];< C >28 V0V1V2V3V4V5V6V7 01234567 visited : (breadth first search) < C >29 V1V2V2V3V4V3V4V5V6V4V5V6V7V5V6V7V6V7V7V1 V2V3V4V5V6V0V7< C >30/* (breadth first search) *//* v */void bfs(int v) {node_ptr w; queue_ptr front, rear;front = rear = NULL;/* initialize queue */printf( %5d , v);visited[v] = TRUE; /* 1 */insert(&front, while(front) /* 2 */{ v = delete( for(w = graph[v]; w; w = w->link;if(!))))}}