❓ 그래프(Graph)란?
그래프(Graph)란 연결되어 있는 원소 간의 관계를 표현한 자료구조를 말합니다.
- 일상에서는 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수과목 등을 예시로 들 수 있습니다.
그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraph)로 구성될 수 있습니다.
- 그래프는 연결할 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합으로 구성됩니다.
- 그래프 G를 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미합니다.
📌 그래프의 종류
- 무방향 그래프(Undirected Graph)
- 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프입니다.
- 무방향 그래프에서 정점 Vi왕 Vj를 연결하는 간선을 (Vi, Vj)로 표현하는데, 이때 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타냅니다.
- V(G1) = {A, B, C, D}, E(G1) = {(A, D), (B, C), (B, D), (C, D)}
- 방향 그래프(Directed Graph)
- 방향 그래프는 간선에 방향이 있는 그래프입니다.
- 방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 <Vi, Vj>로 표현하는데 Vi를 꼬리(tail), Vj를 머리(head)라고 합니다. 이때 <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선입니다.
- V(G1) = {A, B, C, D} E(G1) = {<A, B>, <A, D>, <B, C>, <B, D>, <C, D>}
- 완전 그래프(Complete Graph)
- 완전 그래프는 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프입니다.
- 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n(n-1)/2이고, 방향 그래프의 최대 간선 수는 n(n-1)입니다.
- 부분 그래프(Subgraph)
- 부분 그래프는 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프입니다.
- 가중 그래프(Weight Graph)
- 가중 그래프는 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프입니다.
- 유향 비순환 그래프(DAG, Directed Acyclic Graph)
- 방향 그래프에서 사이클이 없는 그래프입니다.
- 연결 그래프(Connected Graph)
- 떨어져 있는 정점이 없는 그래프입니다.
- 단절 그래프(Disconnected Graph)
- 연결되지 않은 정점이 있는 그래프입니다.
📌 알아야 하는 그래프 용어들
| 용어 | 의미 |
| 정점 (vertex) | 위치라는 개념 (node 라고도 부름) |
| 간선 (edge) | 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) |
| 인접 정점 (adjacent vertex) | 간선에 의해 직접 연결된 정점 |
| 정점의 차수 (degree) | 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 |
| 진입 차수 (in-degree) | 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름) |
| 진출 차수 (out-degree) | 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름) - 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수 (내차수 + 외차수) |
| 경로 길이 (path length) | 경로를 구성하는데 사용된 간선의 수 |
| 단순 경로 (simple path) | 경로 중에서 반복되는 정점이 없는 경우 |
| 사이클 (cycle) | 단순 경로의 시작 정점과 종료 정점이 동일한 경우 |
그래프에서 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)한다 하고, 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 말합니다.
개념을 익혔다면 다음으로 알아야할 것은 그래프의 탐색일 것입니다.
이에 관련된 내용은 다음에 정리하도록 하겠습니다.
.Reference
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
[자료구조] 그래프(Graph)란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
https://leejinseop.tistory.com/43
[자료구조] 그래프(Graph)의 개념 설명
1. 그래프 그래프(Graph)는 연결되어있는 원소간의 관계를 표현한 자료구조입니다. · 그래프는 연결할 객체를 나타내는 정점(Vertext)과 객체를 연결하는 간선(Edge)의 집합으로 구성됩니다. · 그래
leejinseop.tistory.com
https://pangtrue.tistory.com/147
[자료구조] 그래프(Graph)
그래프(Graph) 그래프란 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 그래프의 종류는 크게 3가지로 나뉜다. 무방향 그래프(undirected graph) 방향 그래프(directed graph) 가중치 그래프(weight
pangtrue.tistory.com
'프론트엔드 면접 질문 > 자료구조와 알고리즘' 카테고리의 다른 글
| [자료구조] 트리(Tree)의 개념과 종류 (0) | 2024.03.29 |
|---|---|
| [자료구조] 그래프(Graph)의 탐색 및 구현 (0) | 2024.03.29 |
| [자료구조] 스택(Stack)과 큐(Queue) (0) | 2024.03.27 |
| [자료구조] 자료구조의 종류와 분류 (0) | 2024.03.27 |
| [자료구조] 자료구조란 (0) | 2024.03.27 |
