티스토리 뷰
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다.
* 그래프(Graph)
- 연결되어 있는 원소간의 관계를 표현하는 자료구조
- 정점(Node) : 연결할 객체, 위치
- 간선(Edge) : 객체를 연결하는 선 , 관계
- G = (V,E) : V는 그래프에 있는 정점들의 집합을 의미하며, E는 정점을 연결하는 간선들의 집합을 의미함
[그래프의 구조]
* 그래프의 종류
1) 무방향 그래프(Undirected Graph)
- 두 정점을 연결하는 간선에 방향이 없는 그래프
- (Vi, Vj) : 정점 Vi, Vj을 연결하는 간선을 표현
2) 방향 그래프(Directed Graph)
- 간선에 방향이 있는 그래프
- 다이그래프(Digraph)라고도 함
- <Vi, Vj> : 점 Vi, Vj을 연결하는 간선을 표현, Vi -> Vj
3) 완전 그래프(Complete Graph)
- 한 정점에서 다른 모든 정점과 연결되어 최대의 간선 수를 가진 그래프
- 정점이 n개인 무방향 그래프의 최대 간선 수 = n(n-1) / 2개
- 정점이 n개인 방향 그래프의 최대 간선 수 = n(n-1)개
4) 부분 그래프(SubGraph)
- 원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프
5) 가중 그래프(Weight Graph)
- 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프
- 네트워크(Network)라고도 함
* 그래프 관련 용어
- 그래프에서 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때 두 정점 Vi, Vj를 인접(Adjacent)되어 있다고 하고, 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(Incident)되어 있다고 함
- 경로(Path) : 간선을 따라갈 수 있는 길을 순서대로 나열한 것, 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
- 경로 길이(Path Length) : 경로를 구성하는 간선의 수
- 인접 정점(Adjacent Vertex) : 간선에 의해 연결된 정점
- 단순 경로(Simple Path) : 모두 다른 정점으로 구성된 경로
- 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
방향그래프에서의 차수
- 진입차수 : 외부 노드에서 들어오는 간선의 수
- 진출 차수 : 한 노드에서 외부로 향하는 간선의 수
* 그래프 순회(Graph Traversal), 그래프 탐색(Graph Search)
- 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것
* 그래프 순회 종류
1) 깊이 우선 탐색 (DFS, Depth-First Search)
- 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회함
- 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가 다시 깊이 우선 탐색을 반복해야 하므로 LIFO구조의 스택을 사용
[수행 순서]
(1) 시작 정점 v를 결정하여 방문
(2) 정점 v에 인접한 정점 중에서
1) 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push하고 w를 방문함, 그리고 w를 v로 설정하고 다시 (2) 반복
2) 방문하지 않은 정점이 없으면 스택을 pop하여 구한 가장 마지막 방문 정점을 v로 설정하고 다시 (2) 수행
(3) 스택이 공백이 될 때까지 (2) 반복
2) 너비 우선 탐색 (BFS, Breadth-First Search)
- 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문함
- 인접한 정점을 방문한 뒤 다시 해당 정점의 인접한 정점을 방문하며 그래프를 순회함
- 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 FIFO구조를 갖는 큐를 사용
[수행 순서]
(1) 시작 정점 v를 결정하여 방문
(2) 정점 v에 인접한 정점 중에서
1) 방문하지 않은 인접 정점이 있으면 차례로 방문하면서 큐에 enQueue함
2) 방문하지 않은 인접 정점이 없으면 큐를 deQueue하여 구한 정점을 v로 설정하고 다시 (2) 반복
(3) 큐가 공백이 될 때까지 (2) 반복
* 신장 트리(Spanning Tree)
- n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리
- 최소의 도로를 사용하여 모든 도시를 연결해야 하는 도로망 건설이나 최소의 네트워크선을 사용하여 시스템을 연결해야 하는 통신망 설계 등과 같은 여러 분야에 응용
* 최소 신장 트리(MST, Minimum Spanning Tree)
- 트리를 구성하는 간선들의 가중치를 합한 값이 최소가 되는 신장 트리
- 가중치 무방향 그래프가 베이스일때 구할 수 있음
- MST를 찾아내는 방법은 다양하며 대표적으론 크루스칼(Kruskal), 프림(Prime) 알고리즘 존재
- 도로 건설(도로 길이 최소), 전기 회로(전선 길이 최소), 통신(전화선 길이 최소), 배관(파이프 총 길이 최소)에 활용
'개인공부 > 자료구조|알고리즘' 카테고리의 다른 글
| [자료구조] 검색(Search) 개념 (0) | 2023.11.22 |
|---|---|
| [자료구조] 정렬(Sort) 개념 (0) | 2023.11.22 |
| [자료구조] 트리(Tree) (0) | 2023.11.20 |
| [자료구조] 큐(Queue) (0) | 2023.11.20 |
| [자료구조] 스택(Stack) (0) | 2023.11.20 |