CHAP 10 : 그래프.

Slides:



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

1. 도형의 연결 상태 2. 꼭지점과 변으로 이루어진 도형 Ⅷ. 도형의 관찰 도형의 연결상태 연결상태가 같은 도형 단일폐곡선의 성질 연결상태가 같은 입체도형 뫼비우스의 띠.
이진 나무 구조 강윤섭 2008년 5월 23일.
그래프(Graph)
주요 내용 기본 용어 이진 트리(binary tree) 이진 탐색 트리(binary search tree)
주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
Shortest Path Algorithm
제 6 장 그래프 6.1 그래프의 정의 6.2 용어 및 표현법 6.3 그래프의 표현 방법 6.4 그래프의 순회와 신장 트리
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
컴퓨터 프로그래밍 기초 [Final] 기말고사
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
CHAP 10:그래프 (1) 순천향대학교 하상호.
CHAP 10:그래프 순천향대학교 하상호.
그래프 추상 데이타 타입(1/9) 개요 Koenigsberg 다리 문제 차수(degree) : 정점에 연결된 간선의 수
CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 생능출판사 학기 데이터구조.
CHAP 10:그래프 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 62).
자료구조론 10장 그래프(graph).
제 6 장 그래프.
되추적(Backtracking).
자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호.
제3장 스택과 큐.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
8장 함수 함수의 필요성 라이브러리 함수와 사용자 정의 함수 함수의 정의, 원형, 호출 배열을 함수 인자로 전달 재귀호출.
Chapter 10 그래프(graph) SANGJI University Kwangman KO
강의 #9 그래프(Graph).
그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
CHAP 10 : 그래프.
CHAP 10: 그래프(part 2) 순천향대학교 하상호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
C언어 응용 제 11 주 그래프1.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
그래프(graph) 연결되어 있는 객체 간의 관계를 표현하는 자료구조 가장 일반적인 자료구조 형태
CHAP 7: 트 리 (1) 한 성 대 학 교 정보통신공학과 봉 정 식.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
Introduction To Data Structures Using C
CHAPTER 6 그래프.
CHAP 10:그래프 (2) 순천향대학교 하상호.
자바 5.0 프로그래밍.
어서와 C언어는 처음이지 제14장.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
주요 내용 왜 그래프인가? 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
그래프의 용어 알고리즘 수업자료 김정현.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
객체기반 SW설계 팀활동지 4.
알고리즘 알고리즘이란 무엇인가?.
CHAP 10 : 그래프.
보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
7주차: Functions and Arrays
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
Numerical Analysis Programming using NRs
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다.
07. DB 설계 명지대학교 ICT 융합대학 김정호.
제 9 장 그래프.
29장. 템플릿과 STL 01_ 템플릿 02_ STL.
문제풀이방식-맹목적 탐색 Ai4.
보고서 #4 (1) (제출기한: 10/6) #1 다음 그래프 G에 대해서 답하시오. (2*5 = 10)
C++ Espresso 제15장 STL 알고리즘.
11. 트리.
Presentation transcript:

CHAP 10 : 그래프

그래프(graph) 연결되어 있는 객체 간의 관계를 표현하는 자료구조 우리가 배운 트리(tree)도 그래프의 특수한 경우임 지도에서 도시들의 연결 상태 전기회로의 소자 간 연결 상태 네트위크를 통해 연결되어 있는 컴퓨터들 전공 과목간의 선수 과목 관계

그래프 역사 1800년대 오일러에 의하여 창안 오일러(Euler) 경로 A,B,C,D 지역의 연결 관계 표현 오일러 정리 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 경로를 오일러 경로라 함 A,B,C,D 지역의 연결 관계 표현 위치: 정점(node) 다리: 간선(edge) 오일러 정리 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재함 따라서 그래프 (b)에는 오일러 경로가 존재하지 않음

