자료구조론 10장 그래프(graph).

Presentation on theme: "자료구조론 10장 그래프(graph)."— Presentation transcript:

1 자료구조론 10장 그래프(graph)

2 이 장에서 다룰 내용 그래프의 구조 그래프의 구현 그래프 순회 신장 트리와 최소비용 신장 트리

3 그래프 그래프(graph) 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것으로서, 정점은 대상을 나타내고, 간선은 대상들 간의 관계를 나타냄 그래프 G = (V, E) V는 정점들의 집합 E는 간선들의 집합 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계를 가지는 원소들을 표현할 수 있다. 그래프의 예

4 그래프 종류 무방향 그래프(undirected graph) 정점 사이의 간선에 방향이 없는 그래프
정점 Vi와 정점 Vj 사이의 간선을 (Vi, Vj)로 표현 (Vi, Vj)와 (Vj, Vi)는 동일한 간선을 나타냄 예) G1: V(G1)={A, B, C, D} E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D)} A B C D |V| 집합 V의 크기 |E| 집합 E의 크기 V(G) : 그래프 G의 정점 집합 E(G) : 그래프 G의 간선 집합

5 그래프 종류 방향 그래프(directed graph) , 다이그래프(digraph) 간선이 방향을 가지고 있는 그래프
정점 Vi에서 정점 Vj를 연결하는 간선 즉, Vi→Vj를 <Vi, Vj>로 표현 Vi를 꼬리(tail), Vj를 머리(head)라고 한다. <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선을 나타냄 예) G3: V(G3)={A, B, C, D} E(G3)={<A,B>, <A,D>, <B,C>, <B,D>, <C,D>} A B C D

6 그래프 종류 완전 그래프(complete graph) 각 정점에서 다른 모든 정점으로의 간선이 존재하는 그래프
주어진 정점 수에 대해 간선 수가 최대임 정점이 n개인 완전 그래프 간선 수 undirected graph : n(n-1)/2개 directed graph : n(n-1)개 완전 그래프의 예

7 그래프 종류 가중 그래프(weighted graph) , 네트워크(network)
예) A B C D A B C D 3 5 4 2 10 2 9 3 3 6

8 그래프 용어 인접(adjacent), 부속(incident)
그래프에서 두 정점 Vi과 Vj를 연결하는 간선 (Vi, Vj)가 존재하면, 두 정점 Vi와 Vj는 인접하다고 함 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속되어 있다고 함 예) 정점 A와 인접한 정점은 B와 D 정점 A에 부속되어있는 간선은 (A,B)와 (A,D) A B D C

9 그래프 용어 차수(degree) : 정점에 부속된(incident) 간선의 수 예) 정점 A의 차수는 2,
정점 B의 차수는 3 방향 그래프의 정점의 차수 = 진입차수(in-degree) + 진출차수(out-degree) (진입차수 1 + 진출차수 2) A B C D A B C D

10 그래프 용어 경로(path) : 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것
: 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것 즉, Vi에서 Vj까지의 경로란 정점 Vi에서 Vj까지 간선으로 연결된 정 점을 순서대로 나열한 리스트 예) 정점 A에서 정점 C까지의 경로: A-B-C, A-B-D-C, A-D-C, ... 경로길이(path length) : 경로를 구성하는 간선의 수 단순경로(simple path) : 모두 다른 정점으로 구성된 경로(시작과 마 지막 정점은 동일할 수 있음) A-B-C는 단순경로, A-B-D-A-B-C는 단순경로가 아님 사이클(cycle) : 단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로 A-B-C-D-A는 사이클 A B C D

11 그래프 용어 DAG(directed acyclic graph) 방향 그래프이면서 사이클이 없는 그래프 예)
DAG DAG 아님 : 사이클 A-B-D-A A A B D B D C C

12 그래프 용어 연결(connected) 연결 그래프(connected graph)
정점 Vi에서 Vj까지 경로가 있으면 Vi와 Vj가 연결되었다고 함 연결 그래프(connected graph) 모든 쌍의 정점들 사이에 경로가 있는 그래프 예) 다음 중 연결 그래프인 것은? A B C D A B C D A B C D A B C D

