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

Presentation on theme: "CHAP 10:그래프 (2) 2016. 9. 27 순천향대학교 하상호."— Presentation transcript:

1 CHAP 10:그래프 (2) 순천향대학교 하상호

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

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

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

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

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

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

8 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++) do repeat0 end dfs_mat #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType

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

10 너비 우선 탐색 너비 우선 탐색(breath first search: BFS)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 시작 정점 1 2 3 4

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

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

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

14 BFS 알고리즘(2) bfs(v: vertex) visited[v] = true;
initQueue(q); // q is a queue addQueue(q, v); while (not is_empty(q)) do repeat end bfs

15 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)) do repeat end bfs_mat #define MAX 50 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType

16 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)) do repeat end bfs_list #define MAX 50 typedef struct graphNode { int vertex; // 정점 struct graphNode *link; } graphNode; typedef struct graphType { int n; // 정점 개수 graphNode * adjList[MAX]; } graphType;

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

18 코드: 프로그램 10.5

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

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

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

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