C언어 응용 제 11 주 그래프1

다음 주 과제 다음 주 제3차 시험 9장 읽어오기 숙제 해서 제출하기 시험범위 : 7장, 8장, 9장 3절 시험시간 : 11월 17일(월요일) 1교시 시험장소 : C101 주의 : 11월 19일(수요일)은 정상 수업 9장 읽어오기 숙제 해서 제출하기

그래프 그래프의 구조 그래프의 구현 그래프 순회 신장 트리와 최소 비용 신장 트리

그래프 자료구조의 개념을 이해한다. 그래프의 표현 방법을 알아본다. 그래프의 순회 방법과 알고리즘을 알아본다. 신장 트리와 최소 비용 신장 트리를 알아본다. 최소 비용 신장 트리를 응용한 최단 경로 알고리 즘을 이해한다.

그래프(graph) 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계를 가지는 원소들을 표현하기 위한 자료구조 그래프 G 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합 G = (V, E) V는 그래프에 있는 정점들의 집합 E는 정점을 연결하는 간선들의 집합 그래프의 예 [그림 9-1] 그래프의 사용 예_버스 노선도, 인맥 지도

그래프의 종류 무방향 그래프(undirected graph) 두 정점을 연결하는 간선의 방향이 없는 그래프 정점 Vi와 정점 Vj을 연결하는 간선을 (Vi, Vj)로 표현 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타낸다. V(G1)={A, B, C, D}      E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D)} V(G2)={A, B, C}          E(G2)={(A,B), (A,C), (B,C)} [그림 9-2] 그래프 G1과 G2

방향 그래프(directed graph) , 다이그래프(digraph) 간선이 방향을 가지고 있는 그래프 정점 Vi에서 정점 Vj를 연결하는 간선 즉, Vi→Vj를 <Vi, Vj>로 표현 Vi를 꼬리(tail), Vj를 머리(head)라고 한다. <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선V(G3)={A, B, C, D}      E(G3)={<A,B>, <A,D>, <B,C>, <B,D>, <C,D>} V(G4)={A, B, C}          E(G4)={<A,B>, <A,C>, <B,A>, <B,C>} [그림 9-3] 방향 그래프 G3, G4

완전 그래프(complete graph) 각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프 정점이 n개인 무방향 그래프에서 최대의 간선 수 : n(n-1)/2개 정점이 n개인 방향 그래프의 최대 간선 수 : n(n-1)개 완전 그래프의 예 G5는 정점의 개수가 4개인 무방향 그래프이므로 완전 그래프가 되려면 4(4-1)/2=6개의 간선 연결 G6은 정점의 개수가 4개인 방향 그래프이므로 완전 그래프가 되려면 4(4-1)=12개의 간선 연결 [그림 9-4] 완전 그래프 G5, G6

부분 그래프(subgraph) 원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프 그래프 G와 부분 그래프 G'의 관계  V(G')⊆V(G),  E(G')⊆E(G) 그래프 G1에 대한 부분 그래프의 예 [그림 9-5] 그래프 G1과 부분 그래프 G1’

가중 그래프(weight graph) , 네트워크(network) [그림 9-6] 가중 그래프 G7, G8

그래프 관련 용어 그래프에서 두 정점 Vi과 Vj를 연결하는 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)되어 있다고 하고, 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어있다고 한다. 그래프G1에서 정점 A와 인접한 정점은 B와 D이고, 정점 A에 부속되어있는 간선은 (A,B)와 (A,D)이다. 차수(degree) – 정점에 부속되어있는 간선의 수 그래프 G1에서 정점 A의 차수는 2, 정점 B의 차수는 3 방향 그래프의 정점의 차수 = 진입차수 + 진출차수 방향 그래프의 진입차수(in-degree) : 정점을 머리로 하는 간선의 수 방향 그래프의 진출차수(out-degree) : 정점을 꼬리로 하는 간선의 수 방향 그래프 G3에서 정점 B의 진입차수는 1, 진출차수는 2 정점 B의 전체 차수는 (진입차수 + 진출차수) 이므로 3이 된다.

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

DAG (directed acyclic graph) 방향 그래프이면서 사이클이 없는 그래프 연결 그래프 (connected graph) 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프 즉, 떨어져있는 정점이 없는 그래프 그래프에서 두 정점 Vi에서 Vj까지의 경로가 있으면 정점 Vi와 Vj가 연결(connected)되었다고 한다. 트리는 사이클이 없는 연결 그래프이다. 단절 그래프 (disconnected graph) 연결되지 않은 정점이 있는 그래프 [그림 9-7] 연결 그래프와 단절 그래프

추상 자료형 그래프 ADT Graph 데이터 : 공백이 아닌 정점의 집합과 간선의 집합 연산 : g∈Graph; u,v∈V;    데이터 : 공백이 아닌 정점의 집합과 간선의 집합    연산 :         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

