Chapter 10 그래프(graph) SANGJI University Kwangman KO (kkman@sangji.ac.kr)

그래프(graph) 그래프 연결되어 있는 객체간의 관계를 표현하는 자료구조 다양한 모델에 적용할 수 있는 유연성 있는 자료구조 예: 전기회로, 프로젝트관리, 지도에서 도시들의 연결 다양한 모델에 적용할 수 있는 유연성 있는 자료구조 꼭지점(vertex)와 변(edge)으로 구성 물리적인 모델링이나 추상적인 모델 모두에 쉽게 적용.

그래프 역사 오일러 문제 문제의 핵심만을 표현 오일러 경로 1800년대 오일러에 의하여 창안 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제 문제의 핵심만을 표현 위치: 정점(node) 다리: 간선(edge) 오일러 경로 정점에 연결된 간선의 개수가 짝수이면 존재

그래프 용어 그래프는 (V, E)로 표시 (예) 예제 그래프 V는 정점(vertices)들의 집합 E는 간선(edge)들의 집합 정점과 간선은 모두 관련되는 데이터를 저장 (예) 예제 그래프 정점은 각 도시를 의미 간선은 도시를 연결하는 도로를 의미 간선에는 도로의 길이등의 데이터가 저장될 수 있음

인접(adjacency) 경로(path) 두 꼭지점이 하나의 변으로 연결 되어 있는 경우 A와 B, B와 C, B와 E, D와 E는 인접. 경로(path) 두 꼭지점을 연결하는 변들의 연결 경로에서는 꼭지점과 변이 교대로 나타나지만 연결된 꼭지점의 나열로 표기. A와 D사이의 경로는 ABED

그래프의 종류 무방향 그래프(undirected graph) 연결된 그래프(connected graph) 무방향 간선 간선을 통해서 양방향으로 갈수 있음을 표현 (A, B)와 같이 정점의 쌍으로 표현 (A, B) = (B, A) A B

그래프(directed graph)로 구분 방향간선 방향성이 존재하는 간선으로 도로의 일방 통행길과 마찬가지로 한쪽 방향으로만 갈 수 있음을 표시 A, B>로 표시, <A, B> ≠ <B, A> A B

가중치 그래프(weighted graph) 간선에 비용이나 가중치가 할당된 그래프 A B 1200

그래프 표현의 예 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(G3)= {(0, 1), (0, 2))} V(G2)= {0, 1, 2},         E(G2)= {<0, 1>, <1, 0>, <1, 2>}

그래프 용어 인접 정점(adjacent vertex) 차수(degree) 경로(path) 간선에 의해 연결된 정점 정점 0와 정점 1 차수(degree) 정점에 연결된 다른 정점의 개수 정점 0의 차수는 3 경로(path) 정점의 나열로 표현 단순경로: 0, 1, 2, 3 사이클(cycle): 0, 1, 2, 0

경로의 길이 경로를 구성하는데 사용된 간선의 수 완전그래프 모든 정점이 연결되어 있는 그래프

그래프 ADT ∙객체: 정점의 집합과 간선의 집합 ∙연산: ▪ 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를 제거

그래프 표현 방법 그래프 표현 방법 인접 행렬(adjacent matrix) 2차원 배열 사용 표현 인접 리스트(adjacency list) 연결리스트를 사용 표현

인접 행렬 간선 (i, j)가 그래프에 존재, M[i][j] = 1

인접 리스트 각 정점에 인접한 정점들을 연결 리스트로 표현 각 꼭지점은 자신의 연결 리스트를 하나씩 유지 자신의 연결 리스트에 자신이 연결된 꼭지점을 항목으로 추가

그래프 탐색 탐색 전체 그래프를 검색하기 위하여 한 꼭지점에서 시작하여 주변 꼭지점들을 순서에 맞추어 방문하는 과정 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문 종류 깊이 우선 탐색(Depth First Search; DFS) 너비 우선 탐색(Breadth First Search; BFS)

깊이 우선 탐색(DFS) 특징 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사 시작 꼭지점에서 멀어지는 방향으로 탐색. 스택을 이용하여 구현

단계 1 단계 2 단계 3 단계 4 스택에서 꼭지점 pop. 스택에 아무것도 없으면 탐색을 종료 꺼내온 꼭지점으로 이동하고 방문 표시 단계 3 현재 꼭지점에 연결된 다른 꼭지점들을 찾아서 해당 꼭지점에 방문한 적이 없으면 스택에 push 단계 4 현재의 꼭지점에 연결되어있고 방문하지 않은 꼭지점들을 모두 스택에 넣고 나면 단계 1로 돌아간다.

스텝 스택 탐색한 꼭지점 1 A 2 B, F, G 3 B, F, H A, G 4 B, F A, G, H 5 B A, G, H, F 6 C, D A, G, H, F, B 7 C, E A, G, H, F, B, D 8 C A, G, H, F, B, D, E 9 A, G, H, F, B, D, E, C

