그래프

Question 1

그래프

Answer 1

[정의] 정점의 집합을 V, 간선의 집합을 E, 그리고 그래프를 G라고 했을 때, G = (V, E)
[종류]
- 무방향성 그래프 : A ㅡ B, (A, B)
- 방향성 그래프 : A → B, <A, B>
- 가중치 그래프(네트워크) : 간선에 비용이나 가중치 할당

Question 2

그래프 탐색

Answer 2

최소신장트리(MST) : Prim, Kruskal, Solin
최단거리경로 탐색 : 다익스트라, 벨만포드, A*,플로이드와샬, BFS

Question 3

최소신장트리

Answer 3

[정의] 연결 그래프의 연결된 간선 일부를 사용하여 모든 정점을 포함하여 가중치의 합이 최소가 되는 트리
[특징] 모든 정점 포함, 비순환 구성, 최소 비용(edge 가중치 합 최소)
[대표 알고리즘]
- 프림(Prim) , 크루스칼(Kruskal), Solin

Question 4

크루스칼

Answer 4

[정의] 모든 비용을 오름차순으로 나열하여 가장 적은 비용이 드는 간선을 선택하는 알고리즘
* 사전에 가중치 정보를 파악하여 오름차순 정렬하여 트리 구성
[절차]
1. 간선 가중치 오름차순 정렬
2. 최소 가중치 간선 선택 → MST에 추가
3. 다음 가중치 간선 선택 → MST에 추가
4. Cycle 검증 및 제외
* 순환(Cycle)이 발생하는 간선은 제외
[시간복잡도] O(ElogV) - E(간선 개수), V(정점 개수)

Question 5

프림

Answer 5

[정의] 임의의 루트 정점을 선택하고 그것과 연결된 가장 적은 비용 정점 선택 알고리즘
* 시작점에서 단계적으로 노드를 추가하는 방식으로 트리 구성
[절차]
1. 임의의 루트 정점 선택
2. 인접 정점 최소 간선 선택 → MST에 추가 (반복)
3. 간선이 n-1이면 종료
* 순환이 발생하는 간선은 제외
[시간복잡도] O(N^2)

Question 6

솔린

Answer 6

[정의] 단계마다 여러 개의 간선이 선택되는 방법
[절차]
1. 그래프의 모든 정점들이 트리를 형성
2. 각 트리에 대해 최소 비용을 갖는 간선을 선택 연결
3. N-1개의 간선이 될때까지 2반복
* 순환이 발생하는 간선은 제외