[자료구조] 그래프

(2021.07.19)

 

자구 재수강하면서 정리했던 것들

DFS, BFS, 최소비용 신장트리, 최단경로 알고리즘은 하나씩 자세하게 정리해서 따로 올릴 계획이다.

---

 

 

 

 

 

V(vertex) : 정점
E(Edge) : 간선
차수(degree) : 정점에 부속되어있는 간선의 수
경로(path) : 정점 Vi ~ 정점 Vj 까지 간선으로 연결된 정점을 순서대로 나열한 리스트
   - 단순경로 : 모두 다른 정점으로 구성
   - cycle : 시작정점과 마지막정점이 같음 

 

순차 자료구조를 이용한 그래프의 구현: 인접행렬

연결 자료구조를 이용한 그래프의 구현: 인접리스트

 

그래프의 순회

- DFS: 깊이 우선 탐색 (후입 선출 구조의 스택)

- BFS: 넓이 우선 탐색 (선입 선출 구조의 큐)

 

 

신장트리(Spanning Tree)

: 모든 정점이 n개인 무방향 그래프 G에서 정점이 n개고, 간선이 n-1개인 트리 형태의 부분그래프

--> 간선을 최소로 이용하여 모든 정점을 연결한 그래프

 

신장트리에도 깊이 우선 신장트리와 너비 우선 신장트리가 있음

 

 

최소 비용 신장트리

- 크루스칼 알고리즘(Kruskal Algorithm) 1 : 가중치가 높은 간선을 제거 

- 크루스칼 알고리즘(Kruskal Algorithm) 2 : 가중치가 낮은 간선부터 삽입

   +) 크루스칼 알고리즘은 edge 수가 적은 경우에 적합함.

   +) 희소행렬에 적합함.

   +) 가중치에 따라 간선을 미리 정렬해둠.

- 프림 알고리즘(Prim Algorithm) : 하나의 정점에서 시작하여 트리를 확장해나감 

   +) edge 수가 많은 경우에 적합함.

   +) 가중치가 낮은 간선을 찾을 때, 지나간 정점에 부속된 간선 중에서 찾는 것임

- 솔린 알고리즘(Sollin Algorithm) : 각 정점에 대해, 정점에 연결된 가장 가중치가 낮은 간선을 선택하여 단계별 진행

 

 

최단 경로 알고리즘

- 다익스트라(Dijkstra) : 정점 하나를 출발점으로 두고, 다른 모든 도착점으로 하는 단일점에서의 최단 경로

- 벨만 포드(Bellman-Ford) : 가중치가 음수일 때, 사용가능

- 플로이드 (Floyd) : 모든 정점 사이의 최단 경로를 구하고, 그것을 이용하여 만드는 최단경로 알고리즘