1. 너비우선탐색(BFS)
2. 깊이우선탐색(DFS)
3. 최소신장트리
① 프림 알고리즘
| 그림 | 설명 | 안 보임 | 경계 | 결과 집합 |
|---|---|---|---|---|
| 왼쪽에 있는 것이 우리가 문제를 풀어야 할 그래프이다. 왼쪽에 있는 그림은 트리가 아니다. 트리의 정의 상 트리에는 순환 고리가 없어야 하는데 왼쪽에 있는 그림에는 순환 고리가 있기 때문이다. 왼쪽 도표의 정확한 이름은 그래프 혹은 네트웍이 되겠다. 변(arc) 옆에 있는 숫자는 무게(weight), 다른 말로 비용(cost)을 나타낸다. 아직 아무 변도 색이 바뀌지 않았다. 임의의 점을 출발점으로 정할 수 있다. 정점 D를 출발점으로 정하겠다. | C, G | A, B, E, F | D | |
| 다음으로는 D와 붙어 있는 정점을 선택해야 한다: A는 5만큼 떨어져있고(비용이 5라는 뜻), B는 9 떨어져있고, E는 15 떨어져 있고, F는 6 떨어져 있다. 이 중 5가 가장 작으므로 정점 A 및 변 DA의 색을 바꾸겠다. | C, G | B, E, F | A, D | |
| 다음 정점은 D 혹은 A와 붙어 있는 정점을 선택하면 된다. B는 D에서 9떨어져 있고, A에서 7 떨어져 있다. E는 D에서 15만큼 떨어져 있고, F는 6만큼 떨어져 있다. 6이 가장 작은 수이므로, F 및 DF의 색을 바꾸겠다. | C | B, E, G | A, D, F | |
| 위와 같은 방법으로하면 A에서 7 떨어진 B가 선택된다. DB의 색을 빨강으로 바꾸겠다. B와 D가 이미 색이 바뀌어 있기 때문이다. 따라서 DB는 이용될 수 없다. | 널 | C, E, G | A, D, F, B | |
| 이 경우 우리는 C', E, 및 G 중 하나를 선택할 수 있다. C는 B에서 8 떨어져 있고, E는 B에서 7 떨어져 있다. G는 F에서 11 떨어져 있다. E가 가장 가까우므로 E와 EB의 색을 바꾸겠다. 다른 두 개는 빨강으로 칠하겠는데, 이는 두 정점이 이미 사용되었기 때문이다. | 널 | C, G | A, D, F, B, E | |
| C와 G가 남아있다. C는 E에서 5떨어져 있고, G는 E에서 9 떨어져 있다. C를 선택하겠다. C와 EC의 색을 바꾸겠다. BC는 빨강으로 칠하겠다. | 널 | G | A, D, F, B, E, C | |
| G만 남아 있다. F에서 11 떨어져 있고, E에서 9 떨어져 있다. E가 가까우므로 EG의 색을 바꾸겠다. 이제 모든 정점의 색을 바꿨고, 최소 비용 걸침 나무가 녹색으로 표시되었다. 총 비용(cost or weight) 합은 39이다. | 널 | 널 | A, D, F, B, E, C, G |
② 크루스칼 알고리즘
| 우리가 풀어야 할 그래프이다. 간선(arc) 옆에 있는 숫자는 간선의 무게(weight)를 가리킨다. 지금은 모든 간선(arc)들이 색이 동일하다. | |
| AD 와 CE 가 가장 짧은(weight가 가장 작은) 간선이다. 아무거나 골라서 AD를 선택한다. AD의 색을 변경하였다. | |
| 이제, CE가, 무게(weight)가 5로서, 루프(loop)를 생성하지 않는 가장 짧은 간선이다. CE의 색을 변경하였다. | |
| 같은 방식으로 고르면 다음 간선은 DF이다. 무게(weight)는 6이다. | |
| 다음으로 가장 짧은 간선은 AB와 BE인데, 둘 다 길이 (= 무게(weight))가 7이다. 임의로AB를 골랐다. BD는 빨강색으로 변경하였는데, ABD를 연결시키면 루프를 이루기 때문이다. | |
| 다음으로 가장 짧은 간선은 BE로서 길이 7이다. 더 많은 간선들이 빨강으로 변했다. BCE 루프를 생성하기 때문에 BC가 빨강색으로 변했으며, DEBA 루프를 생성하기 때문에 DE가 빨강색으로 변했고, FEBAD 루프를 생성하기 때문에 FE가 빨강색으로 변했다. | |
| 끝내, EG가 연결되면서 알고리즘이 종료된다. 미니멈 스패닝 트리가 완성되었다. |