그래프

그래프

- 원소 간의 관계를 표현 -> 정점, 간선으로 이루어진 자료 구조

- 선형이나 트리로 표현할 수 없는 연결 구조를 표현할 수 있다. -> 비선형 자료 구조

- 그래프는 사이클이 있을 수 있다. / 트리에서는 사이클이 존재하지 않음.

- 차수 : 정점에 연결된 간선의 수

 -> 진출 차수 : 정점에서 나가는 간선의 수

 -> 진입 차수 : 정점으로 들어오는 간선의 수

그래프의 종류

무방향 그래프

- 두 정점을 연결하는 간선의 방향이 없는 그래프

- 정점 A와 정점 B를 연결하는 간선 (A, B) = (B, A)

방향 그래프

- 두 정점을 연결하는 간선의 방향이 있는 그래프

- 정점 A와 정점 B를 연결하는 간선

 A -> B : <A, B> / B -> A : <B, A>

완전 그래프

- 각 정점에서 다른 모든 정점을 연결한 그래프

- 최대 간선 수(정점 n개)

 -> 무방향 : n(n-1)/2

방향 : n(n-1)

부분 그래프

- 원래 그래프에서 일부 정점이나 간선을 제외한 그래프

가중치 그래프

- 정점을 연결하는 간선이 가중치를 가지고 있는 그래프

그래프의 구현

1. 순차 자료 구조

- 2차원 배열의 인접 행렬 = 정방 행렬(n x n)

 -> 두 정점 사이에 연결된 간선의 유무를 저장, 있으면 1, 없으면 0

- 정점이 n개일 때, 간선의 개수에 상관없이 항상 n x n개의 메모리 사용

 -> 간선의 개수가 적을 경우, 메모리 낭비

- 무방향 : 자기 자신을 가리키는 간선이 존재하지 않음 

-> 행렬의 대각선 값은 0, 대각선을 기준으로 행과 열이 대칭 => A행의 합 = A열의 합 = 정점A의 차수 

- 방향 : A행의 합은 정점A의 진출 차수, A열의 합은 정점A의 진입 차수

2. 연결 자료 구조

- 연결 리스트를 이용한 인접 리스트

- 하나의 정점에 인접한 정점의 수만큼, 정점의 헤드가 자식 노드를 가진다.

 -> 노드는 오름차순으로 연결된다.

그래프 순회

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

- 시작 정점에서 한 방향으로 더이상 경로가 없을 때까지 방문

 -> 더이상 방문할 노드가 없다면, 가장 마지막에 방문한 노드의 방문하지 않은 다른 노드로 재탐색

- 후입 선출 구조의 스택을 사용

 -> 인접 노드를 가지고 있는 노드를 스택에 푸쉬해 두고,

인접 노드가 더이상 없을 때, 스택에서 팝한 노드의 인접 노드를 탐색

스택이 공백 스택이 될 때까지 반복

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

- 시작 정점에서 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문

 -> 인접한 노드를 모두 방문 후, 인접 노드의 인접 노드를 방문

- 선입 선출 구조의 큐를 사용

 -> 인접 노드를 가지고 있는 노드를 큐에 인큐,

인접 노드를 모두 방문 후, 큐에서 디큐,

디큐한 노드의 인접 노드 방문, 다시 인접 노드를 가진 노드를 인큐

큐가 공백 큐가 될 때까지 반복

신장 트리

- 사이클이 없는 단순 연결 그래프

- 무방향 그래프에서 정점이 n개일 때, n-1개의 간선을 가진다.

- 탐색 방법에 따라 신장 트리가 정해진다.

 -> 깊이 우선 신장 트리 / 너비 우선 신장 트리

최소 비용 신장 트리

- 가중치 그래프에서 가중치의 합이 최소인 신장 트리

- Kruskal 알고리즘

1. 가중치가 높은 순으로 정렬 후, 가중치가 높은 간선을 제거

2. 가중치가 낮은 순으로 정렬 후, 가중치가 낮은 간선을 삽입

- Prime 알고리즘

 -> 간선을 정렬하지 않고, 시작 정점으로부터 가중치가 작은 간선을 연결

간선이 연결된 정점의 가중치를 모두 확인하여 연결

가중치가 가장 작은 간선을 연결하되, 사이클은 허용되지 않으므로, 다음으로 낮은 가중치를 확인하여 연결.