데이터 구조의 그래프 유형과 예제
사라 첸
그래프는 정점과 간선으로 구성된 비선형 데이터 구조입니다. 정점에는 정보나 데이터가 포함되며, 가장자리는 정점 쌍 사이의 링크 역할을 합니다.
그래프는 노드와 간선의 위치에 따라 여러 유형이 될 수 있습니다. 다음은 몇 가지 중요한 그래프 유형입니다.
방향성 그래프
방향성 그래프의 가장자리에는 방향을 의미하는 화살표가 포함되어 있습니다. 화살표는 가장자리가 가리키거나 끝나는 위치를 결정합니다.
다음은 방향성 그래프의 예입니다.
- 노드 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의 비용이 듭니다. 따라서 무방향 그래프인 경우 두 가지 다른 가중치를 할당할 수 없습니다.
무한 그래프
그래프에는 무한한 수의 모서리와 노드가 포함됩니다. 그래프가 무한이고 연결된 그래프이기도 하면 무한한 수의 간선도 포함됩니다. 여기서 확장된 가장자리는 가장자리를 통해 이러한 노드에 더 많은 가장자리가 연결될 수 있음을 의미합니다.
다음은 무한 그래프의 예입니다.
널 그래프
널 그래프(Null Graph)에는 노드나 꼭짓점만 포함되어 있지만 가장자리는 없습니다. V가 정점이고 E가 가장자리인 그래프 G = (V, E)가 주어지면 가장자리 E의 수가 XNUMX이면 null이 됩니다.
다음은 Null 그래프의 예입니다.
간단한 그래프
그래프 데이터 구조는 모서리 없이 꼭짓점이나 노드가 하나만 존재하는 경우 사소한 것으로 간주됩니다.
다음은 간단한 그래프의 예입니다.
멀티 그래프
두 정점 사이에 여러 개의 간선이 있거나 정점에 루프가 있는 경우 그래프를 다중 그래프라고 합니다. 그래프 데이터 구조에서 "루프"라는 용어는 동일한 노드 또는 꼭지점을 가리키는 가장자리를 의미합니다. 멀티그래프는 방향이 지정되거나 지정되지 않을 수 있습니다.
다음은 다중 그래프의 예입니다.
B에서 A까지 두 개의 가장자리가 있습니다. 또한 정점 E에는 자체 루프가 있습니다. 위 그래프는 간선에 가중치가 없는 방향성 그래프입니다.
완전한 그래프
각 꼭지점이 다른 모든 꼭지점과 방향이 있거나 방향이 없는 가장자리를 가지면 그래프가 완성됩니다.
총 V개의 정점이 있고 각 정점에 정확히 V-1개의 가장자리가 있다고 가정합니다. 그러면 이 그래프를 완전 그래프(Complete Graph)라고 합니다. 이 유형의 그래프에서 각 정점은 가장자리를 통해 다른 모든 정점에 연결됩니다.
다음은 XNUMX개의 꼭짓점이 있는 완전 그래프의 예입니다.
이미지에서 볼 수 있듯이 총 노드 수는 XNUMX개이며 모든 노드에는 정확히 XNUMX개의 가장자리가 있습니다.
연결된 그래프
노드 또는 정점에서 시작하여 시작 노드에서 모든 노드를 이동하는 경우 그래프를 연결된 그래프라고 합니다. 이를 위해서는 각 노드 또는 정점 쌍 사이에 최소한 하나의 가장자리가 있어야 합니다.
연결된 그래프의 예는 다음과 같습니다.
위의 "완전한 그래프 예" 그래프에 대한 설명은 다음과 같습니다.
- C와 F 사이에 간선이 없다고 가정하면 A에서 G로 이동할 수 없습니다. 그러나 C에서 F로의 간선을 사용하면 주어진 노드에서 어떤 노드로든 이동할 수 있습니다.
- 완전한 그래프는 연결된 그래프입니다. 주어진 그래프의 노드에서 다른 노드로 이동할 수 있기 때문입니다.
순환 그래프
그래프에 하나 이상의 순환이 있는 경우 그래프는 순환적이라고 합니다.
순환 그래프의 예는 다음과 같습니다.
여기서 정점 A, B, C는 순환을 형성합니다.
그래프 내부에는 여러 개의 사이클이 있을 수 있습니다.
방향성 비순환 그래프 (DAG)
그래프 내부에 순환이 없으면 그래프를 방향성 비순환 그래프 또는 DAG라고 합니다. DAG는 다음 작업을 수행하는 동안 중요합니다. 토폴로지 정렬 또는 실행 순서를 찾는 것입니다. DAG는 스케줄링 시스템을 생성하거나 리소스의 종속성을 검색하는 데에도 중요합니다. 그러나 위 그래프에는 내부 사이클이 포함되어 있지 않습니다.
다음은 DAG(방향성 비순환 그래프)의 간단한 예입니다.
사이클 그래프
순환 그래프는 순환 그래프와 다릅니다. 사이클 그래프에서 각 노드에는 정확히 두 개의 가장자리가 연결됩니다. 즉, 각 노드는 정확히 XNUMX도를 갖습니다.
사이클 그래프의 예는 다음과 같습니다.
이분 그래프
이런 종류의 그래프 정점이 두 세트에 할당되는 특별한 종류의 그래프입니다.
이분 그래프는 다음 규칙을 따라야 합니다.
- 두 개의 꼭지점 세트는 서로 구별되어야 합니다. 즉, 모든 꼭지점은 두 개의 그룹 또는 세트로 나누어져야 합니다.
- 동일한 세트 정점은 가장자리를 형성해서는 안 됩니다.
오일러 그래프
그래프 데이터 구조는 모든 정점이 짝수 차수를 갖는 경우 오일러 그래프로 간주됩니다. 정점의 정도라는 용어는 특정 정점을 가리키거나 가리키는 가장자리의 수를 의미합니다.
다음은 오일러 그래프의 예입니다.
모든 꼭짓점의 각도는 짝수입니다. 정점 A, D, E, H에는 XNUMX개의 각도가 있습니다. 여기서 노드 C의 각도는 XNUMX개로 짝수입니다.
해밀턴 그래프
해밀턴 그래프(Hamilton Graph)는 동일한 노드를 다시 방문하거나 동일한 가장자리를 사용하지 않고도 주어진 꼭지점의 모든 꼭지점을 방문할 수 있는 연결 그래프입니다. 이러한 종류의 연결된 그래프를 "해밀턴 그래프"라고 합니다. 주어진 그래프가 해밀턴 그래프인지 아닌지 확인하기 위해 방문하는 경로를 해밀턴 경로(Hamiltonian Path)라고 합니다.
다음은 해밀턴의 간단한 그래프 예입니다.
이 이미지에서는 위 그래프의 모든 노드에서 모든 정점을 방문할 수 있습니다. 경로 중 하나는 다음과 같습니다. 아드치베. 해밀턴 사이클(Hamilton Cycle)을 찾는 것도 가능합니다. 해밀턴 사이클은 동일한 정점에서 시작하고 끝납니다. 그래서 해밀턴 사이클은 ADCHBEA.
