그래프(Graph)란?
--> 정점과 간선으로 이루어진 자료구조. 트리도 그래프에 속함.
관련 용어
- 정점(vertex) : 그래프 상의 점. node 라고도 함.
- 간선(edge) : 하나의 선. link, branch 라고도 함.
- 차수(degree) : 하나의 정점에 인접한 정점의 수
그래프의 구현 방법
- 인접행렬 방식
--> 그래프의 정점을 2차원 배열로 만든 것 - 인접리스트 방식
--> 그래프의 각 정점에 인접한 정점들을 연결리스트(Linked List)로 표현한 것
인접행렬 방식의 장단점
장점
1) 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있어 두 정점에 대한 연결 정보를 조회할 때 O(1)의 시간복잡도면 가능함.
2) 인접리스트에 비해 구현이 비교적 쉬움.
단점
1) 간선의 수와 관계없이 항상 n^2 크기의 2차원 배열이 필요해 메모리 공간이 낭비.
2) 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n^2)의 시간이 소요.
인접리스트 방식의 장단점
장점
1) 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 비교적 효율적.
2) 정점들의 연결 정보를 탐색할 땐 O(n)의 시간 소요.
단점
1) 구현이 비교적 어려움.
2) 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 차수만큼 시간이 필요.
(O(e) 소요. e는 간선의 개수)
그래프 종류
- 방향 그래프 <-> 무방향 그래프
- 연결 그래프 <-> 비연결 그래프
- 순환 그래프 <-> 비순환 그래프
- 가중치 그래프
- 완전 그래프
- 희소 그래프 <-> 밀집 그래프
그래프 탐색 기법
- DFS(Depth First Search, 깊이 우선 탐색)
- BFS(Breadrh First Search, 너비 우선 탐색)
DFS(Depth First Search, 깊이 우선 탐색)
--> 그래프 상에 존재하는 임의의 한 정점을 기준으로 잡고 다음 정점을 탐색하기 전 해당 정점을 완벽하게 탐색 후 다음정점을 탐색하는 방법. 모든 관계를 다 살펴보아야 할 때 주로 사용됨.
A -> B -> D -> E -> H -> C -> F -> G
BFS(Breadrh First Search, 너비 우선 탐색)
--> 그래프 상에 존재하는 임의의 한 정점을 기준으로 잡고 인접한 정점을 먼저 탐색하는 방법. 넓게 탐색하는 것이 우선. 기준으로 잡은 루트 노드와의 최단 경로를 구할 때 사용됨.
A ->B ->C ->D ->E ->F ->G ->H
참고
https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph
https://suyeon96.tistory.com/32
https://hongcoding.tistory.com/78