DFS 프로그램 // 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색 void dfs_mat(GraphType *g, int v) { 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; 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) 특징 시작 꼭지점에서 먼 순서대로 탐색 진행 시작 정점으로부터 가까운 정점을 먼 저 방문하고 멀리 떨 어 져 있는 정점을 나 중 에 방문하는 순 회 방 법 시작 꼭지점에서 같은 거리에 있는 꼭지점들부터 선택 큐를 이용하여 구현

단계 1 단계 2 단계 3 단계 4 큐에서 꼭지점을 하나 꺼내온다. 큐에 아무것도 없으면 탐색을 종료 꺼내온 꼭지점으로 이동하고 방문 표시 단계 3 현재 꼭지점에 연결된 다른 꼭지점들을 찾아서 해당 꼭지점에 방문한 적이 없으면 (방문 표시가 없으면) 큐에 집어넣는다. 단계 4 현재의 꼭지점에 연결되어있고 방문하지 않은 꼭지점들을 모두 스택에 넣고 나면 단계 1로 돌아간다.

스텝 큐 탐색한 꼭지점 1 A 2 B, F, G 3 F, G, C, D A, B 4 G, C, D A, B, F 5 C, D, H A, B, F, G 6 D, H A, B, F, G, C 7 H, E A, B, F, G, C, D 8 E A, B, F, G, C, D,H 9 A, B, F, G, C, D,H, E

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); // 방문한 정점을 큐에 저장 }

연결 성분 연결 성분(connected component) 최대로 연결된 부분 그래프들을 찾는 것 그래프 탐색으로 찾을 수 있다. visited[i]=count;

위상 정렬 위상 정렬(topological sorting) 방향 그래프 그래프를 이용한 정렬 방법 방향 그래프에서 꼭지점을 연결하는 변들의 방향 이용 방향 그래프 그래프의 변이 방향을 가지고 있어서, 방향에 따라 두 꼭지점의 연결 여부가 결정 인접 행렬과 인접 리스트가 모두 사용

방향 그래프 방향 그래프에서의 인접 행렬과 인접 리스트

방향 그래프 순환과 연결 방향 그래프의 순환 방향 그래프에서도 연결된 꼭지점에 따라 경로 설정 순환(cycle) 경로의 시작과 끝이 연결된 그래프 Directed Acyclic Graph, DAG 순환을 가지지 않는 방향 그래프 위상 정렬 수행

방향그래프의 연결 한 꼭지점에서 연결될 수 있는 꼭지점의 집합 이렇게 찾은 꼭지점의 집합의 역은 성립되지 않음 Warshall 알고리즘 이용.

위상 정렬 방향 그래프에 의해 정해진 순서를 따라 정렬하는 방법 DAG를 기반 선수과목 체계 조건을 만족하는 여러가지 결과가 가능 방향 그래프에서 간선 <u, v> 정점 u는 정점 v를 선행 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

정렬 결과 1: 컴퓨터 공학 기초 -> 프로그래밍 기초 -> C 프로그래밍 -> 객체지향 기초 -> Java 프로그래밍 -> Python 프로그래밍 -> Perl 프로그래밍 정렬 결과 2: 프로그래밍 기초 -> 컴퓨터 공학 기초 -> 객체지향 기초 -> C 프로그래밍 -> Java 프로그래밍 -> Perl 프로그래밍 -> Python 프로그래밍

위상 정렬 수행 단계 단계 1. 자신을 가리키는 변이 없는 꼭지점을 찾는다. 단계 2. 찾은 꼭지점을 출력하고 찾은 꼭지점과 그 꼭지점에서 출발하는 변들을 그래프에서 지운다. 단계 3. 아직 그래프에 꼭지점이 남아 있으면 단계 1로 돌아가고, 남아 있지 않으면 위상 정렬을 종료.

과목번호 과목명 선수과목 전산학개론 없음 1 이산수학 2 자료구조 3 알고리즘 분석 0, 1, 2 4 운영체제 5 인공지능 2, 3, 4 위상정렬: (0,1,2,3,4,5) , (1,0,2,3,4,5) (2,0,1,3,4,5)는 위상 정렬 2번 정점이 0번 정점 앞에 오기 때문이다. 간선 <0, 2>이 존재하기 때문에 0번 정점이 끝나야 만이 2번 정점을 시작할 수 있다.

가중치 그래프 가중치 그래프(weighted graph) 그래프의 변에 가중치를 부여한 그래프 가중치(weight) 한 꼭지점에서 다른 꼭지점 사이를 이동하기 위해 소요되는 비용 인접행렬과 인접 리스트의 방법이 모두 가능 인접 행렬의 방법이 좀더 단순

인접 행렬을 이용한 방법 꼭지점간 연결이 1에서 설정된 가중치로 표기

인접 리스트를 이용한 구현 연결 정보와 함께 가중치 정보 저장

