** 그래프
- 정점들간의 관계를 표현하는 자료구조 ( G=(V,E) )
- V는 Vertex(정점) 과 E는 Edge(간선) 을 의미하며 간선은 정점들 간의 연결관계를 표시합니다.
- 간선 edge는 두 개의 정점이 있어야 정의가 됩니다 (cycle을 가지지 않을 경우)
- directred graph(유향그래프) 와 undirected graph(무향 그래프) 가 있으며
- 유향그래프에서는 vw와 wv는 다른 방향을 가지므로 다른 간선이다.
- 가중치 그래프(weighted graph) 의 경우 (V,E,W)로 구성
** 그래프의 용어
- 정점(Vertex) : 연결된 객체 (node)
- 간선(Edge) : 정점들 간의 연결관계를 나타내는 선
- incident : 정점과 간선의 관계에서 쓰는 용어 (정점에 간선이 연결된 경우)
- adjacent : 정점과 정점간의 관계에서 쓰는 용어 (정점과 정점이 간선에의해 직접적으로 연결되어있는 경우)
- 사이클(cycle) : 경로의 시작 정점과 끝 정점이 같을 경우
- 차수(degree) : 정점에 연결되어 있는 간선의 수를 그 정점의 차수 라고 한다.
** 그래프의 구현
- 보통 인접리스트로 구현을 하여, 인접 행렬으로도 구현 가능하다.
- 인접행렬로 구현을 할 경우 두 정점이 직접 연결되어있는지 (adjacent) 를 O(1) 에 바로 알아낼 수 있다.
- 그러나 어떤 특정 정점에 인접한 모든 정점들을 탐색하거나, 그래프의 간선의 수 등을 알아내려면
O(n*n)이 걸린다 matrix를 모두 조사해야하므로....
- 인접리스트로 구현할 경우 어떤 정점에 인접한 노드들은 바로 찾을 수 있다는 장점이 있다.
** 그래프의 탐색
1. 깊이우선탐색(DFS, Depth-First-Search)
- 정점을 탐색을 하는데 다음 연결된 정점을 탐색하기 전에 첫 정점과 연결된 정점을 우선 탐색
- 모든 노드를 다 탐색하고자 할 경우 자주 사용한다.
- 특정 정점에서 시작하여 원하는 다른 정점까지 경로가 있는지를 탐색할 때 사용하기도 한다.
2. 너비우선탐색(BFS, Breadth-First-Search)
- 탐색 시작 정점으로 부터 연결된 모든 정점을 먼저 탐색을 한 후 그 탐색한 정점과 연결된 다른 정점들을 탐색
- 보통 최단경로를 찾는 문제에 BFS를 많이 사용한다.
- 큐를 이용하여 구현을 많이 하는데 탐색정점과 연결된 정점들을 큐에 넣어서 탐색을 해가면서
- 탐색한 정점은 큐에서 POP하고 그 정점에 연결된 새로운정점들을 큐에 PUSH해 준다.
- 탐색을 시작할 때의 큐의 SIZE만큼 탐색을 하면 탐색 후에는 직접적으로 연결된 정점들은 모두 POP되었을 것이고
탐색을 했던 정점들과 연결된 새로운 정점들이 큐에 들어와 있다.
'학부생 공부 > 자료구조' 카테고리의 다른 글
| 배열(Array) 와 연결리스트(Linked List) 비교 (0) | 2020.12.15 |
|---|---|
| 트리 (Tree) (0) | 2020.10.14 |
| 벡터(Vector) (0) | 2020.02.15 |
| 큐(queue) (0) | 2020.02.14 |
| 스택 (Stack) (0) | 2020.02.13 |