그래프 정의 그래프 G는 (V, E)로 표시 정점(vertices) 간선(edge) 여러 가지 특성을 가질 수 있는 객체 의미 V(G) : 그래프 G의 정점들의 집합 노드(node)라고도 불림 간선(edge) 정점들 간의 관계 의미 E(G) : 그래프 G의 간선들의 집합 링크(link)라고도 불림

그래프의 종류 무방향 그래프(undirected graph) 방향 그래프(directed graph) A B A B 무방향 간선(undirected edge)만 사용 간선을 통해서 양방향으로 갈수 있음 도로의 왕복통행 길 (A, B)는 A와 B사이의 edge를 의미 (A, B) = (B, A) 방향 그래프(directed graph) 방향 간선(directed edge)만 사용 간선을 통해서 한쪽 방향으로만 갈 수 있음 도로의 일방통행 길 <A, B>는 A에서 B로 가는 edge를 의미 <A, B> ≠ <B, A> A B A B

가중치 그래프 가중치 그래프(weighted graph)는 네트워크(network)라고도 함 간선에 비용(cost)이나 가중치(weight)가 할당된 그래프 가중치 그래프 예 정점 : 각 도시를 의미 간선 : 도시를 연결하는 도로 의미 가중치 : 도로의 길이 1200 A B

그래프 표현의 예 V(G1)= {0, 1, 2, 3},      E(G1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)} V(G2)= {0, 1, 2, 3},      E(G2)= {(0, 1), (0, 2))} V(G3)= {0, 1, 2},         E(G3)= {<0, 1>, <1, 0>, <1, 2>}

부분 그래프(subgraph) 정점 집합 V(G)와 간선 집합 E(G)의 부분 집합으로 이루어진 그래프

degree 인접 정점(adjacent vertex) 무방향 그래프에서 정점의 차수(degree) 하나의 정점에서 간선에 의해 직접 연결된 정점 G1에서 정점 0의 인접 정점: 정점 1, 정점 2, 정점 3 무방향 그래프에서 정점의 차수(degree) 하나의 정점에 연결된 간선의 수 G1에서 정점 0의 차수: 3 무방향 그래프의 모든 차수의 합은 간선 수의 2배 G1의 차수의 합: 10 G1의 간선의 합: 5 자신과 자신을 연결하는 edge (loop)는 degree 계산시 2로 count함

degree 방향 그래프에서 정점의 차수(degree) 진입 차수(in-degree) : 외부에서 오는 간선의 수 진출 차수(out-degree) : 외부로 향하는 간선의 수 G3에서 정점 1의 차수: 진입 차수 1, 진출 차수 2 방향 그래프의 모든 진입(진출) 차수의 합은 간선의 수와 동일 G3의 진입 차수의 합: 3 G3의 간선 합: 3

그래프의 경로(path) 무방향 그래프의 정점 s로부터 정점 e까지의 경로 방향 그래프의 정점 s로부터 정점 e까지의 경로 정점의 나열 s, v1, v2, ..., vk, e 나열된 정점들 간에 반드시 간선 (s, v1), (v1, v2), ... , (vk, e) 존재 방향 그래프의 정점 s로부터 정점 e까지의 경로 나열된 정점들 간에 반드시 간선 <s, v1>, <v1, v2>, ... ,<vk, e> 존재 경로의 길이(length) 경로를 구성하는데 사용된 간선의 수 단순 경로(simple path) 경로 중에서 반복되는 정점이 없는 경로 사이클(cycle) 시작 정점과 종료 정점이 동일한 경로

그래프의 경로(path) G1의 0, 1, 2,3은 경로지만 0, 1, 3, 2는 경로 아님 G1의 0, 1, 2, 0과 G3의 0, 1, 0은 사이클

그래프의 연결정도 연결 그래프(connected graph) 트리(tree) an undirected graph in which any two vertices are connected by exactly one simple path. 트리의 예

그래프의 연결정도 완전 그래프(complete graph) 모든 정점이 연결되어 있는 그래프 n개의 정점을 가진 무방향 완전그래프의 간선의 수: n×(n-1)/2 n=4, 간선의 수 = (4×3)/2 = 6

