14 장. 그래프 알고리즘 Internet Computing KUT Youn-Hee Han.

Presentation on theme: "14 장. 그래프 알고리즘 Internet Computing KUT Youn-Hee Han."— Presentation transcript:

1 14 장. 그래프 알고리즘 Internet Computing Laboratory @ KUT Youn-Hee Han

2 Data Structure2 1. 그래프 그래프 ADT 사용 대상 유관한 사물 (Object) 또는 개념 (Concepts) 을 연결 연결망 (Connection Network 또는 Network). 프로젝트 단위작업 (Task) 사이의 순서 분자 연결 구조 전자 부품 연결 구조 전산학, 이산수학의 연구 주제

3 Data Structure3 1. 그래프 용어 정리 그래프 G = 정점 (Vertex, Node) 의 집합 V + 간선 (Edge) 의 집합 E 서브 그래프 (Subgraph) G’  그래프 G 의 일부 Node 들과 이들을 연결하는 Edge 만을 취하여 만든 부분 그래프 인접 (Adjacency)  두 개의 Node 가 간선에 의하여 연결되어 있을 때 이 두 정점은 서로 인접한다고 일컫는다. 가중치 그래프 (Weighted Graph)  간선마다 가중치 값을 할당한 그래프 무방향 그래프 (Undirected Graph) vs. 방향 그래프 (Directed Graph)

4 Data Structure4 1. 그래프 용어 정리 경로 (Path)  임의의 Node V 에서 시작하여 또 하나의 Node V’ 로 가기 위한 일련의 간선모임 단순경로 (Simple Path)  같은 Node 를 중복하여 지나가지 않는 경로  (a) 에서 a-b-c-d: a 에서 d 까지 가기 위한 단순경로  (a) 에서 a-b-c-e-c-d: 단순 경로 아님 사이클 (Cycle)  Node V 에서 출발하여 Node V 로 되돌아오는 경로 단순 사이클 (Simple Cycle)  같은 Node 를 중복하여 지나가지 않는 사이클  (a) 에서 c-b-a-e-c: 단순 사이클  (a) 에서 a-b-c-d-c-b-a: 단순 사이클 아님

5 Data Structure5 1. 그래프 용어 정리 연결 그래프 (Connected Graph) - (a), (b)  그래프내의 모든 Node 들 간에 서로 도달할 수 있는 경로가 존재하는 그래프 절단 그래프 (Disconnected Graph) – (c) 완전 그래프 (Complete Graph) – (e)  모든 Node 들 간에 1:1 로 직접 연결된 Edge 를 지닌 그래프  모든 Node 들이 서로 인접 (Adjacent) 하다.

6 Data Structure6 1. 그래프 용어 정리 그래프의 동일성  아래 두 그래프는 동일하다 (or 일치한다 ) = homogeneous  Node 들 상호간의 공간적인 위치 관계 (Topology) 는 중요하지 않다  같은 Node 집합을 지니고 있고 그들 사이에 Edge 연결 상태가 동일하면 두 그래프는 일치한다.

7 Data Structure7 1. 그래프 그래프와 트리 Tree  연결 (Connected) 그래프 & 사이클 없는 (Acyclic) 그래프 V 개의 정점, 항상 V-1 개의 간선 V 개의 Node 들에 대하여  V-1 개 보다 많은 Edge 가 존재하면 사이클이 존재 (Cyclic Graph)  V-1 보다 적으면 절단 그래프 (Disconnected Graph) 포리스트 (Forest): 트리의 집합

8 Data Structure8 2. ADT 그래프 그래프에 행하는 작업 Create: 새로운 그래프를 만들기 Destroy: 사용되던 그래프를 파기하기 InsertVertex: 새로운 정점을 삽입하기 InsertEdge: 새로운 간선을 삽입하기 DeleteVertex: 기존 정점을 삭제하기 DeleteEdge: 기존 간선을 삭제하기 RetrieveVertex: 키에 의해 정점 레코드를 검색하기 IsAdjacent: 인접해 있는지 확인하기 IsEmpty: 비어있는 그래프인지 확인하기

9 Data Structure9 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 2 차원 행렬 : 2 차원 배열 - A[MAX][MAX] 직접 연결된 간선이 있으면 해당 값을 1(True) 대각선 요소는 무의미. 0 또는 1.

10 Data Structure10 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 가중치 그래프 : 간선의 가중치  가중치 : 정점 사이를 이동하는데 필요한 비용이나 거리 인접하지 않은 정점 : 무한대 값 or 음수 값

11 Data Structure11 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 무방향 그래프 (Undirected Graph) 인 경우  무방향 그래프의 인접행렬은 대각선을 중심으로 대칭  메모리 절약을 위해 배열의 반쪽 만을 사용할 수 있음 방향 그래프 (Directed Graph) 인 경우  대칭이 아님 인접행렬 표현을 위한 심볼 테이블 Node ID 를 배열 인덱스로 매핑 시키는 테이블 “a 에서 c 로 가는 Direct Edge 가 있는가 ?”  a  0  c  2  A[0][2] 가 1 이면 True Vertex 배열 인덱스 a0 b1 c2 d3 e4

12 Data Structure12 3. 그래프 표현방법 정정 배열 (Static Array) AdjacentMatrix[Max][Max] ??? 전체 배열의 크기가 컴파일 타임에 고정된다.  여러 문제 발생 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) Heap 공간을 활용 malloc 함수 이용 전체 배열의 크기가 런타임에 고정된다.  한 번 고정되면 바꾸기 힘든 것은 마찬가지 한 개의 정수 (integer) 공간 typedef int * ptrType; ptrType p = malloc(sizeof(int)); *p = 20;

