CHAP 10:그래프 (1) 2016. 9. 22 순천향대학교 하상호

목차 그래프 개요 그래프 표현 그래프 탐색 연결 성분 신장 트리 최소비용 신장 트리 최단 경로 위상정렬

그래프 그래프(graph): 연결되어 있는 객체간의 관계를 표현하는 자료구조 그래프의 예: 전기회로, 프로젝트관리, 지도에서 도시들의 연결 그래프: 아주 일반적인 자료구조 (예) 트리도 그래프의 일종으로 볼수 있다. 그래프 이론(graph theory): 그래프를 문제해결의 도구로 이용하는 연구분야로 많은 이론과 응용이 존재

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

그래프 용어(1) 그래프는 2개의 집합, (V, E)의 정의 예제 그래프 V는 정점(vertices)들의 집합 E는 간선(edge)들의 집합 V(G), E(G)는 G의 정점들의 집합, 간선들의 집합 표현 G = (V, E)는 한 개의 그래프 표현 예제 그래프 정점은 각 도시를 의미한다. 간선은 도시를 연결하는 도로를 의미한다. 간선에는 도로의 길이등의 데이터가 저장될 수 있다.

그래프 표현의 예 V(G1)= ?     E(G1)= ? V(G2)= ? E(G3)= ? V(G2)= ?         E(G2)= ?

그래프의 종류 간선의 종류에 따른 구분: 정점쌍에 순서 존재 여부 무방향 그래프(undirected graph) 무방향 간선: 간선을 통해서 양방향으로 갈수 있음을 나타내며 (A, B)와 같이 정점의 쌍으로 표현 (A, B) = (B, A) 방향 그래프(directed graph)로 구분 방향간선: 방향성이 존재하는 간선으로 도로의 일방통행길과 마찬가지로 한쪽 방향으로만 갈 수 있음을 나타낸다. <A, B>로 표시한다. <A, B>에서, A는 꼬리(tail), B는 머리(head)라 함. <A, B> ≠ <B, A> 가중치 그래프(weighted graph), 네트워크(network): 간선에 비용이나 가중치가 할당된 그래프 A B A B 1200 A B

그래프 표현 예: more Q: 트리는 그래프인가? Q: (v1, v2) 또는 <v1, v2>가 E(G)에 속하면, v1 ≠ v2? Q: G는 동일한 간선을 여러 개 포함할 수 있는가? Q: G가 무방향 그래프이고, |V(G)| = n일 때, 최대 간선의 개수는? - 이러한 그래프를 완전 그래프(complete graph)라 한다 - G가 방향그래프이면, 최대 간선의 개수는?

그래프 용어(2) 인접 (adjacent)과 부속(incident) (v1, v2) ∈ E(G)이면, v1, v2는 인접되어 있다고 한다. (v1, v2)는 v1, v2에 부속되어 있다고 한다. 예제: G1에서 정점 0에 인접된 정점들은? G1에서 정점 3에 부속된 간선은?

그래프 용어(3) 부분 그래프(subgraph) G=(V, E), G’ = (V’, E’)에서, 다음을 만족하면 G’은 G의 부분 그래프이다. V(G’) ⊆ V(G), E(G’) ⊆ E(G) 예제: 다음 G1에서 부분 그래프를 식별하시오.

복습 다음 그래프 G에 대해서 답하시오. 4 1 5 V(G) = ? E(G)= ? 정점 1에 인접된 정점들은? 정점 1에 부속된 간선은? G의 부분 그래프는? G는 완전 그래프인가? 4 1 5

그래프 용어(4) 경로(path)는 정점의 나열로 표현 G에서 정점 vp부터 vq까지의 경로는 다음 정점들의 시퀀스이다. vp, vi1, vi2, … vin, vq where (vp, vi1), (vi1, vi2), …. (vin, vq) ∈ V(G) 예제: G1에서, 정점 0부터 정점 3까지의 경로는? G가 방향 그래프이면, 방향 경로(directed path)로 정의 <vp, vi1>, <vi1, vi2>, ….<vin, vq>

