[자료구조] 그래프(Graph)란

안녕하세요! 오늘은 비선형 자료 구조인 그래프에 대해서 공부해보겠습니다.

탐색 알고리즘을 공부해보셨다면 아마 익숙하실거에요.
BFS, DFS 정도는 알고리즘 문제로 흔히 나오는 편이니 이 참에 그래프를 공부하는 건 어떨까요?

---

그래프란

그래프는 비선형 자료 구조로 1) 데이터들 간의 2) 관계를 표현한 자료 구조입니다.
여기서 말한 데이터=노드, 관계=엣지 가 됩니다.
다시 말해 그래프는 노드와 엣지로 이루어졌다고 보시면 됩니다.

한번 그림으로 예시를 들어볼까요?

그래프 예시

유비, 관우, 장비 노드 3개가 있고, 각각의 노드가 다른 노드들과 연결되어 있는 그래프입니다.
그래프는 데이터 간의 관계를 표현하는 자료 구조라고 했는데 이 그래프에서는 어떤 관계가 보이시나요?

정답은 의형제 관계입니다!
유비는 관우, 장비와 의형제를 맺었고 관우는 유비, 장비와 의형제를, 그리고 장비는 유비, 관우와 의형제를 맺은 것이죠.

그렇다면 다음 예시는 어떨까요?

지도 그래프

이 그래프에서는 노드들이 지역입니다. 그런데 위의 의형제 그래프와는 다르게 엣지에 숫자가 적혀있죠?
바로 지역간 거리를 뜻하는 숫자입니다.

의형제 그래프에서는 우애를 숫자로 표현할 수 없기에 단순히 관계만 보여줬지만 지역 간 거리는 숫자로 표현할 수 있어서 위와 같이 표현하게 되었습니다.

용어 정리

1. 노드 간 거리를 엣지의 weight 혹은 cost라고 합니다.

• 어떤 요소를 노드 간 거리로 보는지도 아주 흥미로운 요소입니다.
• 기업 간 채무관계를 cost로 나타낼 수도 있고, 지역 간 인구 이동을 cost로 표현할 수 있습니다.

2. 노드에 연결된 엣지의 수를 degree라고 합니다.

• 지도 그래프를 보면 다른 노드들과는 다르게 "세종" 노드만 degree가 4이죠?
• degree를 보면 노드가 얼마나 많은 노드들과 관계를 맺고 있는지 알 수 있습니다.

그래프의 방향성

만약 세종에서 대전으로 가는 길이 막히면 어떻게 될까요? 엣지에 방향성이 생기게 됩니다.
엣지에 방향성이 있는 그래프를 directed graph, 엣지에 방향성이 없는 그래프를 undirected graph라고 합니다.

세종에서 대전 못 가요 ㅜㅠ

---

그래프에 대해서 공부해봤는데 어떠셨나요?
이번에 그래프가 무엇인지 간단히 살펴봤으니 다음번에는 그래프 탐색 알고리즘을 공부해보려고 합니다.
항상 힘내시고 행복하세요!