13 Data Structure13 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) 연속된 정수공간  ptrType p = malloc(NCol * sizeof(int));  NCol 개의 정수가 들어갈 수 있는 공간.  이 변수공간을 마치 배열처럼 사용  포인터 기호 또는 배열 기호에 의해 접근가능

14 Data Structure14 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) 행렬 : NRow * NCol 개의 정수공간 Arrays of Pointers to Array of Integer

15 Data Structure15 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) 동적 배열 생성 함수 동적 배열 반환 함수 int ** InitMatrix(int NRow, int NCol, int initValue) { int **m; m = malloc(NRow * sizeof(int *)); for (int i = 0; i < NRow; i++) m[i] = malloc(NCol * sizeof(int)); for (int i = 0; i < NRow; i++) for (int j = 0; j < NCol; j++) m[i][j] = initValue; return m; } void FreeMatrix(**m) { for (int i = 0; i < NRow; i++) free(m[i]); free(m); }

16 Data Structure16 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) 그래프 표현 typedef struct { int V; 그래프 내부 정점의 수 int E; 그래프 내부 간선의 수 int **M; 인접행렬을 가리키는 포인터 } graphType; typedef graphType* graphPtr; 그래프를 가리키는 포인터 graphPtr InitGraph(int V) 함수 프로토타입 void InsertEdge(graphPtr g, int V1, int V2) 함수 프로토타입

17 Data Structure17 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) Graph 초기화 Edge 삽입 graphPtr InitGraph(int V) { graphPtr G = malloc(sizeof(graphType)); G->V = V; G->E = 0; G->M = InitMatrix(V, V, 0); return G; } void InsertEdge(graphPtr g, int V1, int V2) { if (g->M[V1][V2] = = 0) { g->E++; g->M[V1][V2] = 1; // g->M[V2][V1] = 1; 무방향 그래프이면 V2->V1 도 1 로 셋팅 }

18 Data Structure18 3. 그래프 표현방법 인접 리스트 (Adjacency List) 하나의 정점에 인접한 모든 노드를 연결 리스트 형태로 표시 연결 리스트를 가리키는 포인터 배열 경로에 관한 정보가 아님.  c 를 나타내는 A[2] 에 대한 연결 리스트가 d  e  b 라고 해서 경로가 그렇다는 것은 아님 가중치 정보를 표시하려면 노드에 가중치 필드를 추가.

19 Data Structure19 3. 그래프 표현방법 인접 리스트 (Adjacency List) 무방향 그래프 : 하나의 간선에 대해 두 개의 노드가 나타남. 인접 리스트의 노드 수는 간선 수 E 의 2 배 인접 리스트와 인접 행렬 정점 i 와 정점 j 가 인접해 있는가의 판단  인접행렬 (Adjacent Matrix) 가 유리 정점 i 에 인접한 모든 노드를 찾아라에 대한 연산  인접 리스트 (Adjacent List) 가 유리 공간 면에서 인접행렬은 V 2 개의 공간, 인접 리스트는 2E 개의 공간이 필요 희소 그래프, 조밀 그래프 간선 수가 적은 그래프를 희소 그래프 ( 稀少, Sparse Graph) 간선 수가 많은 그래프를 조밀 그래프 ( 稠密, Dense Graph) 희소 그래프일 수록 인접 리스트가 유리

20 Data Structure20 3. 그래프 표현방법 인접 리스트 (Adjacency List) 을 위한 동적 배열 (Dynamic Array) 그래프 표현 typedef struct { int Data; 정점의 ID 번호 node* Next; 다음 노드를 가리키는 포인터 } node; typedef node* Nptr; typedef struct { int V; 그래프 내부 정점의 수 int E; 그래프 내부 간선의 수 node **A; 포인터 배열을 가리키는 포인터 } graphType; typedef graphType *graphPtr; 그래프를 가리키는 포인터 graphPtr InitGraph(int V) 함수 프로토타입 void InsertEdge(graphPtr g, int V1, int V2) 함수 프로토타입

21 Data Structure21 3. 그래프 표현방법 인접 리스트 (Adjacency List) 을 위한 동적 배열 (Dynamic Array) Graph 초기화 graphPtr InitGraph(int V) { graphPtr G = malloc(sizeof(graphType)); G->V = V; 정점의 수를 V 개로 확정 G->E = 0; 생성 시에 간선 수 0 G->A = malloc(V * sizeof(node *)); V 개 node 포인터 배열을 동적으로 생성 for (int i = 0; i < V; i++) 배열 내 모든 포인터 값을 G->A[i] = NULL; 널로 초기화 return G; 포인터의 포인터를 리턴 }

22 Data Structure22 3. 그래프 표현방법 인접 리스트 (Adjacency List) 을 위한 동적 배열 (Dynamic Array) Edge 삽입 void InsertEdge(graphPtr g, int V1, int V2) { Nptr temp = malloc(sizeof(node)); 새로운 노드를 만들고 temp->Data = V2; 그 곳에 V2 의 ID 번호를 넣음 temp->Next = g->A[V1]; 새 노드가 현재 첫 노드를 가리키게 g->A[V1] = temp; L[V1] 이 새로만든 노드를 가리키게 } 무방향 그래프이면 V2 에도 V1 을 삽입. graphPtr g = InitGraph(5);. InsertEdge(g, 0, 1);. InsertEdge(g, 0, 4); 1 1 4

23 Data Structure23 기말 고사 시험 범위 8 장. 알고리즘과 효율 9 장. 정렬 알고리즘과 효율 10 장. 트리 11 장. 우선순위 큐 13 장. 균형 탐색 트리 14 장. 그래프 알고리즘 p.578 까지 기말고사 : 6 월 20 일 오전 9 시 – B 동 315 호