인접 행렬(adjacent matrix) 행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장 n개의 정점을 가진 그래프 : n x n 정방행렬 행렬의 행 번호와 열 번호 : 그래프의 정점 행렬 값 : 두 정점이 인접되어있으면 1, 인접되어있지 않으면 0 무방향 그래프의 인접 행렬 행 i의 합 = 열 i의 합 = 정점 i의 차수 방향 그래프의 인접 행렬 행 i의 합 = 정점 i의 진출차수 열 i의 합 = 정점 i의 진입차수 인접 행렬 표현의 단점 n개의 정점을 가지는 그래프를 항상 n x n개의 메모리 사용 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비 발생

인접 행렬의 예 [그림 9-8] 그래프 G1, G2, G3, G4에 대한 인접 행렬 표현

인접 행렬 C 프로그램 그래프 G1, G2, G3, G4를 인접 행렬로 구현한 프로그램 실행 결과

인접 리스트(adjacent matrix) 각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트 각 정점의 차수만큼 노드를 연결 리스트 내의 노드들은 인접 정점에 대해서 오름차순으로 연결 인접 리스트의 각 노드 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크  필드로 구성 정점의 헤드 노드 정점에 대한 리스트의 시작을 표현 n개의 정점과 e개의 간선을 가진 무방향 그래프의 인접 리스트 헤드 노드 배열의 크기 : n 연결하는 노드의 수 : 2e 각 정점의 헤드에 연결된 노드의 수 : 정점의 차수 n개의 정점과 e개의 간선을 가진 방향 그래프의 인접 리스트 연결하는 노드의 수 : e 각 정점의 헤드에 연결된 노드의 수 : 정점의 진출 차수

그래프 G1, G2, G3, G4에 대한 인접 리스트 [그림 9-9] 그래프 G1, G2, G3, G4에 대한 인접 리스트 표현

인접 리스트 C 프로그램 그래프 G1, G2, G3, G4를 인접 리스트로 구현한 프로그램 그래프의 정점 A, B, C, D 대신에 0, 1, 2, 3의 번호를 사용하여 연산하고, 출력할 때 A, B, C, D 문자로 표시 간선의 삽입은 항상 인접 리스트의 첫 번째 노드로 삽입하기 실행 결과

그래프 순회(graph traversal), 그래프 탐색(graph search) 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산 그래프 탐색방법 깊이 우선 탐색(depth first search : DFS) 너비 우선 탐색(breadth first search : BFS)

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

깊이 우선 탐색(depth first search : DFS) 순회 방법 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 깊이 우선 탐색의 수행 순서 ⑴ 시작 정점 v를 결정하여 방문한다. ⑵ 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 w를 방문한다. 그리고 w를 v로 하여 다시 ⑵를 반복한다. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 ⑵를 수행한다. ⑶ 스택이 공백이 될 때까지 ⑵를 반복한다.

깊이 우선 탐색 알고리즘 DFS(v) for (i←0; i<n; i←i+1) do { visited[i]←false; }    }    stack←createStack();    visited[v]←true;    v 방문;      while (not isEmpty(stack)) do {                      if (visited[v의 인접정점 w]=false) then {                 push(stack, v);                 visited[w]←true;                 w 방문;                          v←w;              }             else  v←pop(stack);         end DFS()

깊이 우선 탐색 예) 그래프 G9에 대한 깊이 우선 탐색 초기상태 : 배열 visited를 False로 초기화하고, 공백 스택을 생성

① 정점 A를 시작으로 깊이 우선 탐색을 시작 visited[A]←true;  A 방문;

② 정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push 하고, 인접정점 B와 C 중에서 오름차순에 따라 B를 선택하여 탐색을 계속한다. push(stack, A);    visited[B]←true;    B 방문;    

③ 정점 B에 방문하지 않은 정점 D, E가 있으므로 B를 스택에 push 하고, 인접정점 D와 E 중에서 오름차순에 따라 D를 선택하여 탐색을 계속한다. push(stack, B);     visited[D]←true;     D 방문; 

④ 정점 D에 방문하지 않은 정점 G가 있으므로 D를 스택에 push 하고, 인접정점 G를 선택하여 탐색을 계속한다. push(stack, D);   visited[G]←true; G 방문;   

⑤ 정점 G에 방문하지 않은 정점 E, F가 있으므로 G를 스택에 push 하고, 인접정점 E와 F 중에서 오름차순에 따라 E를 선택하여 탐색을 계속한다. push(stack, G); visited[E]←true; E 방문; 

⑥ 정점 E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push 하고, 인접정점 C를 선택하여 탐색을 계속한다. push(stack, E);   visited[C]←true; C 방문;        

⑦ 정점 C에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 E에 대해서 방문하지 않은 인접정점이 있는지 확인한다. pop(stack);

⑧ 정점 E는 방문하지 않은 인접정점이 없으므로, 다시 스택을 pop 하여 받은 정점 G에 대해서 방문하지 않은 인접정점이 있는지 확인한다. pop(stack);

