강의 #9 그래프(Graph).

Presentation on theme: "강의 #9 그래프(Graph)."— Presentation transcript:

1 강의 #9 그래프(Graph)

2 그래프 그래프(graph) 그래프 이론(graph theory): 그래프를 문제해결의 도구로 이용하는 연구분야
연결되어 있는 객체간의 관계를 표현하는 자료구조 아주 일반적인 자료구조 트리도 그래프의 일종으로 볼수 있다 그래프의 예: 전기회로, 프로젝트관리, 지도에서 도시들의 연결 그래프 이론(graph theory): 그래프를 문제해결의 도구로 이용하는 연구분야

3 그래프 역사 1800년대 오일러에 의하여 창안 오일러 문제: 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제
문제의 핵심만을 표현 위치: 정점(node) 다리: 간선(edge) 오일러 경로: 정점에 연결된 간선의 개수가 짝수이면 존재

4 그래프 용어 (1) 그래프는 (V, E)로 표시된다 (예) 예제 그래프 V는 정점(vertices)들의 집합
E는 간선(edge)들의 집합 정점과 간선은 모두 관련되는 데이터를 가질 수 있다. (예) 예제 그래프 정점은 각 도시를 의미한다. 간선은 도시를 연결하는 도로를 의미한다. 간선에는 도로의 길이 등의 데이터가 저장될 수 있다.

5 그래프 용어 (2) 인접 정점(adjacent vertex) : 차수(degree) : 경로(path):
간선에 의해 연결된 정점 정점 0와 정점 1 차수(degree) : 하나의 정점에 연결된 다른 정점의 개수 진입차수(in-degree)/진출차수(out-degree) 정점 0의 차수는 3 경로(path): 정점의 나열로 표현 단순경로: 0, 1, 2, 3 사이클(cycle): 0, 1, 2, 0 경로의 길이 : 경로를 구성하는데 사용된 간선의 수

6 그래프 용어 (3) 부분 그래프 : 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프 그래프 G1의 부분 그래프: 완전그래프 : 모든 정점이 연결되어 있는 그래프 3 1 2 3 1 2

7 그래프의 종류 간선의 종류에 따라 그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분 무방향 간선: 간선을 통해서 양방향으로 갈수 있음을 나타내며 (A, B)와 같이 정점의 쌍으로 표현 (A, B) = (B, A) 방향간선: 방향성이 존재하는 간선으로 도로의 일방 통행길과 마찬가지로 한쪽 방향으로만 갈 수 있음을 나타낸다. <A, B>로 표시한다. <A, B> ≠ <B, A> 가중치 그래프(weighted graph), 네트워크(network): 간선에 비용이나 가중치가 할당된 그래프 A B A B 1200 A B

8 그래프 표현의 예 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(G3)= {(0, 1), (0, 2))} V(G2)= {0, 1, 2},         E(G2)= {<0, 1>, <1, 0>, <1, 2>}

9 그래프 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 연산을 사용한다.

10 그래프 표현 방법 (1) 그래프를 표현하는 2가지 방법 인접 행렬 방법
인접 행렬(adjacent matrix): 2차원 배열 사용 표현 인접 리스트(adjacency list): 연결리스트를 사용 표현 인접 행렬 방법 If (간선 (i, j)가 그래프에 존재)    M[i][j] = 1, 그렇지않으면                             M[i][j] = 0.

11 그래프 표현 방법 (2) 인접 리스트 방법 각 정점에 인접한 정점들을 연결 리스트로 표현

12 그래프 탐색 (1) 그래프 탐색은 그래프의 가장 기본적인 연산 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문
많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결 (예) 특정한 정점에서 다른 정점으로 갈 수 있는지 없는지 (예) 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 연결되어 있지 않은지를 탐색을 통하여 알 수 있다.

13 그래프 탐색 (2) 그래프 탐색의 2가지 방법 깊이우선탐색(DFS: depth-first search) 너비우선탐색(BFS: breadth-first search) 깊이 우선 탐색은 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

14 DFS 알고리즘 (1) depth_first_search(v) v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then depth_first_search(u)

15 DFS 알고리즘 (2) } // 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType *g, int v) { int w; visited[v] = TRUE; // 정점 v의 방문 표시 printf("%d ", v); // 방문한 정점 출력 for(w=0; w<g->n; w++) // 인접 정점 탐색 if( g->adj_mat[v][w] && !visited[w] ) dfs_mat(g, w); //정점 w에서 DFS 새로시작 } // 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 void dfs_list(GraphType *g, int v) { GraphNode *w; visited[v] = TRUE; // 정점 v의 방문 표시 printf("%d ", v); // 방문한 정점 출력 for(w=g->adj_list[v]; w; w=w->link) // 인접 정점 탐색 if(!visited[w->vertex]) dfs_list(g, w->vertex); //정점 w에서 DFS 새로시작 }