그래프 용어(4-2) 경로의 길이(path length) 단순경로(simple path) 사이클(cycle) 경로를 구성하는데 사용된 간선들의 개수 단순경로(simple path) 처음과 끝의 정점을 제외하고는 모든 정점들이 서로 다른 경로 예: 0, 1, 2, 3 사이클(cycle) 처음과 끝의 정점이 동일한 단순 경로 방향 그래프에서는 방향 사이클(directed cycle)이라 함 예: 0, 1, 2, 0

복습 다음 그래프 G에 대해서 답하시오. 4부터 1까지의 경로는? 경로 4, 0, 5, 1과 4, 0, 5, 0을 고려 위 경로의 길이는? 어느 것이 단순 경로인가? 사이클을 식별하라. 4 1 5

그래프 용어(5) 연결 그래프(connected graph) 4 1 4 1 2 3 5 5 G2 G1 무방향 그래프 G에서, 두 정점 v1, v2간에 경로가 존재하면, v1, v2는 연결되어 있다고 한다. V(G)의 임의 두 정점 vi, vj에 대해서, vi로부터 vj간에 경로가 존재하면, G는 연결되어 있다고 한다. 예제: 다음 그래프 G1, G2는 연결되어 있는가? 4 1 4 1 2 3 5 5 G2 G1

그래프 용어(6) 연결 컴포넌트(connected component, 연결 성분) 4 1 4 1 2 3 5 5 G2 G1 최대로 연결된 부분 그래프(maximal connected subgraph) 연결된 부분 그래프들중에서 크기가 최대인 것 예제: 다음 그래프에서 연결 성분을 찾아라. 4 1 4 1 2 3 5 5 G2 G1

문제 다음 그래프 G에 대해서 답하시오. G4는 연결되어 있는가? G의 연결 성분은? 1 5 3 2 6 7 4 8

그래프 용어 (7) 강연결 그래프(strongly connected graph) 방향 그래프 G에서, V(G)의 임의 두 정점 vi, vj에 대해서, vi로부터 vj까지의 방향 경로가 존재하고, vj로부터 vi로의 방향 경로가 존재하면 G는 강연결되어 있다고 한다. 강연결 컴포넌트(strongly connected component) 최대로 강 연결된 부분 그래프 예제: G는 강연결되어 있는가? 강연결된 컴포넌트는? 1 2 3

그래프 용어(8) 정점의 차수 1 2 3 정점의 차수는 그 정점에 부속된 간선들의 개수이다. 예제: G1에서 정점 0의 차수는? 방향 그래프에서, 정점 v의 진입 차수(in-degree)는 외부에서 들어 오는 간선의 개수이고, 진출 차수(out-degree)는 외부로 향하는 간선의 개수이다. 예제: G에서, 정점 2의 진입 차수 진출 차수 차수는? 1 2 3

그래프 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를 제거한다. 그래프에 정점을 추가하려면 insert_vertex 연산을 사용하고 간선을 추가하려면 insert_edge 연산을 사용한다.

그래프 표현 방법 그래프를 표현하는 2가지 방법 인접행렬 방법 인접행렬(adjacent matrix): 2차원 배열 사용 표현 인접리스트(adjacency list): 연결리스트를 사용 표현 인접행렬 방법 G=(V, E), |V| = n이면, G의 인접행렬은 n*n 행렬 M M[i,j] = 1 iff (vi, vj) ∈E(G) <vi, vj> ∈E(G) for 방향 그래프 G = 0 iff otherwise 예제: G1의 인접행렬 표현은?

그래프 표현 방법: 인접 행렬 무방향 그래프에서 인접 행렬은 대칭적인가? 방향 그래프에서 인접행렬은 대칭적인가? 즉, (vi, vj) ∈E(G) iff (vj, vi) ∈E(G) 그렇다면, 행렬의 상위나 하위 삼각형 부분만 저장 가능 방향 그래프에서 인접행렬은 대칭적인가? G=(V, E), |V| = n일 때, 인접행렬 표현을 위한 필요한 메모리양은? ( ?bits) 두 정점 i, j간에 간선의 존재 여부를 어떻게 아는가? 정점 i의 차수를 어떻게 구하는가? G상에 존재하는 간선의 개수를 어떻게 구하는가?

