5장 스택

Size: px

Start display at page:

Download "5장 스택"

준상 독고
5 years ago
Views:

1 강의내용 오늘강의내용 ( 월 7 일 ) 중갂고사문제풀이 9. 그래프의숚회. 최소비용신장트리 ( 가중치그래프 ) 예습 ( 월 일 ) : 장가중치그래프 ( 계속 ) 숙제 : 연습문제 (9 장 ) :,,,,,7,8, 번풀어보기 마감일 : 9 년 월 일 ( 화 )

2 9. 그래프숚회 그래프숚회 주어진어떤정점을출발하여체계적으로그래프의모든정점들을방문하는것 그래프숚회의종류 깊이우선탐색 (DFS) 너비우선탐색 (BFS)

3 9.. 깊이우선탐색 () 깊이우선탐색 (Depth First Search : DFS) 수행 () 정점 i 를방문한다. () 정점 i 에인접한정점중에서아직방문하지않은정점이있으면, 이정점들을모두스택 (stack) 에저장한다. () 스택에서정점을삭제하여새로운 i 를설정하고, 단계 () 을수행한다. () 스택이공백이되면연산을종료한다. 정점방문여부를표시 : 배열 visited[n] 을이용하여표현함. visited[i] true, false, 방문하였음 방문하지않았음

4 9.. 깊이우선탐색 () DFS(i) // i 는시작정점 for (i ; i<n; i i +) do { visited[i] false; // 모든정점을방문안한것으로마크 stack createstack(); // 방문할정점을저장하는스택 push(stack, i); // 시작정점 i 를스택에저장 while (not isempty(stack)) do { // 스택이공백이될때까지반복처리 j pop(stack); if (visited[j] = false) then { // 정점 j를아직방문하지않았다면 visit j; // 직접 j를방문하고 visited[j] true; // 방문한것으로마크 for (each k adjacency(j)) do { // 정점 j에인접한정점중에서 if (visited[k] = false) then // 아직방문하지않은정점들을 push(stack, k); // 스택에저장 end DFS()

5 9.. 깊이우선탐색 () [] [] [] [] [] [] [] header null null null null null null null 그림 9. 탐색을위한그래프 G 그림 9. 그래프 G 에대한인접리스트표현

6 9.. 깊이우선탐색 () 탐색을위한그래프 G 그림 9. 그래프 G 에대한깊이우선탐색경로 ( 참고 ) G 의연결요소 : DFS() 로방문한모든정점들과이정점들에부속한 G 의간선들을모두결합하면곧그래프 G 의연결요소가된다.

7 9.. 너비우선탐색 () 너비우선탐색 (Breadth First Search ; BFS) 수행 () 정점 i 를방문한다. () 정점 i 에인접한정점중에서아직방문하지않은정점이있으면, 이정점들을모두큐 (queue) 에저장한다. () 큐에서정점을삭제하여새로운 i 를설정하고, 단계 () 을수행한다. () 큐가공백이되면연산을종료한다. 정점방문여부를표시방법 배열 visited[n] 을이용

