데이터 구조의 그래프 유형과 예제
사라 첸
⚡ 스마트 요약
데이터 구조에서 그래프는 정점과 간선의 비선형 집합이며, 구조에 따라 방향 그래프, 무방향 그래프, 가중 그래프, 순환 그래프, 비순환 그래프, 완전 그래프, 연결 그래프, 이분 그래프, 오일러 그래프, 해밀턴 그래프 등의 종류로 분류됩니다.
그래프는 정점과 간선으로 구성된 비선형 데이터 구조입니다. 정점은 정보 또는 데이터를 담고 있으며, 간선은 두 정점을 연결하는 역할을 합니다.
그래프는 노드와 에지의 위치에 따라 여러 유형으로 분류될 수 있습니다. 다음은 몇 가지 중요한 그래프 유형입니다.
방향성 그래프
방향 그래프의 간선에는 방향을 나타내는 화살표가 있습니다. 화살표는 간선이 가리키는 방향 또는 끝나는 지점을 나타냅니다. 다음은 방향 그래프의 예입니다.
방향성 그래프
- 노드 A에서 D로 이동할 수 있습니다.
- 하지만 간선이 A에서 D로 향하고 있으므로 노드 D에서 노드 A로 이동할 수 없습니다.
- 그래프에는 가중치가 없으므로 정점 A에서 D로 이동하는 비용은 D에서 F로 이동하는 비용과 같습니다.
무향 그래프
무방향 그래프는 포인터가 없는 간선을 포함합니다. 즉, 두 정점 사이를 반대 방향으로 이동할 수 있습니다. 다음은 무방향 그래프의 간단한 예입니다.
무향 그래프
위 그래프에서,
- 우리는 A에서 B로 이동할 수 있습니다.
- 우리는 B에서 A로 이동할 수도 있습니다.
- 모서리에는 방향이 없습니다.
이는 유한한 수의 정점과 가중치가 없는 간선을 가진 무방향 그래프의 예입니다.
가중 그래프
간선에 가중치 또는 비용이 있는 그래프를 가중 그래프라고 합니다. 숫자 값은 일반적으로 한 정점에서 다른 정점으로 이동하는 데 드는 비용을 나타냅니다. 방향 그래프와 무방향 그래프 모두 간선에 가중치를 둘 수 있습니다. 다음은 가중 그래프(방향 그래프)의 예입니다.
가중치가 있는 방향 그래프
- A에서 B로 가는 길에는 간선이 있고, 가중치는 5입니다. 즉, A에서 B로 이동하는 데 5의 비용이 듭니다.
- A는 B를 가리키지만, 이 그래프에서 B는 A와 직접 연결된 간선이 없습니다. 따라서 B에서 A로 이동할 수 없습니다.
- 하지만 A에서 F로 이동하려면 여러 경로가 있습니다. 경로는 ADF와 ABF입니다. ADF의 비용은 (10+11) 또는 21입니다.
- 여기서 경로 ABF의 비용은 (5+15) 또는 20입니다. 여기서는 경로에 있는 각 간선의 가중치를 더하고 있습니다.
다음은 가중치가 있는 무방향 그래프의 예입니다.
가중치가 있는 무방향 그래프
여기서 가장자리에는 무게가 있지만 방향은 없습니다. 즉, 정점 A에서 D로의 이동 비용은 10이고 그 반대의 경우도 마찬가지입니다.
양방향 그래프
양방향 그래프와 무방향 그래프는 공통적인 속성을 가지고 있습니다. 즉, 다음과 같습니다.
- 일반적으로 무방향 그래프는 두 정점 사이에 하나의 간선을 가질 수 있습니다.
예 :
- 여기서 A에서 D로, D에서 A로 이동하는 데 드는 비용은 10입니다.
- 양방향 그래프에서는 두 정점 사이에 두 개의 가장자리가 있을 수 있습니다.
다음은 그 예입니다.
양방향 그래프
A에서 D로 이동하는 데는 17의 비용이 들지만, D에서 A로 이동하는 데는 12의 비용이 듭니다. 따라서 무방향 그래프에서는 서로 다른 두 가중치를 할당할 수 없습니다.
무한 그래프
그래프는 무한한 수의 간선과 노드를 포함합니다. 그래프가 무한하고 연결 그래프인 경우, 간선의 수도 무한합니다. 여기서 확장된 간선이란 더 많은 간선이 해당 노드에 연결될 수 있음을 의미합니다. 다음은 무한 그래프의 예입니다.
무한 그래프
널 그래프
널 그래프는 노드 또는 정점만 포함하고 간선이 없는 그래프입니다. 그래프 G = (V, E)에서 V는 정점, E는 간선의 개수일 때, 간선의 개수 E가 0이면 널 그래프가 됩니다. 다음은 널 그래프의 예입니다.
널 그래프
간단한 그래프
그래프 데이터 구조는 정점 또는 노드가 하나만 있고 간선이 없는 경우 자명한 그래프로 간주됩니다. 다음은 자명한 그래프의 예입니다.
멀티 그래프
그래프에서 두 정점 사이에 여러 개의 간선이 존재하거나, 정점이 루프를 가질 때 이를 멀티그래프라고 합니다. 그래프 자료 구조에서 "루프"란 동일한 노드 또는 정점을 가리키는 간선을 의미합니다. 멀티그래프는 방향 그래프일 수도 있고 무방향 그래프일 수도 있습니다. 다음은 멀티그래프의 예입니다.
B에서 A로 가는 간선이 두 개 있습니다. 또한, 정점 E는 자기 루프를 가지고 있습니다. 위 그래프는 간선에 가중치가 없는 방향 그래프입니다.
완전한 그래프
그래프가 완전 그래프라는 것은 각 정점이 다른 모든 정점과 방향 또는 무방향 간선을 가지고 있다는 것을 의미합니다. 정점의 총 개수가 V이고 각 정점이 정확히 V-1개의 간선을 가지고 있다고 가정해 봅시다. 그러면 이 그래프를 완전 그래프라고 합니다. 완전 그래프에서는 각 정점이 간선을 통해 다른 모든 정점과 연결되어 있습니다. 다음은 정점이 다섯 개인 완전 그래프의 예입니다.
이미지에서 볼 수 있듯이 전체 노드 수는 5개이며, 모든 노드는 정확히 4개의 간선을 가지고 있습니다.
연결된 그래프
그래프에서 어떤 노드 또는 정점에서 시작하여 그 노드에서 모든 노드로 이동할 수 있다면, 그 그래프를 연결 그래프라고 합니다. 이를 위해서는 각 노드 또는 정점 쌍 사이에 적어도 하나의 간선이 있어야 합니다. 다음은 연결 그래프의 예입니다.
위의 연결 그래프에 대한 설명은 다음과 같습니다.
- C와 F 사이에 간선이 없다고 가정하면 A에서 G로 이동할 수 없습니다. 그러나 C에서 F로 이어지는 간선이 있으면 주어진 노드에서 어떤 노드로든 이동할 수 있습니다.
- 완전한 그래프는 연결된 그래프입니다. 주어진 그래프의 노드에서 다른 노드로 이동할 수 있기 때문입니다.
순환 그래프
그래프에 하나 이상의 순환이 존재하면 그 그래프를 순환 그래프라고 합니다. 다음은 순환 그래프의 예입니다.
여기서 정점 A, B, C는 사이클을 형성합니다. 그래프는 내부에 여러 개의 사이클을 가질 수 있습니다.
방향성 비순환 그래프 (DAG)
그래프 내부에 순환이 없으면 그 그래프를 방향 비순환 그래프(DAG)라고 합니다. DAG는 여러 작업을 수행할 때 중요합니다. 토폴로지 정렬 실행 순서를 찾는 데에도 사용됩니다. DAG는 스케줄링 시스템을 구축하거나 리소스의 종속성을 파악하는 데에도 중요합니다. 하지만 위의 그래프에는 순환이 없습니다. 다음은 간단한 방향 비순환 그래프(DAG)의 예입니다.
사이클 그래프
사이클 그래프는 순환 그래프와는 다릅니다. 사이클 그래프에서는 각 노드가 정확히 두 개의 간선에 연결되어 있으며, 이는 각 노드의 차수가 정확히 두 개임을 의미합니다. 다음은 사이클 그래프의 예입니다.
이분 그래프
이런 종류의 그래프 이분 그래프는 정점이 두 집합에 할당되는 특별한 종류의 그래프입니다. 이분 그래프는 다음 규칙을 따라야 합니다.
- 두 꼭짓점 집합은 서로 달라야 합니다. 즉, 모든 꼭짓점은 두 그룹 또는 집합으로 나뉘어야 합니다.
- 같은 집합에 속한 정점들은 간선을 형성해서는 안 됩니다.
오일러 그래프
그래프 데이터 구조에서 모든 정점의 차수가 짝수이면 오일러 그래프라고 합니다. 정점의 차수란 특정 정점으로 향하거나 특정 정점에서 나가는 간선의 수를 의미합니다. 다음은 오일러 그래프의 예입니다.
모든 정점의 차수는 짝수입니다. 정점 A, D, E, H는 차수가 2입니다. 여기서 노드 C는 차수가 4로 짝수입니다.
해밀턴 그래프
해밀턴 그래프는 주어진 정점에서 동일한 정점을 다시 방문하거나 동일한 간선을 사용하지 않고 모든 정점을 방문할 수 있는 연결 그래프입니다. 이러한 연결 그래프를 "해밀턴 그래프"라고 합니다. 주어진 그래프가 해밀턴 그래프인지 아닌지 확인하기 위해 방문하는 경로를 해밀턴 경로라고 합니다. 다음은 간단한 해밀턴 그래프 예시입니다.
이 이미지에서는 위 그래프의 모든 노드에서 모든 정점을 방문할 수 있습니다. 경로 중 하나는 다음과 같습니다. 아드치베또한 해밀턴 사이클을 찾을 수도 있습니다. 해밀턴 사이클은 같은 꼭짓점에서 시작하고 끝납니다. 따라서 해밀턴 사이클은 다음과 같습니다. 아드치베아.