신장 트리 신장 트리(spanning tree) 신장 트리 검색 그래프내의 모든 정점을 포함하는 트리 모든 정점들이 연결 사이클을 포함할 수 없음 그래프내의 n개의 정점, n-1개의 간선으로 연결 신장 트리 검색 깊이 우선 탐색, 너비 우선 탐색에 사용된 간선의 집합

신장 트리 용도 최소의 링크를 사용하여 네트워크를 구축하고 싶은 경우 도로 건설 - 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제 전기 회로 - 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제 통신 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 배관 - 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

최소 신장 트리 최소 신장 트리(minimum spanning tree) 모든 꼭지점을 연결할 수 있도록 최소한의 변만 선택한 그래프 그래프의 부분 집합의 개념 한 그래프에서 여러 최소 신장 트리 구성 가능 E = V -1 E : 최소 신장 트리에서 필요한 변의 수 V : 그래프에 있는 모든 꼭지점의 수

최소 신장 트리의 구현, DFS 이용 DFS는 그래프의 연결된 변을 따라 탐색을 수행하기 때문에 적용 하나의 꼭지점에서 연결된 다른 꼭지점을 찾는 과정을 반복적으로 수행하며 모든 꼭지점을 방문. 지나온 변들이 최소 신장 트리를 구성

MST 알고리즘 2가지의 대표적인 알고리즘 Kruskal의 알고리즘 Prim의 알고리즘

Kruskal의 알고리즘 탐욕적인 방법(greedy method) 알고리즘 설계에서 있어서 중요한 기법 중의 하나 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달 탐욕적인 방법은 항상 최적의 해답을 주는지를 반드시 검증해야 한다. Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명

특징 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 그래프의 간선 가중치의 오름차순으로 정렬 정렬된 간선들의 리스트중 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가 사이클을 형성하면 그 간선은 제외

Kruskal의 MST 알고리즘의 구현 union-find 알고리즘 집합들의 합집합을 구하고 집합의 원소가 어떤 집합에 속하는지를 계산하는 알고리즘 여러가지 방법으로 구현이 가능 Kruskal의 MST 알고리즘에서 사이클 검사에 사용

a와 b가 같은 집합에 속함 a와 b가 다른 집합에 속함

Prim의 MST 알고리즘 특징 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함 앞 단계에서 만들어진 신장 트리 집합에, 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장 트리가 n-1개의 간선을 가질 때까지 계속.

간선 (a, b)와 간선 (f, e)의 가중치를 비교해보면 (f, e)가 27로서 (a, b)의 29보다 높다 간선 (a, b)와 간선 (f, e)의 가중치를 비교해보면 (f, e)가 27로서 (a, b)의 29보다 높다. 따라서 (f, e) 간선이 선택되고 정점 e가 신장 트리 집합에 포함된다.

Prim의 MST 알고리즘

Prim의 MST 알고리즘

Prim의 MST 알고리즘

최단 경로 알고리즘 최단 경로(shortest path) 문제 네트워크에서 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제 간선의 가중치는 비용, 거리, 시간 등 그래프를 적용하는 가장 보편적인 경우 가중치와 방향을 모두 가지는 그래프를 기준으로 하여 최단 경로 탐색 과정 수행

Dijkstra의 최단 경로 알고리즘 Dijkstra 알고리즘 꼭지점에서 시작해서 주변 꼭지점으로 퍼져가며 최단 경로 탐색 단계 단계 1: 현재 선택된 꼭지점을 ‘고정’으로 표시 단계 2: 선택된 꼭지점에 연결된 변들을 통하여 다른 꼭지점들까지 연결되는 더 짧은 경로가 있는 지를 확인, 더 짧은 경로가 있다면 꼭지점의 ‘거리정보’를 갱신 단계 3: 각 꼭지점까지의 거리를 확인하여 ‘고정’으로 표시 되지 않은 꼭지점 중 거리가 가장 짧은 꼭지점을 선택

단계 4: 모든 꼭지점이 ‘고정’으로 표시되었으면 최단 경로 탐색을 중지하고 아니면 단계 1로 돌아간다. (고정 : 해당 꼭지점에 대한 최단 경로 탐색이 완료 되었기 때문에 이를 확정하고 더 이상 고려하지 않음을 의미) 집합 S: 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합 distance 배열 최단 경로를 알려진 정점만을 통하여 각 정점까지가는 최단경로의 길이 매단계에서 가장 distance 값이 적은 정점을 S에 추가.

매단계에서 새로운 정점이 S에 추가되면 distance값을 갱신

최단 경로 탐색 결과 각 꼭지점이 자기의 전 꼭지점으로 가리키고 있는 꼭지점을 거꾸로 올라가면 최단 경로 도시 경로 대전 서울-대전 강릉 서울-강릉 대구 서울-강릉-대구 광주 서울-대전-광주 부산 서울-강릉-대구-부산