8 9.. 너비우선탐색 () BFS(i) for (i ; i<n; i i+) do { visited[i] false; visited[i] true; queue createq(); enqueue(queue, i); while (not isempty(queue)) do { j dequeue(queue); if (visited[j] = false) then { visit j; visited[j] true; for (each k adjacency(j)) do { if (visited[k] = false) then { enqueue(queue, k); end BFS() // i 는시작정점 // 모든정점을방문안한것으로마크 // 방문할정점을저장하는큐

9 9.. 너비우선탐색 () 탐색을위한그래프 G 그림 9. 그래프 G 에대한너비우선탐색경로 ( 참조 ) 너비우선순위로만들어진연결요소는정점 i 에서정점 j 까지도달할수있는최소의간선을이용한최단경로를표현함.

10 9.. 연결요소 () 연결그래프인지의여부를판별하는방법 DFS 나 BFS 알고리즘이용함. 무방향그래프 G 에서하나의정점 i 에서시작하여 DFS(or BFS) 로방문한노드집합 V(DFS(G, i)) 가 V(G) 와같으면 G 는연결그래프. V(DFS(G, i)) = V(G) : 연결그래프, 하나의연결요소 V(DFS(G, i)) V(G) : 단절그래프, 둘이상의연결요소 연결요소찾기방법 정점 i 에대해 DFS (or BFS) 수행함. 두개이상의연결요소가있는경우에는방문하지않은나머지정점 j 에대해 DFS(or BFS) 반복수행하면연결요소를모두찾을수있음.

11 9.. 연결요소 () 연결요소를찾는알고리즘 dfscomponent(g, n) // G=(V,E), n은 G의정점수 for (i ; i <n; i i +) do { visited[i] false; for (i ; i <n; i i +) do { // 모든정점,,, n-에대해연결요소검사 if (visited[i] = false) then { print( new component ); DFS(i); // 정점 i가포함된연결요소를탐색 end dfscomponent() ( 참조 ) DFS(i) 를 BFS(i) 로대체해도무방

12 9.. 신장트리 (Spanning Tree)() 트리갂선 (tree edge) G 가연결그래프일때 DFS 나 BFS 는 G 의모든정점방문할때, G 의갂선들은 방문에사용한갂선들 ( 트리갂선 ) 과 그렇지않은갂선들 ( 비트리갂선 ) 로나뉨 트리갂선을구하는방법 방문에사용된갂선 (j, k) 의집합을 T 라할때 DFS 와 BFS 알고리즘의 for 속의 if-then 절에명령문 T T {(j, k) 삽입시켜구할수있음. T 에있는갂선들을전부결합시키면그래프 G 의모든정점들을포함한트리가됨. 이러한갂선을트리간선이라함

13 9.. 신장트리 () 신장트리 (spanning tree) 그래프 G 에서 E(G) 에있는갂선과 V(G) 에있는모든정점들로구성된트리를말함. DFS, BFS 에사용된갂선의집합 T 는그래프 G 의신장트리를의미함. 주어진그래프 G 에대한신장트리는유일하지않음 그림 9. 연결그래프 G 와신장트리 (a) 연결그래프 G (b) 신장트리

14 9.. 신장트리 () 신장트리의종류 깊이우선신장트리 (depth first spanning tree) : DFS 사용 너비우선신장트리 (breadth first spanning tree) : BFS 사용 (a) 연결그래프 G (b) DFS() 신장트리 (c) BFS() 신장트리 그림 9. 연결그래프 G 와신장트리

15 9.. 신장트리 () 비트리갂선 (nontree edge) 집합 (NT) 신장트리에사용되지않은갂선들의집합 NT 에있는임의의갂선 (i, j) 를신장트리 T 에첨가시키면그즉시사이클이만들어진다. 신장트리에비트리갂선을첨가하면더이상트리가아님 예 ) DFS() 신장트리 갂선 (, ) 첨가 :,,,,,, 으로구성된사이클형성

16 9.. 신장트리 () 최소연결부분그래프 (minimal connected subgraph) G 의부분그래프 G 중에서다음조건을만족하는그래프 () V(G ) = V(G) () E(G ) E(G) () G 는연결그래프 () G 는최소의간선수를포함 신장트리는최소연결부분그래프로서, n- 개의갂선을가짐 n 개의정점을가진연결그래프는최소한 n- 개의갂선필요 n- 개의갂선을가진연결그래프는트리임. 통신네트워크설계에응용됨. 정점이도시, 갂선이도시갂의통신링크를나타냄. 도시갂네트워크설계에서최소링크수 (n-) 로연결하는방법

17 장가중치그래프. 최소비용신장트리. 최단경로. 위상숚서. 임계경로

18 . 최소비용신장트리 가중치그래프 (Weighted Graph) 혹은네트워크 (Network) 갂선에가중치가부여된그래프 최소비용신장트리 (minimum cost spanning tree) 신장트리비용은신장트리를구성하는갂선들의가중치를합한것 이비용이최소가되는신장트리를말함. 최소비용신장트리를구하는알고리즘들 Kruskal 알고리즘 Prim 알고리즘 Sollin 알고리즘 갈망기법 (greedy method) 최적의해를단계별로구함 각단계에서생성되는중갂해법이그단계까지의상황에서는최적임. 신장트리의제한조건 가중치가부여된무방향그래프 n (n= V ) 개의갂선만사용하되사이클을생성하는갂선사용금지

19 .. Kruskal 알고리즘 () 방법 한번에하나의갂선을선택하되비용이가장작은갂선을택하여, 최소비용신장트리 T 에추가함. n 개의정점을가진그래프 G 의갂선의집합 E(G) 로부터 n- 개의갂선을선정하는것임. 비용이가장작은갂선을선정하되, 이미 T 에포함된갂선들과사이클이만들어지는것은제외시킨다. 비용이같은갂선들은임의의숚서로하나씩추가함. 구현 최소비용갂선선택 그래프 G 의갂선들을가중치에따라오름차숚으로정렬한갂선의숚차리스트유지함. 사이클검사 T 에추가로포함될정점들을연결요소별로정점그룹을만들어유지 갂선 (i, j) 가 T 에포함되기위해서는사이클이형성되지않아야함. 즉, 정점 i 와 j 가각각상이한정점그룹에속해있어야함.

20 .. Kruskal 알고리즘 () 7 G=(V, E) T={ S={{, {, {, {, {, { (a) 8 8 T={(,), (,), (,) S={{,,, {,, { (d) T={(,) S={{, {,, {, {, { (b) T={(,), (,), (,), (,) S={{,,,,, { 간선 (,) 은첨가거절 (e) T={(,), (,) S={{, {,, {,, { (c) T={(,), (,), (,), (,), (,) S={{,,,,, 간선 (,) 은첨가거절 (f) 8 그림. Kruskal 알고리즘수행단계

21 .. Kruskal 알고리즘 () Kruskal(G,n) //G=(E,V) 이고 n= V, V 는정점수 T ; edgelist E(G); // 그래프 G의갂선리스트 S {, S {,..., S n- {n-; while ( E(T) <n- and edgelist >) do { // E(T) 는 T에포함된갂선수, edgelist 는검사할갂선수 select least-cost (i, j) from edgelist; edgelist edgelist - {(i, j); // 갂선 (i, j) 를 edgelist에서삭제 if ({i, j 가동시에 S k for any k에속하지않음 ) then { T T {(i, j); // 갂선 (i, j) 를 T에첨가 S i S i S j ; // 갂선이부속된두정점그룹을합병 if ( E(T) <n-) then { print ('no spanning tree'); return T; end Kruskal()

22 .. Prim 알고리즘 () 방법 한번에하나의갂선을선택하여, 최소비용신장트리 T 를구축함. Kruskal 알고리즘과는달리구축전과정을통해하나의트리만을계속확장해나가는방법임. 구현 하나의정점 u 를트리의정점집합 V(T) 에추가 V(T) 의정점들과인접한정점들중최소비용갂선 (u, v) 를선택하여 T 에포함시키고, 새로선정된정점은 V(T) 에포함. T 가 n- 개의갂선을포함할때까지반복한다. 즉, 모든정점이 V(T) 에포함될때까지반복 항상새로선택되는갂선 (u, v) 은 u 또는 v 어느하나만 T 에속하는갂선으로서최소비용을가진갂선임. 즉, 사이클이형성되지않도록선택해야함.

23 .. Prim 알고리즘 () G=(V, E) (a) T={ V(T)={ (b) T={(,) V(T)={, (c) T={(,), (,) V(T)={,, (d) T={(,), (,), (,) V(T)={,,, (e) T={(,), (,), (,), (,) V(T)={,,,, (f) 그림. Prim 알고리즘의수행단계 T={(,), (,), (,), (,), (,) V(T)={,,,,, (g) 8

24 .. Prim 알고리즘 () Prim(G, i) T ; V(T) = { i ; while ( T < n-) do { // i는시작정점 // 최소비용신장트리 // 신장트리의정점 if (select least-cost (u, v) such that u V(T) and v V(T) then { T T {(u, v); V(T) V(T) {v; else { print( no spanning tree ); return T; return T; end Prim()

25 .. Sollin 알고리즘 () 방법 한단계마다여러개의갂선을선택하면서최소비용신장트리를구축해나가는방법임. 구축과정중에두개의트리가하나의동일한갂선을중복으로선정할경우, 하나의갂선만사용하고중복된또다른갂선은사용하지않음. 구현 그래프의각정점하나만을포함하는 n 개의트리로구성된신장포리스트 (forest) 에서부터시작 매번포리스트에있는각트리마다하나의갂선을선택 선정된갂선들은각각두개의트리를하나로결합시키면서신장트리로확장해나감. n- 개의갂선으로된하나의트리가만들어지거나, 더이상선정할갂선이없을때종료함.

26 .. Sollin 알고리즘 () G=(V, E) 8 (a) 8 (b) (c) 그림. Sollin 알고리즘의수행단계

27 .. Sollin 알고리즘 () Sollin(G, n) S {; S {;,..., S n- {n-; T ; List ; while ( T < n- and Edges ) do { for (each S i ) do { // G = (V, E), n = V // n개의노드그룹으로초기화 // 최소비용신장트리 // 연산단계에서선정된간선 select least-cost (u, v) from Edges such that u S i and v S i ; if ((u, v) List) then List List {(u, v); // 중복간선은제거 while (List ) do { remove (u, v) from List; if ({u, v S u or {u, v S v ) then { T T {(u, v); S u S u S v ; Edges Edges {(u, v); if (( T < n-) then { print( no spanning tree ); return T; end Sollin() // List 가공백이될때까지 // S u 와 S v 는각각정점 u 와 v 가포함된트리

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]