Chap 11. 그래프

정점 : 연결의 대상이 되는 개체 또는 위치
간선 : 정점 사이의 연결

---

 

- 무방향 그래프
연결 관계에 있어서 방향성이 없는 그래프

 

 

- 방향 그래프
간선에 방향정보가 포함된 그래프

 

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

- 가중치 그래프
간선에 가중치 정보를 두어서 그래프를 구성
ex) 두 정점 사이의 거리

- 부분 그래프
그래프의 일부 정점 및 일부 간선으로 이루어진 그래프

---

<그래프 구현>
- 무 방향 그래프 정방 행렬

- 방향 그래프 정방 행렬

- 무방향 그래프 연결리스트

- 방향 그래프 연결리스트

---

 

 

<깊이 우선 탐색 DFS>

ex) 비상 연락망
- 한 사람에게만 연락한다.
- 연락할 사람이 없으면, 자신에게 연락한 사람에게 알린다.
- 처음 연락을 시작한 사람의 위치에서 연락은 끝이 난다.

 

 

 

---

 

 

 

<너비 우선 탐색 BFS>
- 보낼 수 있는 사람 모두에게 보낸다.
- 순서대로 보낼 수 있는 사람 모두에게 보낸다.

 

---

<최소 비용 신장 트리>

- 경로 
정점을 잇는 간선을 순서대로 나열한 것

- 단순 경로
동일한 간선을 중복하여 포함하지 않는 경로

- 싸이클 
단순 경로이면서 시작과 끝이 같은 경로

- 신장 트리 
사이클을 형성하지 않는 그래프

*그래프의 모든 정점이 간선에 의해서 하나로 연결되어있다.
*그래프 내에서 사이클을 형성하지 않는다.

- 최소 비용 신장 트리
신장 트리의 모든 간선의 가중치 합이 최소인 그래프

최소 비용 신장 트리 예시

---

 

● 크루스칼 알고리즘

- 간선이 없는 노드들과 가중치를 오름차순으로 정렬
- 가중치가 낮은 간선들부터 노드에 하나씩 추가한다.
- 그래프 내에 싸이클이 생성되면 안된다.
- 간선의 수 + 1 = 정점의 수 가 될때까지 진행한다.

---