그래프란? 🤔
정점과 간선들로 이루어진 집합을 말한다.
구현 과정 📌
💡 기초 용어 정리
정점(Node) : 위치라는 개념
간선(Edge) : 위치 간의 관계, 노드를 연결하는 선
차수(Degree) : 각 정점이 지닌 간선의 수
사이클(Cycle) : 경로의 시작 정점과 종료 정점이 동일한 경우
가중치(Weight) : 간선이 가지는 고유값
💡 그래프 표현 방법
인접 행렬
정점의 개수 N개에 대해 N X N 행렬(배열)을 이용하여 표현한다.
V[i][j] : i번 노드 ~ j번 노드를 잇는 간선의 여부 확인
인접 리스트
가변길이의 벡터를 통해 구현한다.
정점 N개인 그래프의 인접 리스트 초기 선언
v[i] = {i와 연결되어 있는 모든 정점}
공간 복잡도
인접 행렬 : N X N 행렬 사용 → O(N^2)
인접 리스트 : 간선 개수 X 2 만큼의 공간 필요 → O(E)
→ 인접 리스트가 훨씬 효율적이다 !