그래프 ADT 그래프에 정점을 추가하려면 insert_vertex 연산 사용 ∙객체: 정점의 집합과 간선의 집합 ∙연산: ▪ create_graph() ::= 그래프를 생성한다. ▪ init(g) ::= 그래프 g를 초기화한다. ▪ insert_vertex(g,v) ::= 그래프 g에 정점 v를 삽입한다. ▪ insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v)를 삽입한다. ▪ delete_vertex(g,v) ::= 그래프 g의 정점 v를 삭제한다. ▪ delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v)를 삭제한다. ▪ is_empty(g) ::= 그래프 g가 공백 상태인지 확인한다. ▪ adjacent(v) ::= 정점 v에 인접한 정점들의 리스트를 반환한다. ▪ destroy_graph(g) ::= 그래프 g를 제거한다. 그래프에 정점을 추가하려면 insert_vertex 연산 사용 그래프에 간선을 추가하려면 insert_edge 연산 사용

그래프 표현 방법 인접행렬 (adjacent matrix) 방법 인접 행렬의 대각선 성분은 모두 0(자체 간선 불허) if(간선 (i, j)가 그래프에 존재)    M[i][j] = 1, 그렇지않으면                              M[i][j] = 0. 인접 행렬의 대각선 성분은 모두 0(자체 간선 불허) 무방향 그래프의 인접 행렬은 대칭

그래프 표현 방법(cont.) 인접리스트 (adjacency list) 방법 각 정점에 인접한 정점들을 연결리스트로 표현

그래프 탐색 그래프의 가장 기본적인 연산 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결 (예) 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부 (예) 전자회로에서 특정 단자와 다른 단자가 서로 연결되어 있는지 여부

깊이우선 탐색(DFS) 깊이 우선 탐색 (DFS: depth-first search) 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 되돌아가기 위해서는 스택 필요(순환함수 호출로 묵시적인 스택 이용 가능)

DFS 알고리즘 depth_first_search(v) v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면)then depth_first_search(u) 점선: 인접한 노드이긴 하나 이미 방문한 노드이기 때문에 재귀호출을 하지 않는 다는 것을 의미

DFS 프로그램 // 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색 void dfs_mat(GraphType *g, int v) //GraphType은 교재 참조 { int w; visited[v] = TRUE; // 정점 v의 방문 표시 printf("%d ", v); // 방문한 정점 출력 for(w=0; w<g->n; w++) // 인접 정점 탐색 if( g->adj_mat[v][w] && !visited[w] ) dfs_mat(g, w); //정점 w에서 DFS 새로시작 } // 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 void dfs_list(GraphType *g, int v) { GraphNode *w; // GraphNode는 교재 참조 visited[v] = TRUE; // 정점 v의 방문 표시 printf("%d ", v); // 방문한 정점 출력 for(w=g->adj_list[v]; w; w=w->link) // 인접 정점 탐색 if(!visited[w->vertex]) dfs_list(g, w->vertex); //정점 w에서 DFS 새로시작 }

너비우선 탐색(BFS) 너비 우선 탐색(BFS: breadth-first search) 너비우선탐색 알고리즘 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 큐를 사용하여 구현됨 너비우선탐색 알고리즘 breadth_first_search(v) v를 방문되었다고 표시; 큐 Q에 정점 v를 삽입; while (not is_empty(Q)) do Q에서 정점 w를 삭제; for all u ∈ (w에 인접한 정점) do if (u가 아직 방문되지 않았으면) then u를 큐에 삽입; u를 방문되었다고 표시;

