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

Slides:



Advertisements
Similar presentations
1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
Advertisements

그래프(Graph)
UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현
제2장 주파수 영역에서의 모델링.
제14장 동적 메모리.
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
최윤정 Java 프로그래밍 클래스 상속 최윤정
Internet Computing KUT Youn-Hee Han
연결리스트(linked list).
제 9 장 구조체와 공용체.
컴퓨터 프로그래밍 기초 [Final] 기말고사
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
CHAP 10:그래프 (1) 순천향대학교 하상호.
CHAP 10:그래프 순천향대학교 하상호.
CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 생능출판사 학기 데이터구조.
CHAP 10:그래프 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 62).
제5장 트리.
자료 구조: Chapter 3 (2)구조체, 포인터
자료구조론 10장 그래프(graph).
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
CHAPTER 02 OpenCV 개요 PART 01 영상 처리 개요 및 OpenCV 소개.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
Dynamic Memory and Linked List
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
Chapter 10 그래프(graph) SANGJI University Kwangman KO
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
CHAP 10 : 그래프.
CHAP 10 : 그래프.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
그래프(graph) 연결되어 있는 객체 간의 관계를 표현하는 자료구조 가장 일반적인 자료구조 형태
11장. 1차원 배열.
13 인덱스 인덱스의 개념 인덱스의 구조 인덱스의 효율적인 사용 방법 인덱스의 종류 및 생성 방법 인덱스 실행 경로 확인
Introduction To Data Structures Using C
CHAP 10:그래프 (2) 순천향대학교 하상호.
어서와 C언어는 처음이지 제14장.
인터넷응용프로그래밍 JavaScript(Intro).
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
13. 포인터와 배열! 함께 이해하기 IT응용시스템공학과 김 형 진 교수.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
주요 내용 왜 그래프인가? 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
USN(Ubiquitous Sensor Network)
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
그래프의 용어 알고리즘 수업자료 김정현.
데이터 동적 할당 Collection class.
CHAP 10 : 그래프.
보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)
Chapter 1 단위, 물리량, 벡터.
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
Summary of Pointers and Arrays
Numerical Analysis Programming using NRs
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
동적메모리와 연결 리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
제 4 장 Record.
29장. 템플릿과 STL 01_ 템플릿 02_ STL.
어서와 C언어는 처음이지 제21장.
13. 포인터와 배열! 함께 이해하기.
C++ Espresso 제15장 STL 알고리즘.
7 생성자 함수.
6 객체.
BoardGame 보드게임 따라가기.
2019 2학기 9장 배열과 포인터 1. 주소, 주소연산자(&) 2. 포인터, 역참조연산자(*) 3. 배열과 포인터.
Presentation transcript:

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 호