[Data Structure & Alogrithm] Graph
📝 Graph
📌 핵심 요약
"그래프(Graph)는 정점(Vertex)과 정점을 연결하는 간선(Edge)로 구성되는 자료구조이다."
📌 설명
- 그래프(Graph)는 정점(Vertex)과 정점을 연결하는 간선(Edge)로 구성되는 자료구조이다.
- 무방향 그래프 : 연결 관계에 있어서 방향성이 없는 그래프
- 방향 그래프 : 간선에 방향정보가 포함된 그래프
- 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프
- 가중치 그래프 : 간선에 가중치 정보가 있는 그래프
- 인접 행렬(adjacent matrix) 기반 그래프 : 정방 행렬을 활용
- 인접 리스트(adjacent list) 기반 그래프 : 연결 리스트를 활용
📌 Graph 의 탐색
- 깊이 우선 탐색(DFS)
- 탐색의 각 과정에서 가능한 한 그래프 안으로 ‘깊이’ 들어가려고 시도한다, 막힌 정점을 만난다면 이전 정점으로 돌아간다.
- 너비 우선 탐색(BFS)
- 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다.
- DFS/BFS 탐색 시간 복잡도
- 인접 리스트 O(V+E), 인접 행렬 O(V^2)