그래프(Graph)

1. 그래프

그래프는 정점과 간선으로 구성되어 있다.

 

 

그래프는 방향성이 없는 '무방향 그래프'와 방향성이 있는 '방향그래프'로 나눠볼 수 있다.

'각각 정점에서 다른 모든 정점을 연결한 그래프'를 '완전 그래프'라고 하며 아래 두 그래프가 이에 해당한다.

 

 

 

2. 그래프 구현방법

1) 인접 행렬(adjacent matrix) 기반 그래프

2차원 배열을 이용한다.

 

 

 

2) 인접 리스트(adjacent list) 기반 그래프

연결 리스트를 활용하여 그래프를 표현한다.

 

 

 

3. 그래프의 탐색

1. 깊이 우선 탐색 (DFS : Depth First Search)

 자신과 연결된 노드들 중 내용이 전달 안 된 하나를 먼저 선택해서 그 사람과 연결된 노드들에게 내용을 다 전달하면, 다음 하나를 또 선택한다. 백트래킹이라고도 하며, 재귀함수의 그래프 버전이라고 볼 수 있다.

연결된 사람 중 누구에게 먼저 알릴지 기준은 알아서 정하면 된다.

 

아래 예시에서는 동수와 연결된 지윤과 지민 중 '지민'을 선택하였다. 똑같이 지민은 '민재'에게 민재는 '지희'에게 지희는 '수정에게 전달했다.

 

 그다음 마지막에 '수정'은 다시 '지희'에게 "나는 이제 더 이상 알려줄 사람이 없어, 너 아직 알려주지 않은 사람 남았으면 걔한테 알려줘!"라고 한다.

 '지희'도 '민재'에게 똑같이 알려주면 '민재'가 '지윤'에게 알려주고 '지윤', '민재', '지민'이 똑같이 "다 알려줬다"라고 각자 알려줬던 사람에게 말해주면 결과적으로 시작점인 '동수'가 다 보낸 걸 확인한다.

 

 

*Start = 동수

- 구현에 사용되는 개념 = Stack

 

 

2. 너비 우선 탐색 (BFS : Breadth First Search)

 자신과 연결된 노드들 중 내용이 전달 안 된 모두에게 알려준다. 가까운 곳을 먼저 다 보고 먼 사람을 보는 방식이다.

 

아래의 예시에서는 '지윤'이 자신과 연결된 '동수'와 '민재'에게 알려준다. 여기서 '동수'와 '민재' 중 누가 먼저 자신과 연결된 사람들에게 알릴지는 알아서 정하면 된다. 지금은 '동수'가 먼저 알렸다고 하겠다.

똑같은 방식으로 모두가 각자와 연결된 사람들 중 내용 전달이 안 된 사람들에게 알려준다.

 

 

*Start = 지윤

- 구현에 사용되는 개념 = Queue

 

 

4. 최소 비용 신장 트리 (minimum cost spanning tree)

1. 용어 정리

1) 단순경로 (simple path) : 동일한 간선을 중복해서 지나지 않는 경로

2) 사이클 : 단순경로이면서 시작과 끝이 같은 경로

3) 신장 트리 (spanning tree) : 사이클을 형성하지 않는 그래프

 

2. 최소 비용 신장 트리

모든 노드가 끊김 없이 이어져 있으며 사이클을 형성하지 않는 그래프 중 cost들의 합이 최소가 되는 spanning tree를 말한다. 관련 알고리즘으로는 Kruskal(크루스칼)알고리즘과 Prim(프림)알고리즘 등이 있다.

 

아래는, Kruskal(크루스칼)알고리즘에 대한 설명이다.

1) cost(weight)들을 오름차순(우선순위)대로 정렬한다.

2) 제일 낮은 수부터 차례대로 선택해나가되 사이클을 형성하지 않도록 한다.

3) (간선의 수) + 1 = (정점의 수) 를 만족할 때까지 선택해나간다.

 

예시를 보면,

 

우선, cost를 오름차순으로 정렬하면 2, 3, 4, 6, 7, 8, 9, 11, 12, 13이다. 2부터 선택한다.

 

 

cost값이 3~6인 간선까지 선택했다. 다음은 cost가 7인 간선을 추가할 차례인데, 이 간선을 추가하면 '사이클'이 생기기 때문에 다음 수로 넘어간다.

 

결과적으로 아래의 최소비용 트리가 완성된다.