14 장. 그래프 알고리즘 Internet Computing KUT Youn-Hee Han
Data Structure2 1. 그래프 그래프 ADT 사용 대상 유관한 사물 (Object) 또는 개념 (Concepts) 을 연결 연결망 (Connection Network 또는 Network). 프로젝트 단위작업 (Task) 사이의 순서 분자 연결 구조 전자 부품 연결 구조 전산학, 이산수학의 연구 주제
Data Structure3 1. 그래프 용어 정리 그래프 G = 정점 (Vertex, Node) 의 집합 V + 간선 (Edge) 의 집합 E 서브 그래프 (Subgraph) G’ 그래프 G 의 일부 Node 들과 이들을 연결하는 Edge 만을 취하여 만든 부분 그래프 인접 (Adjacency) 두 개의 Node 가 간선에 의하여 연결되어 있을 때 이 두 정점은 서로 인접한다고 일컫는다. 가중치 그래프 (Weighted Graph) 간선마다 가중치 값을 할당한 그래프 무방향 그래프 (Undirected Graph) vs. 방향 그래프 (Directed Graph)
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: 단순 사이클 아님
Data Structure5 1. 그래프 용어 정리 연결 그래프 (Connected Graph) - (a), (b) 그래프내의 모든 Node 들 간에 서로 도달할 수 있는 경로가 존재하는 그래프 절단 그래프 (Disconnected Graph) – (c) 완전 그래프 (Complete Graph) – (e) 모든 Node 들 간에 1:1 로 직접 연결된 Edge 를 지닌 그래프 모든 Node 들이 서로 인접 (Adjacent) 하다.
Data Structure6 1. 그래프 용어 정리 그래프의 동일성 아래 두 그래프는 동일하다 (or 일치한다 ) = homogeneous Node 들 상호간의 공간적인 위치 관계 (Topology) 는 중요하지 않다 같은 Node 집합을 지니고 있고 그들 사이에 Edge 연결 상태가 동일하면 두 그래프는 일치한다.
Data Structure7 1. 그래프 그래프와 트리 Tree 연결 (Connected) 그래프 & 사이클 없는 (Acyclic) 그래프 V 개의 정점, 항상 V-1 개의 간선 V 개의 Node 들에 대하여 V-1 개 보다 많은 Edge 가 존재하면 사이클이 존재 (Cyclic Graph) V-1 보다 적으면 절단 그래프 (Disconnected Graph) 포리스트 (Forest): 트리의 집합
Data Structure8 2. ADT 그래프 그래프에 행하는 작업 Create: 새로운 그래프를 만들기 Destroy: 사용되던 그래프를 파기하기 InsertVertex: 새로운 정점을 삽입하기 InsertEdge: 새로운 간선을 삽입하기 DeleteVertex: 기존 정점을 삭제하기 DeleteEdge: 기존 간선을 삭제하기 RetrieveVertex: 키에 의해 정점 레코드를 검색하기 IsAdjacent: 인접해 있는지 확인하기 IsEmpty: 비어있는 그래프인지 확인하기
Data Structure9 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 2 차원 행렬 : 2 차원 배열 - A[MAX][MAX] 직접 연결된 간선이 있으면 해당 값을 1(True) 대각선 요소는 무의미. 0 또는 1.
Data Structure10 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 가중치 그래프 : 간선의 가중치 가중치 : 정점 사이를 이동하는데 필요한 비용이나 거리 인접하지 않은 정점 : 무한대 값 or 음수 값
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
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;
Data Structure13 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) 연속된 정수공간 ptrType p = malloc(NCol * sizeof(int)); NCol 개의 정수가 들어갈 수 있는 공간. 이 변수공간을 마치 배열처럼 사용 포인터 기호 또는 배열 기호에 의해 접근가능
Data Structure14 3. 그래프 표현방법 인접행렬 (Adjacency Matrix) 을 위한 동적 배열 (Dynamic Array) 행렬 : NRow * NCol 개의 정수공간 Arrays of Pointers to Array of Integer
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); }
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) 함수 프로토타입
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 로 셋팅 }
Data Structure18 3. 그래프 표현방법 인접 리스트 (Adjacency List) 하나의 정점에 인접한 모든 노드를 연결 리스트 형태로 표시 연결 리스트를 가리키는 포인터 배열 경로에 관한 정보가 아님. c 를 나타내는 A[2] 에 대한 연결 리스트가 d e b 라고 해서 경로가 그렇다는 것은 아님 가중치 정보를 표시하려면 노드에 가중치 필드를 추가.
Data Structure19 3. 그래프 표현방법 인접 리스트 (Adjacency List) 무방향 그래프 : 하나의 간선에 대해 두 개의 노드가 나타남. 인접 리스트의 노드 수는 간선 수 E 의 2 배 인접 리스트와 인접 행렬 정점 i 와 정점 j 가 인접해 있는가의 판단 인접행렬 (Adjacent Matrix) 가 유리 정점 i 에 인접한 모든 노드를 찾아라에 대한 연산 인접 리스트 (Adjacent List) 가 유리 공간 면에서 인접행렬은 V 2 개의 공간, 인접 리스트는 2E 개의 공간이 필요 희소 그래프, 조밀 그래프 간선 수가 적은 그래프를 희소 그래프 ( 稀少, Sparse Graph) 간선 수가 많은 그래프를 조밀 그래프 ( 稠密, Dense Graph) 희소 그래프일 수록 인접 리스트가 유리
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) 함수 프로토타입
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; 포인터의 포인터를 리턴 }
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
Data Structure23 기말 고사 시험 범위 8 장. 알고리즘과 효율 9 장. 정렬 알고리즘과 효율 10 장. 트리 11 장. 우선순위 큐 13 장. 균형 탐색 트리 14 장. 그래프 알고리즘 p.578 까지 기말고사 : 6 월 20 일 오전 9 시 – B 동 315 호