그래프
그래프란?
- 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조
- 정점(vertex)와 간선(edge)들의 집합으로 구성
( 정점은 node라고 불리기도 함)
그래프 용어
- 정점 : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소
- 간선 : 링크라고도 하며 정점 간의 관계를 나타냄
- 인접 정점 : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
정점 C의 인접 정점은 A, D
- 차수 : 정점에 연결된 간선의 수
정점 A의 차수는 3, 모든 정점의 차수의 합은 8
무방향 그래프 : 간선 수 x 2
양방향 그래프 : 외부에서 오는 간선의 수를 진입 차수, 외부로 향하는 간선의 수를 진출 차수
- 경로 : 간선을 따라갈 수 있는 길, 정점을 나열하여 표시
- 경로의 길이 : 경로를 구성하는데 사용된 간선의 수
- 단순 경로 : 경로 중에서 반복되는 간선이 없는 경로
- 사이클 : 시작 정점과 종료 정점이 같은 단순 경로 ( A, C, D, A의 경로)
그래프의 종류
그래프의 구현
- 인접행렬 (Adjacency Matrix)
- 인접리스트 (Adjacency List)
인접행렬
- 2차원 배열의 형식 -> arr[][]의 형식
- 노드의 개수가 n이라면 n*n 형태의 2차원 배열로 그래프의 연결 관계를 표현
- 행과 열은 정점을 의미하고, 각각의 원소들은 정점 간의 간선을 나타냄
가중치가 없는 무방향 그래프
- 연결되어 있는 경우 행렬에서 1의 값을 가지고, 연결되지 않은 경우 0의 값을 가짐
- 두 개의 노드에서 간선이 동시에 연결되어 있기 때문에 대칭적 구조를 가짐
가중치가 있는 유방향 그래프
- 행렬에서 각 간선의 가중치 값이 저장됨
- 이 경우 가중치가 0인 것과 간선이 없는 것이 구별되어야 함
장점
- 2차원 배열에 모든 노드들의 간선 정보가 있기 때문에,
두 노드를 연결하는 간선을 조회할 때 O(1) 시간복잡도를 가짐
단점
- 간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비됨
- 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요
인접리스트
- 그래프의 각 노드에 인접한 노드들을 연결리스트(Linked List)로 표현하는 방법
- 노드의 개수만큼 인접리스트가 존재
- 각각의 인접리스트에는 인접한 노드 정보가 저장됨
- 그래프는 각 인접리스트에 대한 헤드포인터를 배열로 가짐
가중치가 없는 무방향 그래프
- 가중치 표현 없이 인접한 노드 정보가 저장
가중치가 있는 유방향 그래프
- 종점 [ 노드 번호 | 간선의 가중치 ] 정보가 저장
장점
- 존재하는 간선만 관리하므로 메모리 사용이 효율적임
단점
- 두 노드를 연결하는 간선을 조회하거나 노드의 차수를 알기 위해서는
노드의 인접리스트를 탐색해야 하므로 노드의 차수만큼의 시간이 필요
