그래프(Graph)
그래프는 정점 와 간선로 이루어진 자료구조이다.
이는 트리(Tree)와 같지만, 트리는 Acyclic(사이클 x)인 반면 그래프는 사이클이 존재한다. (Cyclic)
각 정점(Vertex)들이 간선(Edge)들로 연결되어, 연결된 정점 간의 관계를 표현할 수 있는 자료구조이다.
그래프의 구조(용어)
- 정점(Vertex) : 노드
- 간선(Edge) : 각 노드간의 연결 선 ( = link, branch)
- 인접 정점(Adjacent Vertex) : 간선 하나만을 통해 바로 연결되어 있는 정점 (정점 1과 정점 4는 인접정점 x)
무방향 그래프
- 정점의 차수(Degree) : 하나의 정점에 인접한 정점의 수 (정점 1의 차수는 2 ), (정점 A의 차수는 3)
- 무방향 그래프에서 모든 정점 차수의 합은 그래프 전체 간선 수의 2배이다.
방향 그래프
- 진입 차수(In-Degree) : 방향 그래프에서 각 정점으로 외부에서 들어오는 간선의 수 (정점 B의 진입 차수는 2)
- 진출 차수(Out-Degree) : 방향 그래프에서 각 정점에서 외부로 나가는 간선의 수 (정점 A의 진출 차수는 3)
경로
- 경로 길이(Path length) : 경로를 구성하는데 사용된 간선의 수
- 방향그래프에서 A에서 E로 가는 경우는 여러가지이고, 각각의 경로길이는 다르다.
- A -> B -> D -> E : 경로길이=3
- A -> D -> E : 경로길이=2
- 단순 경로(Simple path) : 경로 중에서 반복되는 정점이 없는 경우
- 사이클(Cycle) : 단순경로로 한 바퀴 돌아서 다시 같은 노드로 돌아오는 경우
- 만약 방향그래프 이미지에서 A - D간의 간선이 D에서 A를 향하고 있다면, A -> B -> D -> A를 사이클이라고 한다.
그래프와 트리 비교
| 그래프 | 트리 | |
| 정의 | 노드와 간선을 하나로 모아놓은 자료구조 | 그래프의 한 종류 (방향성이 있는 비순환 그래프) |
| 방향성 | 방향 그래프 , 무방향 그래프 | 방향 그래프 |
| 사이클 | Cyclic 순환그래프(Cyclic), 비순환 그래프 모두 가능(Acyclic) |
Acyclic 비순환 그래프(Acyclic Graph) |
| 루트 노드 | 루트 노드의 개념이 없음 | 가장 위에 하나의 루트 노드가 존재 |
| 부모-자식 | 부모-자식의 개념이 없음 | 부모-자식 관계로 이루어짐 모든 자식 노드는 한개의 부모 노드만을 가짐 |
| 모델 | 네트워크 모델 | 계층 모델 |
| 순회 | DFS, BFS | Pre-order, In-order, Post-order / Level-order |
| 간선의 수 | 그래프마다 다름 | 노드가 N개인 트리는 항상 N-1개의 간선을 가짐 |
| 경로 | 2개 이상의 경로 가능 | 두 노드간의 경로는 1개만 가질 수 있음 |
그래프의 종류
1. 무방향 그래프(Undirected Graph)
- 두 정점을 연결하는 간선에 방향이 없는 그래프
- 정점 A - B 간선의 표현 : (A, B) = (B, A)
2. 방향 그래프(Directed Graph)
- 두 정점을 연결하는 간선에 방향이 있는 그래프
- 지정된 방향으로만 이동 가능
- 정점 A - B 간선의 표현 : <A, B> ≠ <B, A>
3. 완전 그래프(Complete Graph)
- 모든 정점이 서로 연결되어 최대 간선 수를 갖는 그래프
- 정점이 N개일 경우, 간선 수는 N(N-1) / 2 개
4. 가중치 그래프(Weight Graph)
- 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프
그래프 탐색
1. DFS : 깊이 우선 탐색 (Depth First Search)
- 그래프의 모든 노드를 방문하는 완전 탐색 방식이다.
- 임의의 시작노드에서 출발하여 한쪽 분기를 정해서 최대 깊이까지 탐색을 마친 후, 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
- 재귀함수 또는 Stack 자료구조를 이용한다.
2023.05.08 - [Algorithm/탐색 (search)] - DFS(깊이 우선 탐색)
DFS(깊이 우선 탐색)
DFS(Depth-First Search) : 깊이 우선 탐색 그래프 완전 탐색 : 모든 노드를 방문하고자 할때, 이 방법을 선택한다. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을
innovation123.tistory.com
2. BFS : 너비 우선 탐색(Breadth First Search)
- 그래프의 모든 노드를 방문하는 완전 탐색 방식이다.
- 임의의 시작노드에서 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
- FIFO 탐색 -> Queue 자료구조를 이용한다.
- 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
2023.05.08 - [Algorithm/탐색 (search)] - BFS(깊이 우선 탐색)
BFS(너비 우선 탐색)
BFS(Breadth-First Search) : 너비 우선 탐색 그래프 완전 탐색 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. FIFO 탐색 -> Queue 자료구조를 이
innovation123.tistory.com
그래프의 구현
인접 행렬 (Adjacency Matrix)
- 2차원 배열을 이용한다.
- 노드수가 N개 일때, N x N의 int 행렬 또는 boolean 행렬을 만들어서, 연결 상태 값을 설정한다.
- matrix[ i ][ j ] == true 라면 i -> j로의 간선이 있다는 뜻이다. (int 행렬의 경우 1 = true, 0 = false)
인접 행렬 방식의 특징
- 배열로 구성되어 있기 때문에, 간선 정보 조회가 빠름 O(1)
- 간선의 개수와 무관하게 항상 N^2개의 메모리 공간을 차지한다.
- 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.
인접 리스트 (Adjacency List)
인접 리스트로 그래프를 표현하는 것이 일반적인 방법이다.
- 연결리스트를 이용하여 모든 정점을 인접리스트에 저장한다.
- ArrayList 형 배열( ArrayList<Integer>[] )을 만들어서 연결된 노드를 각각 저장한다.
인접 리스트 방식의 특징
- 연결된 노드의 개수와 딱 맞는 크기로 리스트를 만들기 때문에 메모리 사용량이 상대적으로 적다.
- 노드의 추가 삭제가 빠르다.
- 간선 정보 확인이 상대적으로 오래걸린다.
인접 행렬과 인접 리스트 중 선택 방법
인접 행렬
- 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우
즉, 노드의 개수가 적고 간선의 수가 많을 때 더 낫다.
인접 리스트
- 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우
즉, 노드의 개수가 많고 간선의 수가 적을 때 더 낫다.
참고
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
https://leejinseop.tistory.com/43
반응형
'자료구조_알고리즘 > 자료구조_Java' 카테고리의 다른 글
| [JAVA/자료구조] 우선순위 큐(Priority Queue) (Heap) (0) | 2023.06.11 |
|---|---|
| [JAVA/자료구조] 힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap) (0) | 2023.06.11 |
| [JAVA/자료구조] HashSet (0) | 2023.06.09 |
| [JAVA/자료구조] 트리(Tree), 이진트리(Binary Tree) 란? (0) | 2023.06.08 |
| [JAVA/자료구조] Map / HashMap / Hashtable (0) | 2023.06.06 |
