그래프 📈
그래프의 개념
그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조입니다.
- 버스 노선도, 전철 노선도, 인간관계를 나타내는 인맥지도, 분자 구조 등등
주로 선형 자료구조(배열, 연결리스트 등)나 트리 자료구조로 표현할 수 없을 때 그래프를 사용합니다.
그래프는 연결할 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성됩니다. 그래프 G는 G = (V, E)로 정의하며, V는 그래프에 있는 정점의 집합을 뜻하고 E는 정점을 연결하는 간선의 집합을 뜻한다.
그래프의 종류
그래프는 방향성과 연결 정도에 따라 여러 형태로 나눠집니다.
1. 무방향 그래프
무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프입니다.
무방향 그래프에서의 간선은 (Vi, Vj)로 표현하며 간선에 방향이 없기 때문에 (Vi, Vj), (Vj, Vi)는 같습니다.
👉 (Vi, Vj) == (Vj, Vi)
정점 0에서 정점 1로의 간선 : (V0, V1)
정점 0에서 정점 2로의 간선 == 정점 2에서 정점 0로의 간선 : (V0, V2) == (V2, V0)
2. 방향 그래프 (Directed Graph)
방향 그래프는 간선에 방향이 있는 그래프로, 다이그래프라고도 합니다.
방향 그래프에서의 간선은 <Vi, Vj>로 표현하며 간선에 방향이 있기 때문에 무방향 그래프와는 달리 <Vi, Vj>, <Vj, Vi>는 같지 않습니다.
👉 <Vi, Vj> ≠ <Vj, Vi>
정점 0에서 정점 1로의 간선 : <V0, V1>
정점 0에서 정점 2로의 간선 ≠ 정점 2에서 정점 0로의 간선 : <V0, V2> ≠ <V2, V0>
3. 완전 그래프
완전 그래프는 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프입니다. 정점이 n개인 무방향 그래프에서는 최대 간선 수가 n(n-1)/2개고, 방향 그래프에서는 두 정짐에 대해 방향이 다른 간선을 두 개 연결할 수 있으므로 최대 간선 수는 무방향 그래프의 최대 간선 수보다 2배 많은 n(n-1)개가 됩니다.
- 무방향 그래프
- 정점 4개, 간선 6개
- 정점 4개, 간선 6개
- 방향 그래프
- 정점 4개, 간선 12개
- 정점 4개, 간선 12개
4. 부분 그래프
원래 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프를 부분 그래프라 합니다.
5. 가중 그래프
정점을 연결하는 간선에 가중치(Weight)를 할당한 그래프를 가중치 그래프 또는 네트워크라고 합니다.
그래프 관련 용어 📝
- 정점(vertex) : 위치라는 개념(node)
- 간선(edge) : 정점 간의 관계. 노드끼리 연결하는 선(link, branch)
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
- 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 → 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배, 방향 그래프에서 정점의 차수 = 진입 차수와 진출 차수의 합
- 진입 차수(in-degree) : 정점을 머리로 하는 간선 수, 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수(out-degree) : 정점을 꼬리로 하는 간선 수, 방향 그래프에서 외부로 향하는 간선의 수
- 경로(path) : 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트 = 정점 Vi에서 Vj까지의 경로
- 경로 길이(path length) : 경로를 구성하는 데 사용된 간선의 수
- 단순 경로(simple path) : 모두 다른 정점으로 구성된 경로, 경로 중에서 반복되는 정점이 없는 경우
- 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
- DAG(Directed Acyclic Graph) : 방향 그래프이면서 사이클이 없는 그래프
그래프의 추상 자료형 ( ADT )
- createGraph() : 공백 그래프를 생성하는 연산
- isEmpty(g) : 그래프 g가 정점이 없는 공백 그래프인지 검사하는 연산
- insertVertex(g, v) : 그래프 g에 정점 v를 삽입하는 연산
- insertEdge(g, u, v) : 그래프 g에 간선 (u, v)를 삽입하는 연산
- deleteVertex(g, v) : 그래프 g에서 정점 v를 삭제하고 v에 부속된 모든 간선을 삭제하는 연산
- deleteEdge(g, u, v) : 그래프 g에서 간선 (u, v)를 삭제하는 연산
- adjacent(g, v) : 정점 v에 인접한 모든 정점을 반환하는 연산
그래프와 트리의 차이 📈 vs 🌳
| 그래프 | 트리 | |
|---|---|---|
| 정의 | 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조 | 그래프의 한 종류 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 |
| 방향성 | 방향 그래프, 무방향 그래프 | 방향 그래프 |
| 사이클 | 사이클 가능하며 자체 간선(self-loop)도 가능, 순환그래프와 비순환 그래프 모두 존재 | 사이클이 불가능하며 자체 간선도 불가능, 비순환 그래프 |
| 루트노드 | 루트 노드의 개념이 없음 | 한 개의 루트 노드만이 존재, 모든 자식 노드는 한 개의 부모 노드만을 가짐 |
| 부모-자식 | 부모-자식 개념이 없음 | 부모-자식 관계, top-bottom 또는 bottom-top으로 이루어짐 |
| 모델 | 네트워크 모델 | 계층 모델 |
| 순회 | DFS,BFS | DFS,BFS안의 Pre-,In-,Post-order |
| 간선의수 | 그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음 | 노드가 N인 트리는 항상 N-1의 간선을 가짐 |
| 경로 | - | 임의의 두 노드 간의 경로는 유일 |
| 예시 및 종류 | 지도, 지하철 노선도 | 이진트리, 이진탐색 트리, 이진 힙 |
그래프의 순회 🚪
한 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하는 것을 그래프 순회 또는 그래프 탐색이라고 합니다. 그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
이미지 출처
1. 깊이 우선 탐색
DFS(Depth First Search) : 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 산언이 있는 정점으로 되돌아와 다른 방향의 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속하여 결국 모든 정점을 방문하는 순회 방법입니다. 탐색 과정에서 정점 순서를 관리하기 위해 후입선출 구조의 스택을 사용합니다.
2. 너비 우선 탐색
BFS(Breadth First Search) : 시작 정점에 인접한 정점을 모두 차례로 방문하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식입니다. 가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 순회 방법입니다. 인접한 정점에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 탐색 과정에서 정점 순서를 관리하기 위해 선입선출의 구조를 갖는 큐를 사용합니다.
잘못된 내용이나 오타가 있다면 댓글로 알려주시면 감사하겠습니다!!
