Graph
- 정점과 간선의 집합이다.(트리는 싸이클이 없는 그래프)
- 연결되어 있는 객체간의 관계를 표현할 수 있음
종류
무방향 그래프(Undirected Graph)
- 말 그대로 정점과 간선의 연결관계에서 방향성이 없는 그래프
- Degree : 각 정점에 연결된 Edge의 개수
방향 그래프(Directed Graph)
- 정점과 간선의 연결관계에서 방향성이 있는 그래프
- Degree
- 각 정점에서 나가는 간선의 개수 OutDegree
- 각 정점으로 들어오는 간선의 개수 InDegree
가중치 그래프(Weighted Graph)
구현 방법
인접 행렬(Adjacent matrix)
- 정방 행렬을 사용하는 방법
- NxN Boolean 행렬
matirx[i][j] == 1
이면 i -> j 간선이 존재한다는 뜻
- 해당하는 위치의 value 값을 통해 정점간 연결 관계를 O(1)로 파악 가능
- 간선의 개수와 상관없이 V^2의 공간 복잡도를 가짐
- Dense Graph(간선이 정점보다 많음) 표현에 적당
인접 리스트(Adjacent List)
- 연결 리스트를 사용하는 방법
- 정점의 인접 리스트를 확인해야해 정점이 연결되었는지 확인하는 데 오래 걸림
- 공간 복잡도는 O(E + V)
- Sparse Graph(정점이 간선보다 많음) 표현에 적당
- 무방향 그래프에서 간선은 2번 저장됨
Graph 탐색
깊이 우선 탐색(DFS)
- 임의의 정점에서 연결되어 있는 한 정점으로만 나아가는 방법으로 탐색
- 자료구조로 Stack 을 사용해 탐색할 정점의 순서 기록
- 연결된 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전단계의 정점에서 연결할 수 있는 정점이 있는지 살펴봄
- 시간 복잡도 : O(V+E)
너비 우선 탐색(BFS)
- 임의의 정점에서 연결되어 있는 모든 정점으로 나아가는 방법으로 탐색
- 자료구조로 Queue 를 사용해 탐색할 정점의 순서를 기록
- Queue를 dequeue 해 해당 정점과 연결된 정점들을 enqueue
- 시간 복잡도 : O(V + E)
- BFS로 구한 경로는 최단 경로
신장 트리(Spanning Tree)
- 그래프 내 모든 정점이 연결되어 있으면서 사이클이 없는 트리
- 하나의 연결 그래프가 있으면 신장트리는 여러개가 존재할 수 있음
최소 신장 트리(MST)
- 그래프의 신장트리 중 간선 비용의 합이 최소인 신장트리
- MST를 찾는 대표적인 알고리즘
크루스칼
, 프림
크루스칼 알고리즘(Kruskal Algorithm)
- 그리디 알고리즘
- 그래프의 간선들을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선 선택
- 사이클의 형성 유무는 Union&Find 자료구조 사용
- 시간 복잡도 : O(E log E)
프림 알고리즘(Prim Algorithm)
- 그리디 알고리즘
- 임의의 정점에서 시작
- 정점에서 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택, 반복
- 시간 복잡도 : O(E log V)
참고자료
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
https://chanhuiseok.github.io/posts/algo-33/
https://goodgid.github.io/Prim-Algorithm/