그래프(Graph)란?
- 자료구조의 종류 중 하나로, 여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 구조이다.
- 그래프 내에서 점(테이터)을
정점(vertex), 선(연결)을 간선(edge) 라고 한다.
정점
- 연결된 데이터를 뜻하며,
노드라고도 불린다.
- 두 정점이 간선으로 직접 연결되어 있는 경우
인접정점이라고 하며, 이를 인접하다 라고 표현한다.
- 만약 한 정점에서 출발하여 다시 출발 정점으로 돌아올 수 있다면 이를
사이클이 존재한다고 한다.
간선
- 정점의 연결 관계를 나타낸다.
- 방향성을 가질 수 있으며, 방향성이 없는 경우
무방향 그래프, 방향성이 있는 경우 단방향 그래프라고 한다.
- 만약 어떤 정점에서 간선이 나와 다시 자기 자신으로 다시 돌아간다면 이를
자기루프라고 한다.
- 한 정점에서 나가는 간선의 수를
진출차수, 들어오는 간선의 수를 진입차수로 표현한다.
가중치
- 각 정점간의 연결의 강도를 나타낸다.
- 예를 들어 지도의 경우 그 길이가 가중치가 될 수 있다.
- 이처럼 데이터가 가중치를 포함한다면
가중치 그래프가 된다.
- 만약 길이가 없이 목적지만 보여준다면 이는
비가중치 그래프가 된다.
그래프의 표현
인접 행렬
- 각 정점이 인접한 경우인지를 표시하는 2차원 배열이다.
→ 행렬 = 표
- 연결되는 경우
1, 아닌 경우 0으로 나타낸다.
- 두 정점이 직접적으로 연결되어 있는지(인접한지) 를 확인하기에 용이하며, 가장 빠른 경로를 찾을 때 사용한다.
- 위같은 경우에는 A와 B 는 인접하고, C는 B에서만 접근 할 수 있다.
A에서 B로 갔다가 다시 A로 올 수 있으므로 사이클이 존재한다.
인접 리스트
- 각 정점이 어떤 정점과 인접하는 지를 리스트로 표현한다.
- 모든 정점이 리스트를 하나씩 가지고 있으며, 인접한 정점에 대한 정보를 담는다.
- 위의 인접행렬은 아래의 리스트로 표현 할 수 있다.
A - B - null
B - A - C - null
C - null
- 리스트의 순서는 크게 중요하지 않으며, 우선 순위를 다루는 경우
queue 혹은 heap등을 사용하는 것이 더 권장된다.
- 만약 리스트의 순서가 중요한 경우에는 구현단계에서 고려하여 정렬 할 수 있다.
- 모든 요소를 순회하는 인접행렬보다, 메모리 효율 측면에서 유리하다.
+
- 서로 아예 연결 될 수 없는 데이터(정점)의 경우, '관계가 없다.'라고 표현한다.
.png)
