그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문

Presentation on theme: "그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문"— Presentation transcript:

1 그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
(2) v에 인접하고 방문하지 않은 한 정점 w를 선택 (3) w를 시작점으로 다시 깊이 우선 탐색 시작 (4) 모든 인접 정점을 방문한 정점 u에 도달하면, 최근에 방문한 정점 중 아직 방문을 안한 정점 w와 인접하고 있는 정점으로 되돌아감 (5) 정점 w로부터 다시 깊이 우선 탐색 시작 (6) 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료

2 깊이 우선 탐색(1/3) #define FALSE 0 #define TRUE 1
short int visited[MAX_VERTICES]; void dfs (int v) {/* 그래프의 정점 v에서 시작하는 깊이 우선 탐색 */ nodePointer w; visited[v] = TRUE; printf(“%5d”, v); for (w = graph[v]; w; w = w → link) if (!visited [w→vertex]) dfs (w→vertex); } 깊이-우선 탐색

3 깊이 우선 탐색(2/3) 예제 6.1 0, 1, 3, 7, 4, 5, 2, 6 순으로 방문 [0] [1] [2] [3] [4]
1 2 3 4 5 6 7 adjLists ( a) [0] [1] [2] [3] [4] [5] [6] [7] 1 2 3 4 5 6 1 7 1 7 2 7 2 7 3 4 5 6 (b) 그래프 G와 그 인접리스트

4 깊이 우선 탐색(3/3) DFS의 분석 탐색을 끝내는 시간 O (e) v에 인접한 모든 정점들을 찾는데 O (n)의 시간

5 너비 우선 탐색(1/2) 너비 우선 탐색(BFS; Breadth-First Search) 예제 6.2 시작 정점 v를 방문
새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문 예제 6.2 0, 1, 2, 3, 4, 5, 6, 7 순으로 방문 1 2 3 4 5 6 7

6 너비 우선 탐색(2/2) BFS의 분석 전체 시간 O(n2) 인접 리스트 표현 : 전체 비용 O(e)
void bfs(int v) {/* 정점 v에서 시작하는 너비 우선 탐색. 전역배열 visited는 0으로 초기화됨} node_pointer w; queue_pointer front, rear; front = rear = NULL; /* 큐의 초기화 */ printf(“%5d”, v); visited[v] = TRUE; addq(&front, &rear, v); while (front){ v = deleteq(&front); for (w=graph[v]; w; w=w→link) if (!visited[w→vertex]) { printf(“%5d”, w→vertex); addq(&front, &rear, w→vertex); visited[w→vertex] = TRUE; } BFS의 분석 전체 시간 O(n2) 인접 리스트 표현 : 전체 비용 O(e)

7 신장트리(1/2) 신장트리(spanning tree) : G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리
깊이-우선 신장트리(depth-first spanning tree) 너비-우선 신장트리(breadth-first spanning tree) 완전 그래프와 이 그래프의 세 신장트리 1 2 1 2 3 4 5 6 3 4 5 6 7 7 (a) DFS(0) 신장 트리 (b) BFS(0) 신장 트리

8 최소비용 신장트리 최소비용 신장트리(minimum-cost spanning tree)
최저의 비용을 갖는 신장트리 Kruskal, Prim, Sollin 알고리즘 갈망법(greedy method) 최적의 해를 단계별로 구한다 각 단계에서는 몇 개의 판단 기준에 따라 최상의 결정을 내린다 한번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해낼 수 있는 지 확인 신장트리의 제한 조건 (1) 그래프내에 있는 간선들만을 사용 (2) 정확하게 n-1개의 간선만을 사용 (3) 사이클을 생성하는 간선을 사용 금지

9 Kruskal 알고리즘(1/3) 알고리즘 한번에 하나씩 T에 간선을 추가해가면서 최소비용 신장트리 T를 구축
G는 연결되어 있고 n>0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함됨.

10 Kruskal 알고리즘(2/3) 예제 6.3 Kruskal 알고리즘의 각 단계 28 10 1 10 10 1 1 1 14 5 5
28 10 1 10 10 1 1 1 14 5 5 16 5 5 6 2 24 6 6 2 2 6 2 25 4 4 18 4 4 12 12 3 22 3 3 3 ( d) ( a) ( b) ( c) 10 10 10 10 1 1 1 1 14 14 14 14 5 16 5 16 5 5 16 6 6 6 6 2 2 2 2 25 4 4 4 4 12 12 12 12 22 3 22 3 3 3 ( g) ( h) ( e) ( f) Kruskal 알고리즘의 각 단계

11 Kruskal 알고리즘(3/3) T = { }; while ((T가 n-1개 미만의 간선을 포함) && (E가 공백이 아님)) { E에서 최소 비용 간선 (v,w) 선택; E에서 (v,w)를 삭제; if (v,w)가 T에서 사이클을 만들지 않으면 add (v, w) to T; else discard (v,w); } if (T가 n-1개 미만의 간선을 포함) cout << "신장 트리 없음" << endl; Kruskal 알고리즘 정리 6.1 G를 무방향 연결 그래프라 하자. Kruskal 알고리즘은 최소비용 신장트리를 생성한다.

12 Prim 알고리즘(1/3) 알고리즘 한번에 한 간선씩 최소 비용 신장 트리를 구축 각 단계에서 선택된 간선의 집합은 트리
하나의 정점으로 된 트리 T에서 시작 최소 비용 간선 (u,v)를 구해 T U {(u,v)}이 트리가 되면 T에 추가 T에 n-1개의 간선이 포함될 때까지 간선의 추가 단계를 반복 추가된 간선이 사이클을 형성하지 않도록 각 단계 에서 간선 (u,v)를 선택할 때 u 또는 v중 오직 하나만 T에 속한 것을 고른다.

13 Prim 알고리즘(2/3) Prim 알고리즘 T = { }; TV ={0}; /* 정점 0으로 시작. 간선은 비어 있음.*/
while(T의 간선수가 n-1보다 적음) { u ∈ TV이고 v ∈ TV인 최소 비용 간선을 (u, v)라 함; if (그런 간선이 없음) break; v를 TV에 추가; (u, v)를 T에 추가; } if (T의 간선수가 n-1보다 적음) printf ("신장트리 없음\n“); Prim 알고리즘

14 Prim 알고리즘(3/3) Prim 알고리즘의 진행 단계 10 1 10 1 10 1 5 5 5 6 6 6 2 2 2 25 25
10 1 10 1 10 1 5 5 5 6 6 6 2 2 2 25 25 4 4 4 22 3 3 3 (a) (b) (c) 10 1 10 1 10 1 14 16 16 5 5 5 6 6 6 2 2 2 25 25 25 4 4 4 12 12 12 22 22 22 3 3 3 (d) (e) (f) Prim 알고리즘의 진행 단계

15 Sollin 알고리즘 알고리즘 각 단계에서 여러개의 간선을 선택
각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선 선택된 간선은 구축중인 신장트리에 추가 오직 하나의 트리만이 존재 or 더 이상 선택할 간선이 없을 때 종료 10 1 10 1 14 14 16 5 5 6 6 2 2 25 4 4 12 12 22 22 3 3 (a) (b) Sollin 알고리즘의 단계들