Chapter 14. 그래프(Graph)

#14-1. 그래프의 이해와 종류1

그래프는 '이산수학'에서 배운다. 선택과목으로 이산수학으로 배운다. 그래프.. 길 찾기..

알고리즘 측면에서 바라보았을 때 그래프가 할 이야기가 많이 있다. 자료구조 레벨에서 그래프를 이야기 하고자 한다.

쾨니히스베르크의 다리 문제 : 늘 실패 할 수 밖에 없다. 이것을 밝혀내는 것이 그래프의 시작이다. 

동그라미 정점

선          간선

다리 숫자를 적어 놓는거 밖에 지나지 않는다. 정점과 간선의 모임이다. 그래프 알고리즘이라고 말한다. 

저장한다는거보다는 표현이 강하다. 표현방법 보다는 다수의 알고리즘이 많이 나온다.

#14-1. 그래프의 이해와 종류2

비상 연락망도 정점과 산언을 이용해서 연결되어 있다. 연락의 방향성이 없다. 

그래프의 방향성을 이야기 하기 위해서 예를 든 것이다. 

방향 그래프의 예, 무방향 그래프의 예.

완전 그래프보다 방향 완전 그래프가 간선의 수가 더 많을 수 밖에 없다.

#14-1. 그래프의 이해와 종류3

그래프의 집합 표현

그래프 G의 정점 집합 V(G)

그래프 G의 간선 집합 E(G)

V(G1) = {A, B, C, D}

E(G1) = {(A, B), (A, C), (A, D), (B,C), (C, D)}

꺽여 있으면 방향 그래프이다 <A, B> // A에서 B로..

#14-1. 그래프의 이해와 종류4

그래프의 구현이 최종 목적이 아니다. 그래프의 종류를 담아 두는 것이다. 

그 구 X  r s c  그래프의 표현이 목적이다. 표현해서 그 안에 정보 즉 데이터를 담아 두기 위한 것이다. 

그래프의 ADT를 표현하는 것이 목적이다. 정점과 간선을 삽입 및 삭제하기 위한 것이 목적이다. 그래프의 표현이 다 가능하도록..

실무에서는 그래프의 표현이 확실하다. 바꾸는 내용이 거희 없다. 코드 레벨에서 완성을 시킬 수 있다. 실무에서는 구현하고 마는 경우가 많다. 그래프의 표현을 SUPER로 정의할 필요가 없다. 그래프의 표현 적정한 수준의 ADT를 정의할 수 있는 수준이면 된다. 

enum{SEOUL, INCHEON, DAEGU, BUSAN, KWANGJU}

* 그래프를 구현하는 두 가지 방법 : 인접 행렬 기반

정방 행렬을 이용하는 '인접 행렬 기반 그래프'의 예1

   A  B  C  D 

A  0  1  1  1

B  1  0  1  0

C  1  1  0  1

D  1  0  1  0

이러한 배열 정보 선언해서 간선 정보 표현하겠다. 

A > B > C > D

B > A

C > A

D > A

#14-2. 인접 리스트 기반의 그래프 구현

A > B > C > D

B > A

C > A

D > A

80 % ~ 90 % 정도 될 것이다!!

길이가 5인 배열이 만들어진다. 초기화를 거쳐야 한다. 

그래프와 연관성 없다! 다만 연결 리스트가 요구하므로 적당한 함수를 등록하였다!

#14-3. 그래프의 탐색1

깊이 우선 탐색 DFS

너비 우선 탐색 BFS

2가지가 있다. 개발해 보시라~

깊이 우선 탐색~ 무엇인가를 찾는다. 정점에 돌아다녀야 한다. 탐색의 잇슈는 모든 정점에 돌아다닌다. 

모든 정점에 돌아당기는 방법에 대해서 이야기 한다. 이유가 없어도 구조의 틀은 있었다. 

그래프 구조는 구조가 없다. 정형화된 틀이 없다. 그래프는 내용에 따라서 어떻게 구성될 지 모른다. 내용이 빠져버리면 그래프 설명 할 수 없다.

깊이 우선 탐색 모든 정점에 방문 할 수 있지 않을까??

#14-3. 그래프의 탐색2

깊이 우선 탬색, DFS(Depth First Search) 깊이를 우선시 한다. 깊이 파고 들어가는 방식에 대해 탐색하는 방법을 깊이 우선 탐색이다.

다 깊이 우선 탐색 범주 안에 있다.

* 한 사람에게만 연락을 한다

* 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알린다.

* 처음 연락을 시작한 사람의 위치에서 연락은 끝이 난다.

동수에서 시작하면 동수에서 끝이 난다. 동수가 마지막 연락할 기회를 얻었다. 다시 기회를 얻었다. 내 주변 연락 취할 사람 있는지 찾는다. 찾아보니 연락할 사람 없다. 그러면 연락할 사람 없어. 그러면 연락오고 한다. 시작 점이었던 동수가 연락할 사람이 없다. 하나도 연락할 사람이 없을 때 다 연락을 받았구나! 자기 주변에 더 이상 연락할 사람이 없구나 그럼 깊이 우선 탐색이 끝이 났다.

#14-3. 그래프의 탐색3

너비 우선 탐색, BFS(Breadth First Search)

나랑 연결 되어 있는 다른 사람들에게 연락을 취한다. 다 연락을 취한다. 다 연락 취할 기회를 얻는다. 기회를 다 갖는다.