13 그래프 용어 부분 그래프(subgraph) 원래의 그래프에서 정점이나 간선의 일부를 취해 만든 그래프
그래프 G와 부분 그래프 G'의 관계 V(G')⊆V(G),  E(G')⊆E(G) 그래프 G1의 부분 그래프 3가지 예 G1: A B C D A B C D A C D A B D

14 그래프 그래프 추상 자료형 ADT Graph 데이터 : 공백이 아닌 정점의 집합과 간선의 집합 연산 :
g∈Graph; u,v∈V; createGraph() ∷= create an empty Graph; // 공백 그래프의 생성 연산 isEmpty(g) ∷= if (g have no vertex) then return true; else return false; // 그래프 g가 정점이 없는 공백 그래프인지를 검사하는 연산 insertVertex(g, v) ∷= insert vertex v into g; // 그래프 g에 정점 v를 삽입하는 연산 insertEdge(g, u, v) ∷= insert edge (u,v) into g; // 그래프 g에 간선 (u,v)를 삽입하는 연산 deleteVertex(g, v) ∷= delete vertex v and all edges incident on v from g; // 그래프 g에서 정점 v를 삭제하고 그에 부속된 모든 간선을 삭제하는 연산 deleteEdge(g, u, v) ∷= delete edges (u,v) from g; // 그래프 g에서 간선 (u,v)를 삭제하는 연산 adjacent(g, v) ∷= return set of all vertices adjacent to v; // 정점 v에 인접한 모든 정점을 반환하는 연산 End Graph [ADT 10-1] [ADT 8-1]

15 그래프의 구현 그래프를 구현하는 방법 0 1 1 0 0 1 0 0 0 인접 행렬(adjacency matrix)
인접 리스트(adjacency list) 1 2 3 1 2 3 1 2 3 2 3 1 2 3 3

16 그래프의 구현 인접 행렬(adjacency matrix) 행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법
그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장 정점이 n개일 때, n x n 정방행렬 A Aij : 두 정점이 인접하면 1, 아니면 0 무방향 그래프의 인접 행렬 i행의 합 = i열의 합 = 정점 i의 차수 방향 그래프의 인접 행렬 i행의 합 = 정점 i의 out-degree i열의 합 = 정점 i의 in-degree 인접 행렬 표현의 단점 정점이 n개이면 항상 n x n개의 메모리 사용 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프의 경우, 인접 행렬이 희소 행렬임 메모리 낭비 그래프 연산 수행 시간면에서도 비효율적

17 그래프의 구현

18 그래프의 구현 인접 리스트(adjacency list) G = (V, E)에 대해 |V| = n, |E|=e 라고 하자.
각 정점에 대한 인접 정점들을 연결 리스트에 저장 하나의 그래프를 표현하기 위해 n개의 연결 리스트를 둠 인접 리스트의 노드 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크  필드 로 구성 리스트의 헤드 노드 정점에 대한 리스트의 시작을 표현 크기가 n인 헤드 노드 배열을 둠 무방향 그래프의 인접 리스트 노드의 수 : 2e 각 정점에 대한 리스트의 노드의 수 : 정점의 degree 방향 그래프의 인접 리스트 연결하는 노드의 수 : e 각 정점에 대한 리스트의 노드의 수 : 정점의 out-degree

19 그래프의 구현 인접 리스트 예)

