개요
- 정점과 간선들의 유한 집합
- G = (V, E)
- 정점(Vertex)
- 여러 특성을 가지는 객체
- 노드(node)와 같은 의미
- 간선(edge)
- 정점을 잇는 선
- 객체들의 연결관계를 나타냄
- 링크(link)라고도 함
- 인접 정점
- 간선은 방향성이 있는 경우와 없는 경우 존재
그래프의 종류
무방향 그래프 (Undirected Graph)
- 방향이 없는 그래프
- 노드는 간선을 통해 양방향으로 통행 가능
- 노드 A와 B가 연결된 경우 (A, B) 또는 (B,A)로 표현
- 정점의 차수
방향 그래프(Directed Graph)
- 간선에 방향이 있는 그래프
- 노드 A에서 노드B로 가는 간선이 있을 때 <A,B>라고 표현
- 진입 차수
- 방향 그래프에서 외부에서 정점으로 들어오는 간선의 수
- 진출 차수
- 방향 그래프에서 정점에서 외부로 나가는 간선의 수
가중치 그래프(Weighted Graph), 네트워크(Network)
연결 그래프, 비연결 그래프
연결 그래프
- 무방향 그래프의 모든 노드에 대해 항상 경로가 존재하는 그래프
비연결 그래프
- 무방향 그래프에서 특정 노드에 대해 경로가 존재하지 않는 그래프
사이클, 비순환 그래프
사이클
- 단순 경로의 시작 노드와 종료 노드가 동일한 경우
비순환 그래프
완전 그래프
- 그래프의 모든 노드가 서로 연결되어 있는 그래프
그래프와 트리의 차이
| |
그래프 |
트리 |
| 방향성 |
방향, 무방향 |
방향 |
| 사이클 |
순환, 비순환, 자기순환 |
비순환 |
| 루트 노드 |
루트 개념 없음 |
한 개의 루트 존재 |
| 부모-자식 |
부모-자식 개념 없음 |
1개의 부모 노드 존재(루트 제외) |
| 모델 |
네트워크 모델 |
계층 모델 |
| 간선 수 |
자유 |
N-1 개 |
그래프의 표현
인접 행렬(Adjacent Matrix)
- 인접 행렬의 경우 각각의 정점끼리 간선이 연결되어 있는지 여부나 가중치를 행렬로 표현
- 장점
- 2차원 배열에 모든 정점의 간선 정보가 있어 두 정점간 연결 정보의 조회에 O(1)의 시간 복잡도를 가짐
- 인접리스트에 비해 구현이 쉬움
- 단점
- 모든 정점에 대해 간선 정보를 대입해야 하므로 노드 추가나 삭제에 O(n^2)의 시간 복잡도를 가짐
- 무조건 2차원 배열이 필요해 필요 이상의 메모리 낭비
인접 리스트(Adjacent List)
- 인접 리스트의 경우 각 정점을 표시하고 해당 정점에서 연결된 정점을 연결 리스트로 표현
- 장점
- 정점들의 연결 정보를 탐색할 때 O(n)의 시간 복잡도를 가짐
- 필요한 만큼의 메모리만 사용하기 때문에 메모리 낭비가 적음
- 단점
- 특정 두 정점이 연결되어있는 조회 시 인접행렬에 비해 오래 걸림 → O(E)
- 구현이 비교적 어려움
깊이 우선 탐색 VS 너비 우선 탐색
깊이 우선 탐색(DFS, Deep First Search)
- 한방향으로 인접한 정점이 없을 때 까지 탐색 한 후 다른 방향으로 탐색하는 방식
- 모든 노드를 방문하고자 하는 경우
- 너비 우선 탐색보다 간단한 구조
- 검색속도는 너비 우선 탐색 보다 느림
- 스택이나 재귀함수를 통해 구현
너비 우선 탐색(BFS, Breadth First Search)
- 너비 우선 탐색은 해당 정점에 인접한 정점을 먼저 탐색하는 방식
- 두 노드 사이의 최단 경로를 찾는 경우
- 깊이 우선 탐색에 비해 검색속도가 빠름
- 큐를 이용하여 구현
신장 트리(Spanning Tree)
개요
- 그래프 내 모든 정점을 포함하는 트리
- 그래프의 최소 연결 부분 그래프
- 간선 수가 가장 적음
- n개의 정점을 가지는 그래프의 최소 간선 수는 n-1개
- n-1개의 간선을 가진 그래프는 트리의 형태를 가지고 이러한 트리를 신장 트리라고 부름
특징
- DFS, BFS를 이용하여 그래프에서 신장 트리 탐색 가능
- 하나의 그래프에 많은 신장트리 존재
- 모든 정점들이 연결되어 있고 사이클이 포함되어 있으면 안됨
- n개의 정점을 (n-1)개의 간선으로 연결된 그래프