16 너비우선탐색(BFS) 너비 우선 탐색은  시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 큐를 사용하여 구현됨

17 BFS 알고리즘 (1) breadth_first_search(v) v를 방문되었다고 표시; 큐 Q에 정점 v를 삽입;
while (not is_empty(Q)) do Q에서 정점 w를 삭제; for all u ∈ (w에 인접한 정점) do if (u가 아직 방문되지 않았으면) then u를 큐에 삽입; u를 방문되었다고 표시;

18 BFS 알고리즘 (2) void bfs_mat(GraphType *g, int v) { int w; QueueType q;
init(&q); // 큐 초기화 visited[v] = TRUE; // 정점 v 방문 표시 printf("%d ", v); enqueue(&q, v); // 시작 정점을 큐에 저장 while(!is_empty(&q)){ v = dequeue(&q); // 큐에 정점 추출 for(w=0; w<g->n; w++) // 인접 정점 탐색 if(g->adj_mat[v][w] && !visited[w]) { visited[w] = TRUE; // 방문 표시 printf("%d ", w); enqueue(&q, w); // 방문한 정점을 큐에 저장 }

19 프로그램 실습 #1 깊이우선탐색 및 너비우선탐색을 구현하고 테스트한다 깊이우선탐색은 인접 행렬로 구현된 그래프에 적용
너비우선탐색은 인접 리스트로 구현된 그래프에 적용

20 연결성분찾기 최대로 연결된 부분 그래프들을 찾는 것 그래프 탐색으로 찾을 수 있다. visited[i]=count;
void find_connected_component(GraphType *g) { int i; count = 0; for(i=0; i<g->n; i++) if(!visited[i]){ // 방문되지 않았으면 count++; dfs_mat(g, i); }

21 신장 트리 신장 트리(spanning tree): 그래프내의 모든 정점을 포함하는 트리
신장 트리는 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안 된다.

22 신장 트리 알고리즘 적용하는 탐색 알고리즘에 따라 신장 트리의 용도 깊이 우선 신장 트리 너비 우선 신장 트리
depth_first_search(v) v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then (v,u)를 신장 트리 간선이라고 표시; depth_first_search(u) 적용하는 탐색 알고리즘에 따라 깊이 우선 신장 트리 너비 우선 신장 트리 신장 트리의 용도 통신 네트워크 구축: 최소의 링크를 사용하여 네트워크를 구축하고 싶은 경우

23 최소비용신장트리(MST) 최소비용신장트리(MST: minimu spanning tree): 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 신장트리 MST의 응용 도로 건설 - 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제 전기 회로 - 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제 통신 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 배관 - 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

24 MST 알고리즘 2가지의 대표적인 알고리즘 탐욕적인 방법(greedy method) Kruskal의 알고리즘
Prim의 알고리즘 탐욕적인 방법(greedy method) 알고리즘 설계에서 있어서 중요한 기법 중의 하나 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달 탐욕적인 방법은 항상 최적의 해답을 주는지를 반드시 검증해야 한다. Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명

25 Kruskal의 MST 알고리즘 (1) 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여,  각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가한다. 만약 사이클을 형성하면 그 간선은 제외된다.

26 Kruskal의 MST 알고리즘 (2)

27 Kruskal의 MST 알고리즘 (3)

28 Kruskal의 MST 알고리즘 (4) union-find 알고리즘 Kruskal의 MST 알고리즘의 구현
집합들의 합집합을 구하고 집합의 원소가 어떤 집합에 속하는지를 계산하는 알고리즘 여러가지 방법으로 구현이 가능하다 Kruskal의 MST 알고리즘에서 사이클 검사에 사용된다. a와 b가 같은 집합에 속함 a와 b가 다른 집합에 속함

29 프로그램 실습 #2 Union-find 알고리즘을 이용한 Kruskal 최소 비용 신장 트리 알고리즘을 구현하고 테스트하여라.

30 Prim의 MST 알고리즘 (1) Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함 앞 단계에서 만들어진 신장 트리 집합에, 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장 이 과정은 트리가 n-1개의 간선을 가질 때까지 계속된다. 간선 (a, b)와 간선 (f, e)의 가중치를 비교해보면 (f, e)가 27로서 (a, b)의 29보다 높다. 따라서 (f, e) 간선이 선택되고 정점 e가 신장 트리 집합에 포함된다.

31 Prim의 MST 알고리즘 (2)

32 Prim의 MST 알고리즘 (3)

33 Prim의 MST 알고리즘 (4)

34 프로그램 실습 #3 Prim의 최소 비용 스패닝 트리 알고리즘을 구현하고 테스트하여라.

35 최단경로 알고리즘 최단 경로(shortest path) 문제 간선의 가중치는 비용, 거리, 시간 등을 나타낸다.
네트워크에서 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제 간선의 가중치는 비용, 거리, 시간 등을 나타낸다.

36 Dijkstra의 최단 경로 알고리즘 (1) Dijkstra의 최단 경로 알고리즘은 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 집합 S: 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합 distance 배열: 최단 경로를 알려진 정점만을 통하여 각 정점까지 가는 최단경로의 길이 매 단계에서 가장 distance 값이 적은 정점을 S에 추가한다.

37 Dijkstra의 최단 경로 알고리즘 (2) 매 단계에서 새로운 정점이 S에 추가되면 distance값을 갱신한다.

38 Dijkstra의 최단 경로 알고리즘 (3) // 입력: 가중치 그래프 G, 가중치는 음수가 아님.
// 출력: distance 배열, distance[u]는 v에서 u까지의 최단 거리이다. shortest_path(G, v) S←{v} for 각 정점 w∈G do distance[w]←weight[v][w]; while 모든 정점이 S에 포함되지 않으면 do u←집합 S에 속하지 않는 정점 중에서 최소 distance 정점; S←S∪{u} for u에 인접하고 S에 있는 각 정점 z do if distance[u]+weight[u][z] < distance[z] then distance[z]←distance[u]+weight[u][z];

39 Dijkstra의 최단 경로 알고리즘 (4)

40 Dijkstra의 최단 경로 알고리즘 (5)

41 프로그램 실습 #4 Dijkstra의 최단 경로 알고리즘을 구현하고 테스트하여라.

42 Floyd 최단경로 알고리즘 (1) Floyd의 최단 경로 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아주는 알고리즘 Floyd의 최단 경로 알고리즘은 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성 위의 알고리즘을 설명하기 위하여 Ak[i][j]를 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로라고 하자. 우리가 원하는 답은 An-1[i][j]가 된다. A-1→A0 → A1 → … → An-1순으로 최단 거리를 구한다. floyd(G) for k ← 0 to n - 1 for i ← 0 to n - 1 for j ← 0 to n - 1 A[i][j] = min(A[i][j], A[i][k] + A[k][j])

43 Floyd 최단경로 알고리즘 (2) 먼저 Ak-1까지는 완벽한 최단 거리가 구해져서 있다고 가정하자. 일반적으로 k번째 정점이 추가로 고려되는 상황을 생각하여 보자. 0부터 k까지의 정점만을 사용하여 정점 i에서 정점 j로 가는 최단 경로는 다음의 2가지의 경우로 나누어서 생각할 수 있다. (1) 정점 k를 거쳐서 가지 않는 경우:      k보다 큰 정점은 통과하지 않으므로 이경우 최단 거리는 Ak-1[i][j]가 된다. (2) 정점 k를 통과하는 경우:    i에서 k까지의 최단거리 Ak-1[i][k]에다가 k에서 j까지의 최단거리인 Ak-1 [k][j]를 더한 값이 될 것이다.

44 위상정렬 (1) 위상정렬(topological sort): 방향 그래프에서 간선 <u, v>가 있다면 정점 u는 정점 v를 선행한다고 말한다. 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상 정렬(topological sort)이라고 한다. 과목번호 과목명 선수과목 전산학개론 없음 1 이산수학 2 자료구조 3 알고리즘 분석 0, 1, 2 4 운영체제 5 인공지능 2, 3, 4 위상정렬: (0,1,2,3,4,5) , (1,0,2,3,4,5) (2,0,1,3,4,5)는 위상 정렬이 아니다. 왜냐하면 2번 정점이 0번 정점 앞에 오기 때문이다. 간선 <0, 2>이 존재하기 때문에 0번 정점이 끝나야 만이 2번 정점을 시작할 수 있다.

45 위상정렬 (2)

46 위상정렬 (3) Input: 그래프 G=(V,E) Output: 위상 정렬 순서 topo_sort(G)
for i←0 to do if( 모든 정점이 선행 정점을 가지면 ) then 사이클이 존재하고 위상 정렬 불가; 선행 정점을 가지지 않는 정점 v 선택; v를 출력; v와 v에서 나온 모든 간선들을 그래프에서 삭제;

47 프로그램 실습 #5 위상 정렬 알고리즘을 구현하고 테스트하여라.