그래프 표현 방법: 인접 행렬 다음 그래프의 인접 행렬 표현은? 1 2 3 진입 차수는 어떻게 구하는가? 진출 차수는 어떻게 구하는가? 1 2 3

그래프 표현: 인접 리스트 인접리스트 표현 … G=(V, E), |V| = n이면, n개의 연결리스트로 표현 각 정점에 대해서 한 개의 리스트 존재 정점 i의 리스트에 속한 노드들은 i에 인접한 정점들로 구성 노드 구조: (vertex, link) 각 리스트는 헤더 노드를 포함 예제: G1의 인접 리스트 표현은? Vi의 header Vi에 인접한 정점들 v1 link v2 link …

그래프 표현: 인접리스트 G=(V, E), |V| = n, |E| = e이면, G에 대한 인접리스트에서 헤더 노드의 개수는? 리스트의 노드 개수는? 두 정점 i, j간에 간선의 존재 여부를 어떻게 아는가? 정점 i의 차수를 어떻게 구하는가? G상에 존재하는 간선의 전체 개수를 어떻게 구하는가? 인접리스트는 희소 그래프(sparse graph) 표현에 적합

그래프 표현 방법: 인접 리스트 다음 그래프의 인접 리스트 표현은? 1 2 3 진입 차수는 어떻게 구하는가? 진출 차수는 어떻게 구하는가? 1 2 3

그래프 구현 다음 그래프 표현에 대해서 그래프 ADT를 구현하라.(교재 참고) 인접 행렬 #define MAX 50 ∙객체: 정점의 집합과 간선의 집합 ∙연산: ▪ 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를 제거한다. #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType void graphInit( graphType *g); void insetVertex(graphType *g, int vertex); void insetEdge(graphType *g, int u, int v);

그래프 연산: 인접 행렬 #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType void graphInit( graphType *g) { int r, c; g->n = 0; for (r=0; r<MAX; r++) for (c=0; c<MAX; c++) g->adjMat[r][c] = 0; }

그래프 연산: 인접 행렬 #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType void insetVertex(graphType *g, int vertex) { }

그래프 연산: 인접 행렬 #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType void insetEdge(graphType *g, int start, int end) { }

그래프 구현 다음 그래프 표현에 대해서 그래프 ADT를 구현하라.(교재 참고) 인접 리스트 #define MAX 50 ∙객체: 정점의 집합과 간선의 집합 ∙연산: ▪ 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를 제거한다. #define MAX 50 typedef struct graphNode { int vertex; // 정점 struct graphNode *link; } graphNode; typedef struct graphType { int n; // 정점 개수 graphNode * adjList[MAX]; } graphType; void graphInit(graphType *g); void insertVertex(graphType *g, int vertex); void insertEdge(graphType *g, int u, int v);

그래프 연산: 인접 리스트 #define MAX 50 Typedef struct GraphNode { int vertex; struct GraphNode *link; } GraphNode; typedef struct graphType { int n; // 정점 개수 GraphNode adjList[MAX]; // 인접 리스트 } graphType void graphInit( graphType *g) int v; g->n = 0; for (v=0; r<MAX; r++) g->adjList[v] = NULL: }

그래프 연산: 인접 리스트 #define MAX 50 Typedef struct GraphNode { int vertex; struct GraphNode *link; } GraphNode; typedef struct graphType { int n; // 정점 개수 GraphNode adjList[MAX]; // 인접 리스트 } graphType void insetVertex(graphType *g, int vertex) }

그래프 연산: 인접 리스트 #define MAX 50 Typedef struct GraphNode { int vertex; struct GraphNode *link; } GraphNode; typedef struct graphType { int n; // 정점 개수 GraphNode adjList[MAX]; // 인접 리스트 } graphType void insetEdge(graphType *g, int start, int end) }

Quiz 다음 그래프를 인접 행렬과 인접 리스트로 각각 표현하라. 1 2 3 4

문제 각 그래프 표현(인접 행렬, 인접 리스트)에 대해서, 다음을 구하는 알고리즘을 작성하라. 두 정점 i, j간에 간선의 존재 여부를 판단하라: 정점 i의 차수를 구하라: G상에 존재하는 간선의 전체 개수를 구하라: