이번 시간에는 기초적인 그래프에 대해서 알아보겠다.
그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다.
정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수 있다.
이러한 면에서 트리는 그래프의 일종인 셈이다
하지만 그래프는 트리와는 달리 정점마다 간선이 있을 수도 있고 없을 수도 있으며, 루트노드와 부모와 자식이라는 개념이 존재하지 않는다.
그래프와 트리의 차이점에 대해서는 아래의 표로 좀 더 자세하게 설명하겠다.
그래프와 트리의 차이
그래프와 관련된 용어
-
정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3)
-
간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다.
-
인접 정점(adjacent Vertex) : 간선에 의해 직접 연결된 정점 (0과 2은 인접정점)
-
단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우. 한붓그리기와 같이 같은 간선을 지나가지 않는 경로 ( 0->3->2->1 은 단순경로 )
-
차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (0의 차수는 3)
-
진출 차수(in-degree) : 방향 그래프에서 외부로 향하는 간선의 수
-
진입 차수(out-degree) : 방향 그래프에서 외부에서 들어오는 간선의 수
-
경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
-
사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
그래프의 종류
무방향 그래프(Undirected Graph)
- 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.
방향 그래프(Directed Graph)
- 방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프이다. 간선의 방향으로만 이동할 수 있다
가중치 그래프(Weighted Graph)
가중치 그래프는 간선에 가중치(비용)가 할당된 그래프로, 두 정점을 이동할 때 비용이 드는 그래프이다.
연결 그래프(Connected Graph)
무방향 그래프에 있는 모든 정점 쌍에 대해서 항상 경로가 존재하는 그래프
즉, 노드들이 하나도 빠짐없이 간선에 의해 연결되어 있는 그래프로 트리(Tree)가 대표적인 예이다
비연결 그래프(Disconnected Graph)
무방향 그래프에서 특정 정점 사이에 경로가 존재하지 않는 그래프
즉, 노드들 중 간선에 의해 연결되어 있지 않은 그래프이다.
완전 그래프(Complete graph)
그래프의 모든 정점이 서로 연결되어 있는 그래프이다. (인접 연결)
순환그래프(Cycle)
- 단순 경로에서 시작 정점과 도착 정점이 동일한 그래프이다. (A에서 시작-> A에서 끝 가능)
비순환그래프(Acyclic Graph)
사이클 그래프를 제외한 그래프로, 사이클이 없는 그래프이다.
신장트리(Spanning Tree)
그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프
트리의 속성을 만족하기 때문에 사이클이 존재하면 안된다.
최소 신장트리(Minimum Spanning Tree)
신장트리(Spanning Tree)중 간선의 가중치 합이 최소인 신장 트
그래프의 구현 방법
그래프를 구현하는 방법에는 인접행렬과 인접리스트 방식이 있다. 두 개의 구현방식은 각각의 상반된 장단점을 가지고 있다.
인접행렬 방식
인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다.
노드들 간에 직접 연결이 되어있으면 1을, 아니면 0을 넣어서 행렬을 완성시킨 것이다.
인접행렬의 장점
2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1) 의 시간복잡도면 가능하다.
인접리스트에 비해 구현이 쉽다.
인접행렬의 단점
모든 정점에 대해 간선 정보를 대입해야 하므로 의 시간복잡도가 소요된다.
무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다
구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 30
typedef struct GraphType
{
int n;
int adjMatrix[MAX_VERTEX][MAX_VERTEX];
}GraphType;
void createGraph(GraphType* g) // 그래프를 초기화시킨다.
{
int row, col;
g->n = 0;
for (row = 0; row < MAX_VERTEX; row++)
{
for (col = 0; col < MAX_VERTEX; col++)
{
g->adjMatrix[row][col] = 0;
}
}
// 그래프를 초기화하는 방법이다. 인접행렬은 row && col를 이용해서 for문과 함께 값을 0으로 초기화시킨다.
}
void insertVertex(GraphType* g, int v)
{
//정점을 삽입하는 함수 [예외 처리 ]
if ((g->n) + 1 > MAX_VERTEX)
{
printf("\n 그래프 정점의 개수를 초과하였습니다.");
return;
}
g->n++;
}
void insertEdge(GraphType* g, int u, int v)
{
if (u >= g->n || v >= g->n)
{
printf("\n 그래프에 없는 정점입니다.\n");
return;
}
g->adjMatrix[u][v] = 1;
}
void printfadjMatrix(GraphType* g)
{
int row, col;
for (row = 0; row < (g->n); row++)
{
printf("\n\t\n");
for (col = 0; col < (g->n); col++)
{
printf("%2d", g->adjMatrix[row][col]);
}
}
}
int main()
{
int row;
GraphType* G1, * G2;
G1 = (GraphType*)malloc(sizeof(GraphType));
G2 = (GraphType*)malloc(sizeof(GraphType));
createGraph(G1);
for (row = 0; row < 4; row++)
{
insertVertex(G1, row);
}
insertEdge(G1, 0, 1);
insertEdge(G1, 0, 2);
insertEdge(G1, 0, 3);
insertEdge(G1, 1, 0);
insertEdge(G1, 1, 1);
insertEdge(G1, 1, 2);
insertEdge(G1, 2, 0);
insertEdge(G1, 2, 1);
insertEdge(G1, 2, 2);
insertEdge(G1, 2, 3);
insertEdge(G1, 3, 2);
insertEdge(G1, 3, 0);
insertEdge(G1, 3, 3);
printf("\n G1의 인접행렬");
printfadjMatrix(G1);
for (row = 0; row < 4; row++)
{
insertVertex(G2, row);
}
insertEdge(G2, 0, 1);
insertEdge(G2, 0, 3);
insertEdge(G2, 2, 3);
insertEdge(G2, 3, 1);
printf("\n\n G2의 인접 행렬");
printfadjMatrix(G2);
getchar();
}인접리스트 방식
인접리스트는 그래프의 노드를 리스트로 표현한 것이다.
주로 정점의 리스트 배열을 만들어 관계를 설정하며 노드들 간에 직접 연결이 되어있으면 해당 노드의 인덱스에 그 노드를 삽입해주면 된다.
즉, 1에는 2와 3이 직접 연결되어 있기 때문에 배열의 1번째 칸에 2와 3을 넣어준다.
인접리스트의 장점
정점들의 연결 정보를 탐색할 때 O(n) 시간이면 가능하다.
필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다.
인접리스트의 단점
특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다. (O(E) 시간 소요. E는 간선의 개수)
구현이 비교적 어렵다.
인접리스트 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 100
typedef struct GraphType
{
int vertex;
struct GraphType* link;
}GraphType;
typedef struct graphType //n과 adjList_H를 갖고있는 구조체
{
int n;
GraphType* adjList_H[MAX_VERTEX];
}graphType;
void createGraph(graphType* g) //그래프 생성 n이 의미하는것이 vertex
{
int v;
g->n = 0;
for (v = 0; v < MAX_VERTEX; v++)
{
g->adjList_H[v] = NULL;
}
}
void insertVertex(graphType* g, int v)
{
if ((g->n) + 1 > MAX_VERTEX)
{
printf("\n 그래프 정점의 개수를 초과하였습니다.");
return;
}
g->n++;
}
void insertEdge(graphType* g, int u, int v)
{
GraphType* node;
if (u >= g->n || v >= g->n)
{
printf("\n 그래프에 없는 정점입니다.\n");
return;
}
node = (GraphType*)malloc(sizeof(GraphType));
node->vertex = v;
node->link = g->adjList_H[u];
g->adjList_H[u] = node;
}
void printAdjMatrix(graphType* g)
{
int i;
GraphType* p;
for (int i = 0; i < g->n; i++)
{
printf("\n\t\t 정점 %C의 인접 리스트 ", i + 65);
p = g->adjList_H[i];
}
while (p)
{
printf(" -> %c", p->vertex + 65); //정점 0~4를 A~D로 출력한다.
p = p->link;
}
}
int main()
{
int i;
graphType* G1, *G2;
G1 = (graphType*)malloc(sizeof(graphType));
G2 = (graphType*)malloc(sizeof(graphType));
createGraph(G1);
for (i = 0; i < 4; i++)
{
insertVertex(G1, i);
}
insertEdge(G1, 0, 1);
insertEdge(G1, 0, 2);
insertEdge(G1, 0, 3);
insertEdge(G1, 1, 0);
insertEdge(G1, 1, 2);
insertEdge(G1, 2, 0);
insertEdge(G1, 2, 1);
insertEdge(G1, 2, 3);
insertEdge(G1, 3, 2);
insertEdge(G1, 3, 0);
insertEdge(G1, 3, 3);
printf("\n G1의 인접리스트 ");
printAdjMatrix(G1);
createGraph(G2);
for (i = 0; i < 4; i++)
{
insertVertex(G2, i);
}
insertEdge(G2, 0, 1);
insertEdge(G2, 0, 3);
insertEdge(G2, 2, 3);
insertEdge(G2, 3, 1);
printf("\n\n G2의 인접 리스트 ");
printAdjMatrix(G2);
getchar();
}