그래프(Graph) 자료구조
그래프(Graph) 자료구조
노드와 노드 사이에 연결된 에지의 정보를 가지고 있는 자료구조
- 노드(Node) : 데이터를 표현하는 단위
- 에지(Edge) : 노드를 연결
에지 리스트(Edge List)
- 노드를 배열에 저장하여 에지 표현
- 에지를 중심으로 그래프 표현
- 특징
+ 구현하기 쉽다.
- 특정 노드와 관련된 에지를 탐색하기는 쉽지 않다.
⇒ 노드 중심 알고리즘에는 잘 사용하지 않는다.
- 응용 문제
- 벨만-포드(노드 사이의 최단 거리를 구하는 알고리즘) 알고리즘, 크루스칼(최소 신장 트리를 찾는 알고리즘) 알고리즘
- 에지 리스트로 가중치 없는 그래프 표현하기
- 배열에 출발 노드, 도착 노드 저장
[ 예시 ]
1에서 2로 뻗어나가는 에지 : [1, 2]
4에서 5로 뻗어나가는 에지 : [4, 5]
* 방향이 없는 그래프인 경우 : [1, 2] == [2, 1]
- 에지 리스트로 가중치 있는 그래프 표현하기
- 배열에 출발 노드, 도착 노드, 가중치 저장
[ 예시 ]
1에서 2로 향하는 가중치가 8인 에지 : [1, 2, 8]
인접 행렬(Adjacency Matrix)
- 2차원 배열을 자료구조로 이용하여 그래프 표현
- 노드를 중심으로 그래프 표현
- 특징
+ 구현하기 쉽다.
+ 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있다.
- 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 한다.
⇒ 시간복잡도가 인접 리스트에 비해 느리다.
⇒ 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
- 인접 행렬로 가중치 없는 그래프 표현하기
[ 예시 ]
1에서 2를 향하는 에지 : 1행 2열에 1을 저장
* 1을 저장하는 이유 : 가중치가 없기 때문
- 인접 행렬로 가중치 있는 그래프 표현하기
[ 예시 ]
2에서 5를 향하는 에지 : 2행 5열에 15를 저장
인접 리스트(Adjacency List)
- 2차원 벡터로 그래프 표현
- 특징
+ 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어나다.
+ 노드 개수가 커도 공간 효율이 좋다.
⇒ 메모리 초과 에러가 발생하지 않는다.
- 구현하기 복잡한 편이다.
- 인접 리스트로 가중치 없는 그래프 표현하기
[ 예시 ]
노드 1과 연결된 2, 3 노드 : A[1]에 [2, 3]을 push_back()으로 연결
* int 데이터 하나로 그래프를 표현하기에 충분하므로 vector<vector<int>> A로 선언
- 인접 리스트로 가중치 있는 그래프 표현하기
[ 예시 ]
노드 1과 2가 가중치 8 에지로 연결, 노드 1과 3이 가중치 3 에지로 연결 : A[1]에 [(2, 8), (3, 3)]을 push_back()으로 연결
* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.