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

그래프라고 하면 원 그래프나 막대 그래프, 혹은 수학의 y=f(x) 그래프가 생각날 수 있다.

하지만 컴퓨터 과학에서 사용하는 그래프는 좀 다르다. 이번 포스팅에서는 컴퓨터 과학에서 말하는 그래프에 대해 알아보도록 하겠다.

현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다!

---

📝 그래프 개념

그래프

원으로 그려진 것은 정점 혹은 노드(N, node)라고 한다. 그리고 정점과 정점을 이은 선분을 간선(E, edge)라고 한다.

즉, 그래프란 몇개의 정점이 간선으로 연결되어 있는 것을 말한다.

---

💡 그래프 예시

그래프를 사용하면 세상의 다양한 것들을 표현할 수 있다.

실생활에서 대표적으로 지하철노선도가 있다.

지하철 노선도

출처: 한국공항공사

지하철역을 정점으로 하고, 이웃하는 두 역을 간선으로 연결하면 노선도를 표현하는 그래프를 만들 수 있다.

 

또 컴퓨터 네트워크에서 라우터를 정점으로 하고, 링크로 연결된 두 라우터를 간선으로 연결하면 네트워크의 접속 관계를 표현하는 그래프가 된다.

---

📊 그래프의 종류

1. 가중 그래프

앞에서 설명한 그래프는 정점과 간선으로만 구성되어 있지만, 간선에 값이 붙어 있는 그래프도 있다.

간선에 할당된 값을 간선의 무게나 비용이라고 부르며, 이러한 그래프를 가중 그래프라고 한다.

간성에 비용이 없으면 정점 간 연결 여부만 표현할 수 있지만, 비용이 있으면 연결의 강도를 표현하는 것이 가능하다.

 

가중 그래프

 

 

이 연결의 강도가 무엇을 의미하는지는 그래프가 표현하는 내용에 따라 달라진다.

예를 들어 노선도의 경우 두 역 사이 이동 시간을 간선의 비용으로 하면 이동 시간을 표현하는 그래프가 된다.

 

2. 방향 그래프

간선에 방향을 부여할 수 있다. 이러한 그래프를 방향 그래프라고 한다.

웹 페이지의 링크도 방향성이 있기 때문에 방향그래프로 표현하면 편리하다.

방향 그래프

위 그래프를 보면 정점 A에서 B로 이동할 수 있지만, B에서 A로 직접 이동은 할 수 없다. B와 C 사이에는 양방향 간선이 있으므로 어느 쪽이든 이동이 가능하다.

 

비용을 부여한 방향 그래프

또한, 방향그래프에도 간선에 비용을 부여할 수 있다. 위 그래프를 보면 B에서 C로 이동하는 비용이 7이지만 C에서 B로 이동하는 비용은 5다. 만약 그래프가 이동시간을 나타낸 그래프라면 B에서 C로 이동할 때는 언덕이 있어 시간이 더 걸린다는 것을 표현할 수 있다.

 

3. 무방향 그래프

방향 그래프와 반대로 간선에 방향이 없는 경우를 무방향 그래프라고 한다.

---

📝 그래프를 쓰는 이유

만약 그래프에 지정된 두 정점 s에서 e로 가는 경로 중에서 비용의 합계가 최소가 되는 경로를 찾는 알고리즘을 만들었다고 가정하다. 이 알고리즘은 네트워크에서 통신 시간이 가장 짧은 경로를 찾는 문제, 노선도에서 이동 시간이 가장 짧은 경로를 찾는 문제 등 다양한 문제에 적용할 수 있다. 이처럼 다양한 대상을 그래프라는 도구로 표현해 실생활의 문제를 해결할 수 있다.

---

🔍 그래프 탐색 

그래프 탐색은 한 정점에서 시작하여 간선을 타고 그래프를 탐색하며 목표를 찾는다.

이때 탐색 순서에 따라 너비 우선 탐색, 깊이 우선 탐색으로 나뉜다.

 

각 탐색은 알고리즘 포스팅에서 따로 다루도록 하겠다.

[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)

 

[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)

 

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

[자료구조] 그래프(Graph)란 : heejeong Kwon / https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html