⑨ 정점 G에 방문하지 않은 정점 F가 있으므로 G를 스택에 push 하고, 인접정점 F를 선택하여 탐색을 계속한다. push(stack, G); visited[F]←true; F 방문;

⑩ 정점 F에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 G에 대해서 방문하지 않은 인접정점이 있는지 확인한다. pop(stack);

⑪ 정점 G에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 D에 대해서 방문하지 않은 인접정점이 있는지 확인한다. pop(stack);

⑫ 정점 D에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 B에 대해서 방문하지 않은 인접정점이 있는지 확인한다. pop(stack);

⑬ 정점 B에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 A에 대해서 방문하지 않은 인접정점이 있는지 확인한다. pop(stack); ⑭ 정점 A에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하는데 스택이 공백이므로 깊이 우선 탐색을 종료한다

그래프 G9의 깊이 우선 탐색 경로 : A-B-D-G-E-C-F

그래프 G9를 깊이 우선 탐색하는 C 프로그램 그래프 G9를 인접 리스트로 표현한다. 정점 A~G 대신에 0~6의 번호를 사용하여 연산하고, 출력할 때에는 A~G 문자로 바꾸어 표시한다. 깊이 우선 탐색을 위해서 6장에서 구현한 스택 프로그램을 사용한다. 실행 결과

너비 우선 탐색(breadth first search : BFS) 순회 방법 시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회방법 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출의 구조를 갖는 큐를 사용 너비 우선 탐색의 수행 순서 ⑴ 시작 정점 v를 결정하여 방문한다. ⑵ 정점 v에 인접한 정점들 중에서 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue한다.  ⑶ 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점들을 다시 차례로 방문하기 위해서 큐에서 deQueue하여 구한 정점에서 ⑵를 반복한다. ⑷ 큐가 공백이 될 때까지 ⑵~⑶을 반복한다.

너비 우선 탐색 알고리즘 BFS(v) for (i←0; i<n; i←i+1) do { visited[i]←false; }    }    Q←createQueue();    visited[v]←true;    v 방문;    while (not isEmpty(Q)) do {                while (visited[v의 인접정점 w]=false) do {                 visited[w]←true;                 w 방문;                 enQueue(Q, w);                               }             v←deQueue(Q);       end BFS()

너비 우선 탐색 예) 그래프 G9에 대한 너비 우선 탐색 초기상태 : 배열 visited를 False로 초기화하고, 공백 큐를 생성

① 정점 A를 시작으로 너비 우선 탐색을 시작한다. visited[A]←true; A 방문; 

② 정점 A의 방문 안한 모든 인접정점 B, C를 방문하고, 큐에 enQueue 한다. visited[(A의 방문 안한 인접정점 B와 C)]←true; (A의 방문 안한 인접정점 B와 C) 방문; enQueue(Q, (A의 방문 안한 인접정점 B와 C));

③ 정점 A에 대한 인접정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 정점 B를 구한다. v ← deQueue(Q);

④ 정점 B의 방문 안한 모든 인접정점 D, E를 방문하고 큐에 enQueue 한다. visited[(B의 방문 안한 인접정점 D와 E)]←true; (B의 방문 안한 인접정점 D와 E) 방문; enQueue(Q, (B의 방문 안한 인접정점 D와 E));

⑤ 정점 B에 대한 인접정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 정점 C를 구한다. v ← deQueue(Q);

⑥ 정점 C에는 방문 안한 인접정점이 없으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 정점 D를 구한다. v ← deQueue(Q);

⑦ 정점 D의 방문 안한 인접정점 G를 방문하고 큐에 enQueue 한다. visited[(D의 방문 안한 인접정점 G)]←true; (D의 방문 안한 인접정점 G) 방문; enQueue(Q, (D의 방문 안한 인접정점 G));

⑧ 정점 D에 대한 인접정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 정점 E를 구한다. v ← deQueue(Q);

⑨ 정점 E에는 방문 안한 인접정점이 없으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 정점 G를 구한다. v ← deQueue(Q);

⑩ 정점 G의 방문 안한 인접정점 F를 방문하고 큐에 enQueue 한다. visited[(G의 방문 안한 인접정점 F)]←true; (G의 방문 안한 인접정점 F) 방문; enQueue(Q, (G의 방문 안한 인접정점 F)); 

⑪ 정점 G에 대한 인접정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하여 정점 F를 구한다 . v ← deQueue(Q); ⑫ 정점 F에는 방문 안한 인접정점이 없으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue하는데 큐가 공백이므로 너비 우선 탐색을 종료한다 .

그래프 G9의 너비 우선 탐색 경로 : A-B-C-D-E-G-F

그래프 G9를 너비 우선 탐색하는 C 프로그램 그래프 G9를 인접 리스트로 표현한다. 정점 A~G 대신에 0~6의 번호를 사용하여 연산하고, 출력할 때에는 A~G 문자로 바꾸어 표시한다. 너비 우선 탐색을 위해서 7장에서 구현한 큐 프로그램을 사용한다. 실행 결과

다음 주 계속