그래프 기초

현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현 정점 : 데이터를 표현(사물, 개념 등)

간선 : 정점들을 연결하는데 사용

순환, 비순환 구조를 이룸. 방향이 있는, 없는 그래프가 각각있음. 루트 노드 개념이 없음. 2개 이사의 경로가 가능. 네트워크 모델

 

가중치 그래프

지하철 역 간의 거리를 가중치로 표현 예

 

방향 그래프

 

구현 시 인접 리스트, 인접 행렬로 구현 가능

 

인접 행렬일 경우, 두 정점을 연결하는 간선을 조회할 때 O(1) 시간 복잡도

정점(i) 의 차수를 구할 때는 인접행렬의 i 번째 해의 값을 모두 더하므로 O(n) 의 시간복잡도

인접 행렬 일 경우, 메모리 공간이 더 사용되는 단점

그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 순회해야해서 O(n2) 의 시간복잡도 단점

 

인접 리스트 일 경우

존재하는 간선만 관리하면 되서 메모리 사용 측면에서 효율적

그래프의 모든 간선 수를 알아낼때 시작 노드부터 모든 간선을 탐색하므로 O(n + 간선수) 의 시간이 소요

단점

두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 해서 정점의 차수만큼의 시간이 필요.