그래프
정점(노드)과 간선(엣지)으로 이루어진 자료구조를 의미한다. 간선은 방향을 가질 수 있으며 방향과 순환의 유무에 따라 종류가 나뉘게 된다.
그래프의 표현
출처 : https://howtolivelikehuman.tistory.com/75
인접 행렬 그래프
가중치가 없는 경우
출처 : https://sarah950716.tistory.com/12
가중치가 있는 경우
출처 : https://yoongrammer.tistory.com/84
특징
- 이차원 배열을 주로 사용한다.
- 이동할 수 있으면 1, 없으면 0 으로 표기한다.
- 가중치가 있다면 가중치를 값으로 표기한다.
- 가중치가 0인경우 대비하기 위해 ∞로 표기하기도 한다.
- 무방향 그래프의 경우 대각 성분을 기준으로 대칭성을 가진다.
장점
- 직관적이며 쉽게 구현 가능하다.
- O(1)의 시간복잡도를 가진다
단점
- 불필요한 정보의 저장이 많다.
- 특정 노드와 연결된 노드들이 몇 번 노드인지 확인하기 위해 모든 노드의 연결 관계를 확인해야 한다. 이 경우 시간복잡도가 O(V)가 된다.(V는 노드의 개수)
- 그래프가 커지면 메모리 초과가 발생할 수 있다.
인접 리스트
가중치가 없는 경우
출처 : https://sarah950716.tistory.com/12
가중치가 있는 경우
출처 : https://yoongrammer.tistory.com/84
특징
- 링크드 리스트를 이용해 구현한다.
- 가중치가 있는 경우 추가로 공간을 만들어 저장한다.
장점
- 실제로 연결된 노드들에 대한 정보만 저장한다.
- 간선의 개수에 비례하는 메모리만 차지한다.
- 특정 노드와 연결된 노드들을 확인하기 위해 실제로 연결된 노드들만 탐색 할 수 있다.
- 이 경우 시간복잡도는 O(E)이다. (E는 간선 개수)
단점
- 행렬[i][j] 이렇게 배열처럼 탐색 할 수 없고 리스트를 하나하나 돌면서
노드 i에노드 j가 연결되어 있는지 찾아야 한다. - 이 경우 시간복잡도는 O(V)이다.
