[자료구조] 그래프(graph) 개념

알고리즘 문제를 풀 수 있을 정도로만 간단하게 그래프에 대해 알아보도록 한다.

• 그래프 정의
• 그래프 종류
• 그래프 탐색

---

그래프 정의

'정점과 간선의 집합'
그래프를 정의하는 문장에는 여러가지가 있는데 나는 위가 제일 마음에 들었다. 정점과 간선이 무엇인지는 아래 그림과 설명하겠다.

숫자가 써있는 동그란 것들을 정점(vertax)이라고 한다. 정점은 노드(node)라고도 부른다. 노드에는 데이터가 들어간다. 그리고 정점들을 연결하고 있는 선은 간선(edge)이라고 한다. 간선은 두 노드를 이어준다.
정점의 집합과 간선의 집합을 표현하는 방법도 있다. 주로 정점의 집합은 V, 간선의 집합은 E로 표현한다. 위 그림에서 정점의 집합 V = {1, 2, 3, 4, 5, 6}이고, 간선의 집합 E = {(1, 2), (1, 3), (2, 4), (4, 5), (4, 6)}이다. 집합인 V, E는 절댓값을 씌워서 크기를 표현할 수 있다. 위 그림에서 |V| = 6이고, |E| = 5이다.
각 정점은 차수를 가지고 있다. 차수는 정점들에 연결되어 있는 간선의 개수를 의미한다. 1번 정점의 차수는 2, 3번 정점의 차수는 1, 4번 정점의 차수는 3이다.

---

그래프 종류

그래프의 종류는 많지만 이 글에서는 간단하게 세 가지 그래프만 알아볼 것이다.

무방향 그래프

두 정점을 연결하는 간선에 방향이 없는 그래프이다. 위 그래프 정의에 있는 그래프가 무방향 그래프이다. 간선의 방향이 없기 때문에 어느 방향으로든 움직일 수 있다.

방향 그래프

두 정점을 연결하는 간선에 방향이 있는 그래프이다. 간선에 표시된 방향으로만 움직일 수 있다.

가중치 그래프

두 정점을 연결한느 간선에 가중치가 있는 그래프이다. 이 가중치는 두 정점 사이의 거리, 간선을 지나는데 필요한 비용 등 다양한 의미를 가질 수 있다.

---

그래프 탐색

하나의 노드에서 시작하여 그래프의 모든 노드를 방문하는 것을 그래프 탐색이라고 한다. 그래프를 탐색하는 방법에 대표적으로 DFS, BFS가 있다.

DFS

DFS는 Depth-First Search의 약자로 깊이 우선 탐색이라고 한다. 그래프에서 깊은 부분을 우선적으로 탐색하는 방법이다.
DFS에 대한 조금 더 자세한 내용은 다음 링크에 있다.(https://085a.tistory.com/9)

BFS

BFS는 breadth-First Search의 약자로 너비 우선 탐색이라고 한다. 인접한 노드를 우선적으로 탐색하는 방법이다.
BFS에 대한 조금 더 자세한 내용은 다음 링크에 있다.(https://085a.tistory.com/m/10)

---

잘못된 내용이 있다면 알려주세요!