자료구조 비선형구조 그래프

지난번 포스팅에서는 자료구조의 비선형 구조 중에서 트리에 대해 알아보았습니다. 이번에는 대표적인 비선형 구조인 그래프에 대해 알아보려고 합니다. 그래프와 트리의 관계를 간단하게 나타내자면 그래프가 트리보다 더 큰 범위라고 생각하면 됩니다. 그래프 중에서 사이클이 없는 그래프를 트리라고 이야기하며 이외의 형태를 그래프라고 칭합니다. 그래프와 트리의 몇 가지 차이점이 더 있는데 그것에 대해서는 "비선형 구조 트리" 글에 조금 더 자세히 정리해두었습니다. 지금부터 그래프의 간단한 용어 정리와 함께 그래프의 종류에 대해서 알아보겠습니다.

 

 

그래프의 정의

 

그래프는 정점(Node, Vertex)과 그 정점을 연결하는 간선(Edge)으로 이루어진 구조를 의미합니다. 위의 두 개의 사진 모두 그래프이며 그중 오른쪽처럼 사이클이 없는 그래프가 바로 트리입니다. 왼쪽 이미지에서 Node는 A, B, C, D가 되며, 각각을 연결한 선이 바로 간선입니다. 그래프의 종류에는 방향 그래프와 무방향 그래프가 있으며 간선에 방향이 있는지 없는지에 따른 차이가 있습니다. 왼쪽 그래프 이미지의 경우 간선에 방향을 나타내는 화살표가 없기 때문에 무방향 그래프입니다. 방향, 무방향 그래프의 경우 뒤에서 조금 더 자세히 알아보겠습니다.

 

 

그래프 용어

▶ 경로 : 경로란 하나의 정점에서 다른 하나의 정점까지 가는 길을 의미합니다. 왼쪽 이미지의 A 노드에서 출발하여 C 노드로 가고 싶다고 할 때 가는 방법에는 A에서 C로 바로 가는 방법도 있지만 A->B->C나 A->D->B->C 등의 방법도 있습니다. 이렇듯이 한 정점에서 다른 정점까지의 경로는 여러 개가 있을 수도 있습니다.

▶ 사이클 : 사이클은 한 노드에서 시작해서 간선을 따라 다시 시작한 정점으로 돌아오는 경로를 의미합니다. 그래프 왼쪽 이미지를 보겠습니다. B에서 시작해서 다시 B로 돌아오는 방법으로는 B->C->A->B, B->C->D->B, B->A->D->C->B 등 다양하게 있습니다. 이처럼 B에서 출발해서 다른 정점들을 거쳐 B로 다시 되돌아오는 경로를 사이클이라고 합니다. 

▶ 경로 길이 : 경로를 구성하는 간선의 수를 의미합니다. A에서 C로 갈 때 만약 A->B->C의 경로로 갔다면 거쳐가는 간선의 수는 2개가 되는 것입니다. 

▶ 단순 경로 : 단순 경로는 한 정점에서 다른 정점에 이르거나 경로를 탐색할 때 하나의 노드를 두 번 거치지 않는 경로를 의미합니다. 즉, 하나의 노드 한 번만 방문해야 하는 것입니다.  

▶ 차수 : 하나의 노드에 연결되어 있는 간선의 수를 말합니다. 차수는 방향 그래프일 경우 진입(Indegree) 차수와 진출(Outdegree) 차수 각각 생각해주어야 합니다. 진입 차수의 경우 간선 화살표 방향이 내 정점 쪽으로 향해있는 간선의 개수를 의미하고, 진출 차수는 내 정점에서 출발해서 다른 정점 쪽으로 화살표 방향이 향해있는 간선의 개수를 의미합니다. 최종적인 차수를 구할 때에는 진입과 진출 차수를 모두 더한 값이 됩니다. 위의 왼쪽 이미지의 경우 무방향 그래프로 A 노드에 연결되어 있는 간선은 A와 B를 연결한 간선, A와 C를 연결한 간선, A와 D를 연결한 간선 이렇게 총 3개가 있습니다. 따라서 차수는 3이 됩니다. 

 

 

방향 그래프와 무방향 그래프

1. 방향 그래프

 

방향 그래프는 이름에서도 알 수 있듯이 간선에 방향이 있는 그래프를 의미합니다. A와 B 정점을 잇는 간선을 보면 화살표가 있는 것을 알 수 있습니다. 방향이 있기 때문에 한 정점에서 다른 정점으로 이동할 때 간선의 방향에 따라서만 이동이 가능합니다. 즉, A에서 D로 가는 방법은 A->B->D 뿐이며 B에서 F로 가는 방법은 B->C->F, B->D->C->F 뿐입니다. A->B->C->E->D와 같은 경로 A에서 D로 이동할 수 없으며 B->D->E->C->F 경로 B에서 F로 이동할 수 없는 것입니다. 그래프 용어 부분에서 알아봤던 차수를 설명하겠습니다. 정점 C를 기준으로 했을 때 C로 진입하는 간선의 수는 B, D에서 오는 간선 두 개 이기 때문에 진입 차수는 2, C에서 출발하는 간선은 E, F로 향하는 간선 두 개 이기 때문에 진출 차수도 2입니다. 방향 그래프의 간선의 개수는 최대 "정점의 개수 * (정점의 개수 -1)"로 구성됩니다. 위 이미지는 6개의 정점으로 이루어진 그래프로 최대 간선의 개수는 30개가 되는 것입니다. 

 

2. 무방향 그래프

이번에는 무방향 그래프에 대해 알아보겠습니다. 이 그래프 또한 이름에서 알 수 있듯이 간선에 방향이 없는 그래프를 무방향 그래프라고 합니다. 그래프 정의와 용어 설명을 하면서 계속 예로 들었기 때문에 무방향 그래프는 간단하게 간선의 개수에 대해서만 이야기하겠습니다. A와 B가 연결된 부분만 따로 보았을 때(A - B만 본다는 의미입니다.) 방향 그래프와 달리 A에서 B로 이어진 간선과 B에서 A로 이어진 간선은 같은 간선입니다. 따라서 무방향 그래프에서 최대 간선의 개수는 "정점의 개수*(정점의 개수-1) / 2"를 한 값입니다. 위 그래프는 정점 4개로 이루어진 그래프로 최대 간선의 개수가 6개가 되는 것입니다.