그래프
- 연결 데이터를 저장 할 수 있는 자료구조
- 세상에는 다양한 연결 관계가 존재하기 때문에 그래프 자료구조는 이를 저장하기 유용하다.
그래프 용어 정리
노드 : 그래프에서 하나의 데이터 단위를 나타내는 객체
엣지: 그래프에서 두노드의 직접적인 연결 관계 데이터
엣지가 방향을 가지면 → 방향그래프
엣지가 어떤 정보를 나타내는 수치를 가지면 → 가중치그래프
차수 : 하나의 노드에 연결된 엣지들의 수
무방향 그래프 → 하나의 노드에 연결된 엣지들의 수를 나타낸다.
방향 그래프 → 노드를 떠나는 엣지의 수를 출력 차수 노드에 들어오는 엣지의수를 입력 차수로 부른다.
경로 : 한 노드에서 다른 노드까지 가는길
경로의 거리
비가중치 그래프 → 엣지의 수
가중치 그래프 → 엣지의 가중치 합
최단 경로 : 두노드 사이의 경로 중 거리가 가장 짧은 경로
사이클 : 한 노드에서 시작해서 같은 노드로 돌아오는 경로
모든 노드가 연결 될 필요는 없다. 극단적으로 엣지가 없고 노드만 존재 할 수 도있다.
인접행렬
노드들의 연결관계를 나타내는 2차원 리스트
- 각 노드를 리스트에 저장해 고유 정수 인덱스를 준다
- 노드수 X 노드수 크기의 행렬을 만든다
- 노드들의 엣지 유무 및 가중치에 따라 행렬의 요소를 채운다.
인접 리스트
- 각 노드의 엣지를 리스트에 저장하는 방법
복잡도 표현 기호
V(vertex): 그래프 안에 있는 모든 노드들의 집합
E(edge): 그래프 안의 모든 엣지들의 집합
무방향 그래프의 최대 엣지 수:$V^2/2$
방향 그래프의 최대 엣지수: $V^2$
⇒ E는 최악의 경우 $V^2$에 비례
그래프는 노드를 저장하는데 O(V)의 공간을 사용
인접행렬이 차지하는 공간 : O(V^2)
인접리스트가 차지하는 공간 : O(V+E) = O(V^2)
두노드가 연결 됐는지 확인하는데 걸리는 시간
인접행렬을 사용하면 : O(1)
인접 리스트를 사용하면 : O(V)
한 노드에 연결된 모든 노드들을 알아내는데 걸리는 시간
인접행렬은 무조건 V번 을 돌아야한다. 0인지 1인지 확인해야하기 때문
반면 인접 리스트는 최악의 경우 즉, 모든 노드에 연결되어있는 경우만 즉, 최악의 경우만 V이기 때문에 인접리스트가 더효율적이다.