그래프
- 객체 사이이 연결 관계를 표현할 수 있는 자료 구조
- 정점(vertex)와 간선(edge)들의 유한 집합
- G = {V, E}
그래프의 종류
-
무방향 그래프 (undirected graph)
-
방향 그래프 (directed graph)
-
가중치 그래프(weighted graph)
-
부분 그래프(subgraph): 어떤 그래프의 정점과 간선의 일부로 이루어진 그래프
-
차수(degree): 그 정점에 인접한 정점의 수
-
연결 그래프(connected graph): 무방향 그래프에 있는 모든 정점 쌍에 대하여 항상 경로가 존재하는것.
-
완전 그래프(complete graph): 모든 정점들이 서로 연결되어 있는 그래프
그래프의 표현 방법
- 인접 행렬(adjacency matrix): 2차원 배열을 사용
- 인접 리스트(adjacency list): 연결 리스트를 사용
그래프의 탐색
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
탐색의 방법
- DFS(depth first search): 깊이 우선 탐색
- BFS(breath first search): 너비 우선 탐색
최소 비용 신장 트리
신장 트리(spanning tree)
- 그래프 내의 모든 정점을 포함하는 트리
- 모든 정점이 연결 되어 있어야 하고 사이클을 포함하면 안 됨
- 따라서 n개의 정점을 정확히 n-1개의 간선으로 연결
- 하나의 그래프에는 많은 신장 트리가 존재 가능
- DFS, BFS 도중 사용된 간선만 모으면 만들 수 있음
최소 비용 신장 트리(MST)
- 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결
MST 알고리즘
Kruskal의 MST 알고리즘
- 탐욕적인 방법(greedy method)
- 매 순간 가장 좋다고 생각되는 것을 선택
- kruskal의 알고리즘은 지역적인 해답 뿐만 아니라 전역적인 해답도 최적의 해
- 간선들을 가중치의 오름차순으로 정렬
- 사이클 형성 검사 - union-find연산
- 간선의 개수가 정점의 개수 -1개이면 종료
시간 복잡도 분석
union-find 알고리즘을 이용하면 간선들을 정렬하는 시간에 좌우된다.
Prim의 MST 알고리즘
- 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장
- 포함된 신장 트리 집합에 인접한 정점들 중에서 최소비용으로 연결된 정점을 선택
- 마찬가지로 간선의 개수가 정점의 개수 - 1개이면 종료
시간 복잡도 분석
- 주 반복문이 정점의 수 n만큼 반복, 내부 반복문이 n번 반복
- 따라서 O(n^2)
Kruskal vs Prim
희소 그래프의 경우에는 Kruskal
밀집 그래프의 경우에는 Prim
최단 경로
최단 경로(shortest path): 네트워크에서 정점 i와 정점 j를 연결하는 경로 중 가중치 합이 최소가 되는 경로
- 가중치 인접 행렬 사용
Dijkstra의 최단 경로 알고리즘
하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
Floyd의 최단 경로 알고리즘
그래프에 존재하는 모든 정점 사이의 최단 경로
복잡도 분석
- Dijkstra: O(n^2)
- Floyd: O(n^3)
하지만 모든 정점 쌍의 최단 경로 구할 때 Dijkstra도 O(n^3)이 된다.
Floyd의 알고리즘은 매우 간결한 반복 구문을 사용하므로 Dijkstra의 알고리즘에 비해 상당히 빨리 모든 정점 간의 최단 경로를 찾을 수 있다.
위상 정렬
- 방향 그래프를 정렬
