그래프의 구조

그래프의 종류

• 무방향 그래프
• 방향 그래프
• 완전 그래프
• 부분 그래프
• 가중 그래프

그래프 관련 용어

• 정점 : 자료
• 간선 : 자료와 자료가 이어진 선

그래프의 구현

1. 인접 행렬을 이용한 구현

2. 인접 리스트를 이용한 구현

그래프 순회

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

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

신장트리

• 최소의 간선을 이용하여 모든 정점을 연결한 그래프

최소비용 신장트리

• 가중치 그래프에서 간선에 주어진 가중치는 비용이나 거리, 시간을 의미하는 값이될 수 있다. 따라서 무방향 가중치 그래프에서 신장트리의 비용은 신장트리를 구성하는 간선들의 가중치의 합이 되는데, 가중치의 합이 최소인 신장트리를 최소비용 신장트리라고 한다.

1. Kruskal 알고리즘1

(1) 그래프의 모든 간선을 가중치에 따라 내림차순으로 정리한다.

(2) 그래프에서 가중치가 가장 높은 간선을 제거한다. 이때 정점을 그래프에서 분리시키는 간선은 제거할 수 없다.

(3) 그래프에 n-1개의 간선만 남을 때까지 (2)를 반복한다.

(4) 그래프에 n-1개의 간선이 남게 되면 최소 비용 신장트리가 완성된다.

2. Kruskal 알고리즘2

(1) 그래프의 모든 간선을 가중치에 따라 오름차순으로 정리한다.

(2) 그래프에서 가중치가 가장 작은 간선을 삽입한다. 이때 사이클을 형성하는 간선은 삽입할 수 없다. 이런 경우에는 그 다음으로 가중치가 작은 간선을 삽입한다.

(3) 그래프에 n-1개의 간선만 남을 때까지 (2)를 반복한다.

(4) 그래프에 n-1개의 간선이 남게 되면 최소 비용 신장트리가 완성된다.

3. Prime 알고리즘

(1) 그래프에서 시작 정점을 선택한다.

(2) 선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선을 연결하여 트리를 확장한다.

(3) 이전에 선택한 정점과 새로 확장한 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선을 삽입한다. 이때 사이클을 형성하는 간선은 삽입할 수 없다. 이런 경우에는 그 다음으로 가중치가 작은 간선을 선택하여 삽입한다.

(4) 그래프에 n-1개의 간선을 삽입할 때까지 (3)을 반복한다.

(5) 그래프의 간선이 n-1개가 되면 최소 비용 신장트리가 완성된다.

참고문헌

[자바로 배우는 쉬운 자료구조], 한빛아카데미