구조
-
여러 점들이 복잡하게 연결되어 있는 형태
ex) 복잡한 네트워크망 -
정점(vertex) 또는 노드(Node): 데이터가 저장되는 요소
-
간선(edge): 정점들을 이어주는 선, 정점들의 관계를 나타냄
Graph의 종류
-
무방향 그래프: 간선에 방향이 없는 그래프(양방향)
-
방향 그래프: 간선에 방향이 존재하는 그래프
-
가중치 그래프: 두 정점 사이의 간선에 가중치가 할당된 그래프
- 가중치에는 거리, 비용 등 추가적인 정보가 저장된다.
-
비가중치 그래프
용어
- 진입 차수: 한 정점에 들어오는 간선이 몇 개인지
- 진출 차수: 한 정점에서 나가는 간선이 몇 개인지
- 자기 루프: 정점에서 진출하는 간선이 다시 본인에게 진입하는 경우
- 사이클: 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.
Graph 표현 방식
인접하다 = 두 정점 사이에 간선이 있다.
인접 행렬
- 2차원 배열의 형태로 표현
- 두 정점이 인접하다면, 1(또는 가중치)를 저장
- 인접하지 않다면, 0을 저장
✅ 인접 행렬[시작 정점][도착 정점] = 1
- 두 정점이 인접하는지 바로 index로 접근해서 확인할 수 있다.
- 가장 빠른 경로를 찾을 때 사용한다.
인접 리스트
- List를 사용
- 각 정점마다 리스트를 가지고 있으며, 리스트에는 자신과 인접한 정점이 담겨 있다.
- 인접 리스트는 인접 행렬에 비해 메모리를 효율적으로 사용할 수 있다.
- 인접 형렬은 연결 가능한 모든 경우의 수를 저장하는데 비해, 인접 리스트는 연결된 것들만 저장하기 때문에
- 인접 리스트는 인접 행렬에 비해, 인접하는 정점을 찾는데 시간이 더 소요된다.(리스트를 직접 순회해야 하므로)
활용
- 포털 사이트의 검색 엔진
- SNS에서의 사람들과의 관계(친구, 팔로우)
- 내비게이션 길 찾기
알고리즘 문제
- 최단 경로 문제 - 가중치 그래프의 합이 최소가 되는 경로를 구하기