20 그래프의 구현 인접 행렬, 인접 리스트로 구현한 그래프 프로그램
문제를 간단히 하기 위해 정점 수가 n이면 V = {0, 1, 2, ..., n-1}로 가정; insertVertex 메소드는 이용하지 않음 public class Ex10_1{ public static void main(String args[]) { AdjMatrix mg = new AdjMatrix(4); mg.insertEdge(0,3); mg.insertEdge(0,1); mg.insertEdge(1,3); mg.insertEdge(1,2); mg.insertEdge(1,0); mg.insertEdge(2,3); mg.insertEdge(2,1); mg.insertEdge(3,2); mg.insertEdge(3,1); mg.insertEdge(3,0); System.out.println("그래프 G1의 인접행렬 : "); mg.printMatrix(); AdjList graph2 = new AdjList(4); lg.insertEdge(0,3); lg.insertEdge(0,1); lg.insertEdge(1,3); lg.insertEdge(1,2); lg.insertEdge(1,0); lg.insertEdge(2,3); lg.insertEdge(2,1); lg.insertEdge(3,2); lg.insertEdge(3,1); lg.insertEdge(3,0); System.out.println("그래프 G1의 인접리스트 : "); lg.printAdjList(); } [예제 10-1]

21 그래프의 구현 public class AdjMatrix{ private int[][] matrix;
private int totalV; public AdjMatrix(int totalV) { this.matrix = new int[totalV][totalV]; this.totalV = totalV; } public void insertEdge(int v1, int v2){ if(v1>=totalV || v2>=totalV) System.out.println("그래프에 없는 정점입니다!"); else matrix[v1][v2] = 1; public void printMatrix(){ for(int i=0; i<totalV; i++){ for(int j=0; j<totalV; j++) System.out.print(matrix[i][j] + " "); System.out.println(); [예제 10-1]

22 그래프의 구현 public class AdjList{ private GraphNode[] head;
private int totalV; public AdjList(int totalV) { this.head = new GraphNode[totalV]; this.totalV = totalV; } public void insertEdge(int v1, int v2) { if(v1>=totalV || v2>=totalV) System.out.println("그래프에 없는 정점입니다!"); else{ GraphNode newNode = new GraphNode(); newNode.vertex = v2; newNode.link = head[v1]; head[v1] = newNode; [예제 10-1]

23 그래프의 구현 public void printAdjList() { GraphNode temp;
for(int i=0; i<totalV; i++) { System.out.print("정점 " + i + "의 인접리스트"); temp = head[i]; while(temp != null) { System.out.print(" -> "+ temp.vertex); temp = temp.link; } System.out.println(); private class GraphNode { int vertex; GraphNode link; [예제 10-1]

24 그래프 순회 그래프 순회(graph traversal) - 그래프 탐색(graph search)
어떤 정점에서 시작하여 그래프에 있는 정점들을 한번씩 방문 그래프 탐색 방법 깊이 우선 탐색(depth first search : DFS) 너비 우선 탐색(breadth first search : BFS)

25 그래프 순회 그래프 순회 방법을 우물 파기에 비유해보자.
한 지점을 골라서 팔 수 있을 때까지 계속해서 깊게 파다가 아무 리 땅을 파도 물이 나오지 않으면, 밖으로 나와 다른 지점을 골라 서 다시 깊게 땅을 파는 방법 ( ☞ 깊이 우선 탐색 ) 여러 지점을 고르게 파보고 물이 나오지 않으면, 파놓은 구덩이 들을 다시 좀더 깊게 파는 방법 ( ☞ 너비 우선 탐색 )

26 그래프 순회 깊이 우선 탐색(depth first search : DFS)
G의 모든 정점을 순회하는 DFS 알고리즘(재귀적으로 구현) DFS(G) // 깊이우선탐색 방법으로 그래프 G를 순회 { for each v ∈ V(G) visited[v] ← false; if (visited[v] = false) then aDFS(v); } end DFS() aDFS(v) // v를 시작 정점으로 하여 깊이우선탐색 visited[v] ← true; v 방문; for each x ∈ L(v) ▷ L(v) : 정점 v의 인접 리스트 if (visited[x] = false) then aDFS(x); end aDFS()

27 그래프 순회 예) 깊이우선탐색 순서 : A-B-D-G-E-C-F A B C D E F G

28 그래프 순회 너비 우선 탐색(breadth first search : BFS) 순회 방법
시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방 문하는 방식 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문 하는 순회방법 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출의 구조를 갖는 큐를 사용

29 그래프 순회 G의 정점들을 순회하는 BFS 알고리즘(큐 이용) BFS(s) // 시작정점을 v로 하여 너비우선탐색 {
for each v ∈ V(G) visited[v] ← false; visited[s] ← true; s 방문; Q←createQueue(); enQueue(Q, s); while (not isEmpty(Q)) do { v ← deQueue(Q); for each x ∈ L(v) ▷ L(v) : 정점 v의 인접 리스트 if (visited[x] = false) then { visited[x] ← true; x 방문; enQueue(Q, x); } end BFS()

30 그래프 순회 너비우선탐색 순서 : A-B-C-D-E-G-F A B C D E F C

31 신장 트리와 최소 비용 신장 트리 신장 트리(spanning tree)
n개의 정점으로 이루어진 무방향 연결 그래프에서, n개의 정점 전부 와 n-1개의 간선으로 만들어진 트리 신장 트리는 최소 갯수의 간선으로 그래프의 모든 정점들이 연결 되도록 함 예) G1: G1의 신장 트리들: A B C D A B C D A B C D A B C D

32 신장 트리와 최소 비용 신장 트리 깊이 우선 신장 트리(depth first spanning tree)
깊이 우선 탐색을 이용하여 생성된 신장 트리 너비 우선 신장 트리(breadth first spanning tree) 너비 우선 탐색을 이용하여 생성된 신장 트리 그래프 G9의 깊이 우선 신장 트리와 너비 우선 신장 트리

33 신장 트리와 최소 비용 신장 트리 최소 비용 신장 트리(minimum cost spanning tree)
무방향 가중치 연결 그래프의 신장 트리들 중, 간선들의 가중치 합이 최소인 신장 트리 가중치 그래프의 간선에 주어진 가중치는 두 정점 사이의 비용이 나 거리, 시간을 의미하는 값 최소 비용 신장 트리를 구하는 알고리즘 Kruskal 알고리즘 Prim 알고리즘

34 신장 트리와 최소 비용 신장 트리 Kruskal 알고리즘
정점들은 그대로 두고 간선이 하나도 없는 상태에서 시작하여 가중치 가 낮은 순서로 간선을 삽입하면서 최소 비용 신장 트리를 만든다. Kruskal 알고리즘 수행 과정 ⑴ 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정렬한다. ⑵ 그래프 G에 가중치가 가장 작은 간선을 고른다. 이 간선이 사이클을 형성하지 않으면 트리 간선 집합 T에 삽입하고, 사이클을 형성하면 버리고 다음으로 가중치가 작은 간선을 선택한다. ⑶ T이 n-1개의 간선을 포함될 때까지 ⑵를 반복한다.

35 신장 트리와 최소 비용 신장 트리 예) G10의 최소 비용 신장 트리 구하기 – Kruskal 알고리즘

36 신장 트리와 최소 비용 신장 트리 ① 가중치가 가장 작은 간선 (E,G) 삽입 (현재 삽입한 간선의 수: 1)

37 신장 트리와 최소 비용 신장 트리 ② 나머지 간선 중에서 가중치가 가장 작은 간선 (A,B) 삽입
(현재 삽입한 간선의 수 : 2개)

38 신장 트리와 최소 비용 신장 트리 ③ 나머지 간선 중에서 가중치가 가장 작은 간선 (E,F) 삽입
(현재 삽입한 간선의 수 : 3개)

39 신장 트리와 최소 비용 신장 트리 ④ 나머지 간선 중에서 가중치가 가장 작은 간선 (B,D) 삽입
(현재 삽입한 간선의 수 : 4개)

40 신장 트리와 최소 비용 신장 트리 ⑤ 나머지 간선 중에서 가중치가 가장 작은 간선 (A,D)를 삽입하면 A- B-D의 사이클이 생성되므로 삽입할 수 없다. 그 다음으로 가중치가 가장 작은 간선 (C,F) 삽입 (현재 삽입한 간선의 수 : 5개)

41 신장 트리와 최소 비용 신장 트리 ⑥ 나머지 간선 중에서 가중치가 가장 작은 간선 (D,E) 삽입
(현재 삽입한 간선의 수 : 6개) 현재 삽입한 간선의 수가 6개 최소 비용 신장 트리 완성

42 신장 트리와 최소 비용 신장 트리 Prim 알고리즘
하나의 정점에서 시작하여 모든 정점이 포함될 때까지 최소 비용 신장 트리를 확장해 나간다. ⑴ 그래프 G에서 시작 정점을 선택하여 트리 정점 집합 S에 삽입한다. ⑵ 트리 정점과 트리 밖 정점을 연결하는 간선들 중에서 가중치가 가장 작은 간선을 선택하여 트리를 확장한다. 이 때 선택된 간선의 한쪽 끝인 트리 외 정점을 S에 삽입한다. ⑶ S가 n 개의 정점을 포함할 때까지 ⑵를 반복한다.

43 신장 트리와 최소 비용 신장 트리 예) G10의 최소 비용 신장 트리 구하기 – Prim 알고리즘 초기 상태
A를 시작 정점으로 선택 트리 밖 각 정점 v를 트리 정점과 연결하는 간선의 가중치 중 최 소값(이 값을 d[v]라고 부르자)을 ∞로 초기화 시작 정점 A에 대한 d값은 0으로 초기화 ∞ 3 A B 17 6 5 ∞ D C ∞ 10 12 9 8 E 2 4 ∞ F G ∞ 14 ∞

44 신장 트리와 최소 비용 신장 트리 ① d 값이 가장 작은 트리 밖 정점(즉, A)을 골라 트리 정점 집합 T에 삽입하고, A와 인접한 트리 밖 정점의 d 값을 조정한다. 3 3 A B 17 6 5 17 D C 6 10 12 9 8 E 2 4 ∞ F G 14 ∞ ∞

45 신장 트리와 최소 비용 신장 트리 ② d 값이 가장 작은 트리 밖 정점(즉, B)을 골라 트리 정점 집합 T에 삽입하고, B와 인접한 트리 밖 정점의 d 값을 조정한다. 3 3 A B 17 6 5 17 D C 5 10 12 9 8 E 2 4 ∞ F G 14 ∞ 12

46 신장 트리와 최소 비용 신장 트리 ③ d 값이 가장 작은 트리 밖 정점(즉, D)을 골라 트리 정점 집합 T에 삽입하고, D와 인접한 트리 밖 정점의 d 값을 조정한다. 3 3 A B 17 6 5 17 D C 5 10 12 9 8 E 2 4 9 F G 14 ∞ 12

47 신장 트리와 최소 비용 신장 트리 ④ d 값이 가장 작은 트리 밖 정점(즉, E)을 골라 트리 정점 집합 T에 삽입하고, E와 인접한 트리 밖 정점의 d 값을 조정한다. 3 3 A B 17 6 5 10 D C 5 10 12 9 8 E 2 4 9 F G 14 4 2

48 신장 트리와 최소 비용 신장 트리 ⑤ d 값이 가장 작은 트리 밖 정점(즉, G)을 골라 트리 정점 집합 T에 삽입하고, G와 인접한 트리 밖 정점의 d 값을 조정한다. 3 3 A B 17 6 5 10 D C 5 10 12 9 8 E 2 4 9 F G 14 4 2

49 신장 트리와 최소 비용 신장 트리 ⑥ d 값이 가장 작은 트리 밖 정점(즉, F)을 골라 트리 정점 집합 T에 삽 입하고, F와 인접한 트리 밖 정점의 d 값을 조정한다. 3 3 A B 17 6 5 8 D C 5 10 12 9 8 E 2 4 9 F G 14 4 2

50 신장 트리와 최소 비용 신장 트리 ⑦ d 값이 가장 작은 트리 밖 정점(즉, C)을 골라 트리 정점 집합 T에 삽입하면 알고리즘 종료 3 3 3 A B A B 17 6 5 5 8 D D C C 5 10 12 9 9 8 8 E E 2 2 4 9 4 4 F G F G 14 2