Graph
- 정점(node)의 집합과 간선(edge)의 집합으로 이루어져있다
- 간선의 방향성에 따라 무방향과 방향 그래프로 나뉜다
- 정점을 있는 선이 간선
- 간선들에 값을 줄 수 있다
- 비용이라 칭하며 간선들에 비용이 있는 그래프를 가중그래프(가중치그래프)라 한다
- 서로 다른 개체(혹은 객체)가 연결되어 있다면 높은 확률로 그래프 알고리즘
트리와의 차이점
- 컴퓨터공학 분야에서는 트리를 방향 그래프라 간주
| 그래프 | 트리 |
---|
방향성 | 방향 or 무방향 그래프 | 방향 그래프 |
순환성 | 순환 및 비순환 | 비순환 |
루트 노드 존재 여부 | 루트 노드X | 루트 노드O |
노드간 관계성 | 부모-자식X | 부모-자식O |
모델의 종류 | 네트워크 모델 | 계층 모델 |
구현
인접 행렬(Adjacency Matrix) : 2차원 배열을 이용해 연결 관계 표현
- 간선 정보 저장하는데 O(V2)만큼의 메모리
- V : 노드의 개수
- 노드 수 적은 경우, 점 2개 연결 판단 필요한 경우(일반적인 조회)에 유리
- 특정 노드로부터 이어져있는 간선 찾을 때 O(1)의 시간걸림
- EX) 플로이드 워셜 알고리즘 : 인접 행렬 이용
인접 리스트(Adjacency List) : 리스트를 이용해 연결 관계 표현
- 연결 리스트(튜플 이용해 노드 간선 표현) 자료구조를 이용해 구현
- 특정 점과 연결된 간선 순회 시에 유리
- C++, JAVA의 경우 lib 이용, python의 경우 기본 자료형인 리시트 사용
- 간선 정보 저장하는데 O(E)만큼의 메모리
- 탐색하는데 O(V)만큼 시간 걸림