CHAP 10:그래프 2015. 9. 14 순천향대학교 하상호

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

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

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

그래프 용어(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상에 존재하는 간선의 전체 개수를 구하라:

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

그래프 탐색(cont.) 그래프 탐색(순회)의 2가지 방법 깊이우선탐색(DFS: depth-first search) 너비우선탐색(BFS: breadth-first search) 깊이 우선 탐색은 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

DFS 알고리즘 정점 v를 방문한다 v에 인접한 방문되지 않은 정점 w를 선택하고, w로부터 깊이 우선 방문 정점 u의 인접된 모든 정점들이 이미 방문되었으면, 가장 최근에 방문하였고, 아직 방문되지 않은 인접한 정점 w를 갖는 정점까지 거슬러 올라가서, W부터 깊이 우선 방문한다

Quiz: DFS 다음 그래프에서 0을 시작 정점으로 하여 깊이 우선 탐색 하라. 1 2 3 4

DFS 알고리즘 dfs(v: vertex) // 전역 변수 visited[1..n]가 false로 초기화 되었다고 가정 { visited[v] = true; for (v에 인접한 각 정점 w에 대해서) { }

DFS 코드 (인접 행렬) *g로 전달되지 않음에 유의할 것 int visited[MAX_VERTICES]; // FALSE로 초기화되었다고 가정 // 방문 여부를 기록 dfs_mat(GraphType g, int v) { int w; visited[v] = TRUE; for (w = 0; w < g.n; w++) { } #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType

DFS 코드 (인접 리스트) int visited[MAX_VERTICES]; // FALSE로 초기화되었다고 가정 dfs_list(GraphType g, int v) { GraphNode *w; visited[v] = TRUE; for (w = g.adj_list[v]; w != NULL; w = w.link) } #define MAX 50 typedef struct graphNode { int vertex; // 정점 struct graphNode *link; } graphNode; typedef struct graphType { int n; // 정점 개수 graphNode * adjList[MAX]; } graphType;

BFS 알고리즘 정점 v를 방문한다 v에 인접한 방문되지 않은 모든 정점 w를 방문 W에 인접한 방문되지 않은 모든 정점 w를 방문 …

BFS 구현 큐를 사용하여 구현됨

Quiz: BFS 다음 그래프에서 2를 시작 정점으로 하여 너비 우선 탐색 하라. 1 2 3 4

BFS 알고리즘(2) bfs(v: vertex) { visited[v] = true; initQueue(q); // q is a queue addQueue(q, v); while (not emptyQueue(q)) { }

BFS 코드 (인접 행렬) int visited[MAX_VERTICES]; // FALSE로 초기화되었다고 가정 bfs_mat(GraphType g, int v) { int w; QueueType q; init(&q); visited[v] = TRUE; enqueue(&q, v); while (!isEmpty(q)) { } #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType 알고리즘 복잡도는?

BFS 코드 (인접 리스트) 알고리즘 복잡도는? int visited[MAX_VERTICES]; // FALSE로 초기화되었다고 가정 bfs_list(GraphType g, int v) { GraphNode *w; QueueType q; init(&q); visited[v] = TRUE; enqueue(&q, v); while (!isEmpty(q)) { } #define MAX 50 typedef struct graphNode { int vertex; // 정점 struct graphNode *link; } graphNode; typedef struct graphType { int n; // 정점 개수 graphNode * adjList[MAX]; } graphType; 알고리즘 복잡도는?

복 습 다음 그래프 G에 대해서 답하시오. 인접리스트 표현은? dfs에 의한 방문 순서는? 2 1 3 4 5 6 7 8

코드: 프로그램 10.5

연결 그래프 연결 그래프란? 그래프 G가 주어지면, G가 연결되어있는지 어떻게 알 수 있는가? 2 1 4 5 3

연결 성분 연결 성분이란? 그래프 G가 주어지면, G의 연결 성분을 어떻게 구할 수 있는가?

연결 성분 찾기 알고리즘 Comp(g: graph) { int visited[n] = {0}; // 모든 정점을 방문되지 않은 상태로 초기화 for (g에 속한 각 정점 v 에 대해서) { }

연결 성분 찾기 알고리즘 다음 그래프에 대해서 알고리즘을 적용한 결과는? Visited[] 원소값이 true/false가 아닌 counter 값 저장 다음 그래프에 대해서 알고리즘을 적용한 결과는? Counter는 전역 변수 void find_connected_component(GraphType g) { int v; // visited[] = {0}으로 초기화되었다고 가정 count = 0; for(v=0; v<g.n; v++) // 각 정점에 대해서 } dfs_mat()의 함수가 어떻게 변경되어야 하는가?