중요한 것은 동시에 연락을 취하진 않는다. 누구한테 먼저?? 상관없다. 그렇게 해서 코드가 크게 바뀌지 않는다. 

동수 그리고 민석에게 연락을 취한다고 가정을 하겠다. 주변에게 막 연락을 취하면 다 연락된 것이 아니냐?? 그림으로는 이해가 되는데 코드로 구현하려면 어렵다!! 처음부터 다 구현하려고 하니 배보다 배꼽이 더 커진다!! 다 연결을 시키는 이유는 집중화된 부분만 한다. 

깊이우선탐색은 스택을 활용!

너비우선탐색은 큐를 활용!

이것을 이해하는 것이 우선이다. 중요하다!!

#14-3. 그래프의 탐색4

코드보다 중요한 이론

깊이 우선 탐색의 구현 모델 : 과정 1~DFS

연락을 이미 취했다. 연락을 올린 상대만 올라간다.

#14-3. 그래프의 탐색5

깊이 우선 탐색의 실제 구현 : 파일의 구성

그림을 이해하는 것이 우선이다.

그림 > code 확인을 해야지 내 것이 된다. 그림으로 이해한 것이 코드로 연결 된 것을 확인하였다. 별로 어렵지 않다. 

#14-3. 그래프의 탐색6

너비 우선 탐색, DFS, Depth First Search

queue를 활용한다.QUEUE를 활용한다. 동수가 OR 민석이 먼저 큐에 들어갈 수 있다. 

코드 레벨에서 동수가 먼저 들어가고 그 다음에 민석이 들어가게 해 놓았다. 

큐가 다 비게 되면 너비 우선 탐색은 끝이난다.

#14-3. 그래프의 탐색7

너비 우선 탐색의 코드 구현. BFS

#14-4. 최소 비용 신장 트리 1

사이클의 이해

정점 B에서 점점 D에 이르는 단순 경로. 한 번 들렸던 정점을 들르지 않고 가는 방법을 찾는 것이다. 최단 경로를 찾는 방법이다.

단순 경로는 최단 경로가 아니라 거치지 않고 갈 수 있는 방법!! 단순 경로의 하나이다. 단순 경로.

시작점과 끝점이 같은 단순 경로를 가리켜 '사이클' 이라 한다. A > B > C 시작점 A 끝점도  A다. 그러면 단순 경로라 한다.

사이클이 형성이 되면 시작점과 끝점이 단순 경로가 만들어 진다. 눈으로 보면 이해가 된다. 

SIMPLE PATH 간선을 중복으로 거치지 않는 경로.

사이클을 형성하지 않는 그래프를 신장 트리 SPANNING TREE라 한다. 트리의 구조를 갖는다. 

사이클을 형성하지 않는 그래프를 신장 트리라고 한다. SPANNING TREE..

최소 비용 신장 트리..

가중치라는 개념이 들어간다. 

AO   BO   CO 

최소의 비용을 들여서 연결되는 점을 그리쟈!! 비용적인 면을 고려해서 신장 트리를 구성하자. 가능하면 비용이 최소가 들어야 한다.

A와 B와 C를 연결 도합 5가 든다. PROGRAM화 해야 한다. 더 싼 트리를 만들 수 있겠는가?? 더 싼 것이 필요하다!! 거리에 어느정도 비례를 하겠다. 신장 트리를 구성하면 이렇게 된다. 

최소비용신장트리를 구하는 알고리즘을 말할 것이다.

#14-4. 최소 비용 신장 트리 2

프림(Prim) 알고리즘 : 하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

크루스칼 알고리즘 1 : 과정 1~

이해하기 쉬운 알고리즘이다. 강의를 들으면 이해하기 쉽다.

최소 비용 신장 트리의 조건인

간선의 수 + 1 = 정점의 수

정점의 수 4개, 간선의 수 3개이다. 

크루스칼 알고리즘 2: 과정 1~

1과 달리 2는 하나식 빼는 과정이다. 

1. 독립된 정점이 생기면 안된다.

2. spanning tree 신장 트리 형성이 되었는지 살펴보면서 실행한다!!

가중치가 높은 것 부터 뺴내간다. 그러면 최소 신장 트리가 된다. 

#14-4. 최소 비용 신장 트리 3

크루스칼 알고리즘의 구현을 위한 계획1

가중치를 기준으로 간선을 내림차순으로 정렬한 다음 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거하는 방식!

그리고 가중치 그래프의 구현을 위해서는 가중치가 포함된 간선을 표현한 구조체가 정의되어야 한다.

크루스칼 알고리즘의 구현을 위한 계획2

이 간선을 삭제한 후에도 이 간선에 의해 연결된 두 정점을 연결하는 경로가 있는가?

탐색, 시작점 끝점 다 방문할 줄 알아!!

V1, V2, V3, V4 어느 순간 V1이 V4니?? 어 맞니?? 돌아댕겼는데두 만날 수 없다?? 

코드 보고 이해하는 습관 좋지 않음.. 코드 구현하는 습관이 중요하다!!

그래프를 구성하는 간선들을 가중치를 기준으로 정렬할 수 있어야 한다.

15 14 13 16 

여러가지 자료구조 가져다가 써서 묶어서 사용한다. 이것이 중요하다!!

#14-4. 최소 비용 신장 트리 4

크루스칼 알고리즘을 구현한 함수 : 수정된 함수들