그래프란?
정점과 정점들간의 관계가 표현된 자료구조
- 정점Vertex : 대상이나 개체를 나타내는 그래프의 구성요소
- 간선Edge : 두 정점을 연결하는 선
- 무향 그래프 : 간선의 방향이 없는 무방향 그래프 무향 그래프의 최대 간선 수 V * (V - 1) / 2개
- 유향 그래프 : 방향을 가지는 그래프 유향그래프의 각 정점이 가질 수 있는 최대 간선수는 V - 1개
그래프의 표현
인접행렬
V * V크기의 2차원 배열을 이용해서 간선 정보를 저장
행번호와 열번호는 그래프의 정점에 대응
무향 그래프
왼쪽의 무향 그래프를 오른쪽과 같은 인접행렬로 나타낼 수 있다.
i번째 행의 합 = i번째 열의 합 = Vi의 차수
유향 그래프
방향 그래프라면? 행렬은 위와같이 대칭이 아니게 되는 것이다.
행 i의 합 = Vi의 진출 차수
열 i의 합 = Vi의 진입 차수
위의 경우 1행의 합은 4로 1 노드에서 나가고 있는 간선의 수가 총 4개이다.
반면 1열의 합은 2로 1 노드로 들어오고 있는 간선의 수는 2개임을 알 수 있다.
만약 가중치가 있는 그래프라면 1대신에 각 가중치를 값으로 넣어주면 된다.
인접 행렬의 장점
- 이해하기 쉽다
- 간선의 존재 여부를 즉각 확인 가능
인접 행렬의 단점
- n * n행렬이 필요하기 때문에 n^2에 해당하는 공간이 필요
- 행렬의 준비 과정에서 행렬의 모든 원소를 채우는데에 O(N^2)라는 시간이 소요된다.
=> 간선의 밀도가 높은 그래프의 경우에 적합한 표현방법이다.
인접 리스트
두 정점을 연결하는 간선의 정보를 리스트로 저장함
각 정점마다 리스트를 하나씩 만든다. 각 정점에 인접한 정점들을 연결리스트로 단다.
인접 행렬과 달리 존재하지 않는 간선은 저장되지 않는다.
각 노드는 정점의 번호, 다음 정점의 포인터 로 구성된다.
가중치를 가지는 그래프라면 정점의 번호와 함께 가중치를 저장한다.
인접 리스트의 장점
공간의 낭비가 없다. = 간선의 밀도가 낮은 휘귀그래프의 경우 유용한 표현법이다.
인접 리스트의 단점
정점 i와 정점 j간의 간선이 존재할 때 리스트를 차례대로 훑어야 하므로 인접 행렬보다는 탐색 시간이 걸린다.
인접 배열
각 정점에 연결된 정점들을 연결리스트 대신 배열로 저장하여 연결 리스트의 단점을 해결하는 방법이 있다.
1에 {2, 3, 4, 6}과 같은 배열을 연결 해두고 이 배열을 정렬된 형태로 만들면 이진탐색을 사용할 수 있어
임의의 정점에 인접한 정점 수가 k라면 logK+1번 내로 j의 존재를 확인할 수 있다.
인접 배열의 헤더에 인접 정점이 몇개인지 표시해두면 더 쉽게 탐색을 할 수 있다.
간선 리스트
지금까지의 표현법은 정점을 중심으로 한 표현법이라면 간선 리스트는 간선을 중심으로 한 표현법이다.
두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장한 것
시작 정점과 끝나는 정점을 리스트 형식으로 저장한다.
'공부기록 > 자료구조' 카테고리의 다른 글
[자료구조] 큐 Queue [Java] (0) | 2024.04.01 |
---|---|
[C언어/자료구조] 자료구조와 스택(stack) (0) | 2020.09.16 |