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

 

 

 

 경로탐색 알고리즘을 정리하기에 앞서 그래프 자료구조에 대해 정리해보려고 한다. 

 

 

 

 

그래프 자료구조

 

 

그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미하며,
vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. - 위키백과

 

 

 

 

 

 

 

 

 

 네트워크상에서 연결된 호스트의 관계를 나타낸다거나 게임이나 메신저에서 유저간에 친구관계를 나타낼때 위와 같은 그림을 자주 볼 수 있을 것이다. 그래프는 이처럼 vertex(정점)간의 연결 관계를 나타내기에 적합한 자료구조이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그래프의 종류

 

 

 

 

 

 

 

 

 

 위의 그림처럼 일반적인 그래프에서 매 간선마다 가중치를 다르게 설정하는 경우 '가중치 그래프(Weighted Graph)'라고 부른다. 지하철 노선도와 같이 매 역마다 거리가 다른 경우 가중치 그래프처럼 모든 역(vertex)과 역 사이의 거리(edge)가 다르므로 가중치 그래프를 이용하여 지하철 노선도를 표현할 수 있다.

 

 

 

 

 

 

 

 

 간선도 방향이 존재할 수 있다. 이 경우 '방향 그래프(Directed Graph)'라고 부르며, 일방 통행이 포함된 도로망이나 두 사람 사이의 호감도 등을 표현하는 그림에서 주로 사용이 된다.

 

 

 

 

 

 

 

 

 그래프의 종류는 매 알고리즘 문제마다 달라진다. 그래프 문제에선 어떤 방식의 그래프를 제시해 주는 지를 파악하고 거기에 어떤 알고리즘을 적용하여 풀이해야 하는 지를 빠르게 판단하는 것이 중요하기에 그래프마다의 특징도 어느정도 파악하고 있는 것이 좋다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 이러한 그래프를 코드로 나타내는 데에는 인접 리스트, 인접 행렬 방식 중 하나를 이용해서 알고리즘 문제 풀이에 사용되는 편이다. 이번엔 코드를 통해 어떤식으로 그래프를 표현할지 C++을 기준으로 아래의 그래프를 표현해보자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

인접 리스트

 

 

 

 

 

 

vector<vector<int>> adjacent(6);
adjacent[0] = { 1, 3 };
adjacent[1] = { 0, 2, 3 };
adjacent[3] = { 4 };
adjacent[5] = { 4 };

 

 

 

 

 

 

 

 인접 리스트 방식은 인접해 있는 노드들의 정보만을 기록하는 방식이다. 0번 vertex는 1, 3번 vertex와 연결되어 있으므로 위의 코드처럼 표현할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

인접 행렬

 

 

 

 

 

 

 

vector<vector<bool>> adjacent(6, vector<bool>(6, false));
adjacent[0][1] = true;
adjacent[0][3] = true;
adjacent[1][0] = true;
adjacent[1][2] = true;
adjacent[1][3] = true;
adjacent[3][4] = true;
adjacent[5][4] = true;

 

 

 

 

 인접 행렬 방식은 인접해있지 않은 노드들의 정보를 포함하여 행렬을 이용해 연결 여부를 표현하는 방식이다. 인접 리스트 방식과 같이 2차원 배열을 이용하지만 인접해있지 않은 노드들의 정보를 포함한 모든 정보가 표현된다.

 

 

 

 

 

 

 

 

 

 

어떤 방식을 쓸까?

 

 

 

 

 

 둘 다 장단점이 있다. 인접 리스트 방식은 연결된 노드의 정보만을 표현하므로 인접 행렬방식에 비해 메모리 소모가 적은 반면, 인접 행렬 방식의 경우 vertex간의 연결 관계를 보다 직관적으로 표현 가능하고 임의 접근을 통해 연결여부를 확인하여 알고리즘 수행에서 오히려 소모 시간이 인접 리스트 방식에 비해 적은 편이다.

 

 

 

 

 

 

 

 그리고 대부분의 상황에서 인접 리스트 방식이 선호된다. 사실 메모리 소모는 문제에서 메모리 사용 제한을 걸어두지 않는 이상 별 차이가 나지도 않고, 만약 간선에 가중치가 전부 다르다면 행렬상에 그 가중치를 표시함으로써 가중치가 있는 그래프도 쉽게 표현이 가능하기 때문에 그러하다.