BFS 프로그램(인접행렬) void bfs_mat(GraphType *g, int v) { int w; QueueType q; init(&q); // 큐 초기화 visited[v] = TRUE; // 정점 v 방문 표시 printf("%d ", v); // 정점 출력 enqueue(&q, v); // 시작 정점을 큐에 저장 while(!is_empty(&q)){ v = dequeue(&q); // 큐에서 정점 추출 for(w=0; w<g->n; w++) // 인접 정점 탐색 if(g->adj_mat[v][w] && !visited[w]){ visited[w] = TRUE; // 방문 표시 printf("%d ", w); // 정점 출력 enqueue(&q, w); // 방문한 정점을 큐에 저장 }

BFS 프로그램(인접리스트) void bfs_list(GraphType *g, int v) { GraphNode *w; QueueType q; init(&q); // 큐 초기화 visited[v] = TRUE; // 정점 v 방문 표시 printf("%d ", v); // 정점 v 출력 enqueue(&q, v); // 시작정점을 큐에 저장 while(!is_empty(&q)){ v = dequeue(&q); // 큐에서 정점 추출 for(w=g->adj_list[v]; w; w = w->link)//인접 정점 탐색 if(!visited[w->vertex]){ // 미방문 정점 탐색 visited[w->vertex] = TRUE; // 방문 표시 printf("%d ", w->vertex); // 정점 출력 enqueue(&q, w->vertex); // 방문한 정점을 큐에 삽입 }

연결 성분(connected component) 최대로 연결된 부분 그래프들 (a)에는 2개의 연결 성분이 존재 DFS 또는 BFS 반복 이용 DFS 또는 BFS 탐색 프로그램의 visited[v]=TRUE; 를visited[v]=count; 로 교체 visited에 같은 count 값으로 표시된 정점들은 같은 연결 성분에 속함 void find_connected_component(GraphType *g) { int i; // count = 0; 전역변수로 선어되어야 함 for(i=0; i<g->n; i++) if(!visited[i]){ // 방문되지 않았으면 count++; dfs_mat(g, i); }

위상정렬(topological sort) 방향 그래프에서 간선 <u, v>가 있다면 정점 u는 정점 v를 선행함 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열 선수 과목은 과목들의 선행 관계 표현함 위상 순서(topological order) (0,1,2,3,4,5) , (1,0,2,3,4,5) (2,0,1,3,4,5)는 위상 순서가 아님 왜냐하면 2번 정점이 0번 정점 앞에 오기 때문 과목번호 과목명 선수과목 전산학개론 없음 1 이산수학 2 자료구조 3 알고리즘 분석 0, 1, 2 4 운영체제 5 인공지능 2, 3, 4

위상정렬 알고리즘 Input: 그래프 G=(V,E) Output: 위상 정렬 순서 topo_sort(G) for i←0 to |V| do if( 모든 정점이 선행 정점을 가지면 ) then 사이클이 존재하고 위상 정렬 불가; 선행 정점을 가지지 않는 정점 v 선택; v를 출력; v와 v에서 나온 모든 간선들을 그래프에서 삭제;

위상정렬의 예 (c) (d) (e) (f)

위상정렬 프로그램 void topo_sort(GraphType *g) { int i; StackType s; GraphNode *node; // 모든 정점의 진입 차수를 계산 int *in_degree = (int *)malloc(g->n* sizeof(int)); for(i = 0; i < g->n; i++) // 초기화 in_degree[i] = 0; for(i = 0; i < g->n; i++){ GraphNode *node = g->adj_list[i]; // 정점 i에서 나오는 간선들 while ( node != NULL ) { In_degree[node->vertex]++; node = node->link; }

위상정렬 프로그램(cont.) // 진입 차수가 0인 정점을 스택에 삽입 init(&s); for(i = 0; i < g->n; i++){ if( in_degree[i] == 0 ) push(&s, i); } // 위상 순서를 생성 while(!is_empty(&s)){ int w; w = pop(&s); printf("%d", w); node = g->adj_list[w]; // 각 정점의 진입 차수를 변경 while (node != NULL) { int u = node->vertex; in_degree[u]--; // 진입 차수를 감소 if(in_degree[u] == 0) push(&s, u); node = node->link; // 다음 정점 free(in_degree); return;