[C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트

[C 자료구조] 그래프(Graph)의 종류 : 인접 행렬(Adjacent matrix) vs 인접 리스트(Adjacent list)

위 포스팅에서 그래프의 정의와 그래프의 종류, 그리고 인접행렬, 인접리스트로 그래프를 나타내는 방법까지 배웠습니다.

 

자료구조에서의 그래프 정의는 객체 사이의 연결 관계를 표현할 수 있는 자료구조 입니다. 따라서 추상자료형으로 Graph 를 정의하고 사용할 수 있습니다. 그래프를 ADT 로 정의해보면 다음과 같습니다.

∙객체: 정점의 집합과 간선의 집합
∙연산:  
 ▪ create_graph() ::=	그래프를 생성한다.
 ▪ init(g) ::= 그래프 g를 초기화한다.
 ▪ insert_vertex(g,v) ::= 그래프 g에 정점 v를 삽입한다.
 ▪ insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v)를 삽입한다. 
 ▪ delete_vertex(g,v) ::= 그래프 g의 정점 v를 삭제한다.
 ▪ delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v)를 삭제한다. 
 ▪ is_empty(g) ::= 그래프 g가 공백 상태인지 확인한다. 
 ▪ adjacent(v) ::= 정점 v에 인접한 정점들의 리스트를 반환한다. 
 ▪ destroy_graph(g) ::=	그래프 g를 제거한다.

정의했던 대로 정점과 간선의 집합이 필요하고, 이것이 정의 될 때 인접행렬과 인접 리스트 방식이 있는 겁니다.

그에 따라 아래의 연산들을 추가적으로 정의해주면 그래프 추상 데이터 타입이 됩니다. 이번 포스팅은 인접행렬과 인접리스트 방법으로 위의 그래프 ADT 를 구현해보는 포스팅입니다. 이 중에서 간선과 정점 삽입 연산까지만 구현해볼 겁니다.

 

 인접행렬 구현

 

그래프 정의 / 초기화 init()

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 20
typedef struct Graph {
	int n; // 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
}graph;

// 그래프 초기화
void init(Graph* g)
{
	int row, col;
	g->n = 0;
	for (row = 0; row < MAX_VERTICES; row++)
		for (col = 0; col < MAX_VERTICES; col++)
			g->adj_mat[row][col] = 0;
}

Graph 구조체 안에는 인접 행렬을 나타낼 2차원 배열과 정점의 개수를 저장할 변수를 선언합니다. 그 이후 초기화를 진행하는데 당연히 아직은 정점을 따로 삽입하지 않았기 때문에 n = 0 으로 초기화합니다. 또한 간선도 없으니까 배열을 모두 0으로 초기화 시켜 줍니다.

 

정점 삽입 연산 : insert_vertex()

void insert_vertex(Graph* g, int vertex)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "최대 정점 개수 초과\n");
		return;
	}
	g->n++;
}

정점을 삽입하는 연산은 단순히 n을 하나 증가하면 됩니다. 이 때 정점의 번호는 순차적으로 증가한다고 가정했기 때문에 이렇게 설정할 수 있는 겁니다. 최대 크기로 배열은 선언되어 있고 정점 0, 정점 1, 정점 2 ... 순으로 정점을 삽입하는 것으로 생각하시면 됩니다.

 

간선 삽입 연산 : insert_vertex()

void insert_edge(Graph* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "정점 번호 오류\n");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}

인접 행렬에서는 간선은 배열의 값으로 구분됩니다. 간선이 존재할 경우 1, 간선이 존재하지 않을 경우 0 입니다. 따라서 간선을 추가하는 연산은 어떤 정점 2개를 연결할 것인지 2개의 정점을 입력으로 받아서 2개의 그래프를 연결해주면 됩니다. 이번 구현은 무방향 그래프이기 때문에 mat[start][end] 와 mat[end][start] 를 모두 1로 만들어줘 양방향의 간선을 만들어줍니다.

 

전체 코드 및 실행 결과

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 20
typedef struct Graph {
	int n; // 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
}graph;

// 그래프 초기화
void init(Graph* g)
{
	int row, col;
	g->n = 0;
	for (row = 0; row < MAX_VERTICES; row++)
		for (col = 0; col < MAX_VERTICES; col++)
			g->adj_mat[row][col] = 0;
}
// 정점 삽입 연산
void insert_vertex(Graph* g, int vertex)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "최대 정점 개수 초과\n");
		return;
	}
	g->n++;
}
// 간선 삽입 연산
void insert_edge(Graph* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "정점 번호 오류\n");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}
// 인접 행렬 출력 함수
void print_graph(Graph* g)
{
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			printf("[%d] ", g->adj_mat[i][j]);
		}
		printf("\n");
	}
}

void main()
{
	graph* g;
	g = (graph*)malloc(sizeof(graph));
	init(g);
	for (int i = 0; i < 4; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 0, 3);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 3);
	print_graph(g);

	free(g);
}

간선 삽입과 정점 삽입 연산만 구현한 아주 간단한 그래프 형태의 자료구조입니다. print_graph 함수는 정점까지의 행렬들을 출력해주는 함수입니다. 왼쪽의 인접 행렬은 오른쪽의 그래프를 나타내는 인접 행렬입니다. (0, 1) (0, 2) (0, 3) (1, 2) (2 3) 연결이 행렬에 그대로 나타나 있는 것을 확인할 수 있습니다.

 

 

 인접리스트 구현

 

인접리스트 방법으로 위 그래프를 구현해보겠습니다. 마찬가지로 정점 삽입, 간선 삽입만 간단히 구현하여 위와 같은 결과를 뽑아내는 코드를 보겠습니다.

그래프 정의 / 초기화 init()

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 20
typedef struct GraphNode {
	int vertex;
	struct GraphNode* next;
}graphnode;

typedef struct Graph {
	int n; // 정점의 개수
	GraphNode* adj_list[MAX_VERTICES];
}graph;

void init(graph* g)
{
	g->n = 0;
	for (int v = 0; v < MAX_VERTICES; v++)
		g->adj_list[v] = NULL;
}

인접리스트 방식으로 그래프를 구현하려면 당연히 연결리스트 노드를 정의해야 합니다. 그리고 그래프 구조체 내에 2차원 배열 대신 그래프의 포인터 배열이 들어가게 됩니다. 포인터 배열에는 각 정점에서 시작되는 포인터가 들어가게 됩니다. 예를 들어 adj_list[0] 에는 0번 부터 시작해서 1,2,3 ... 의 연결을 표현해야 하는 리스트가 들어가게 될텐데 그 때의 head 포인터 역할을 하는 것이 배열에 저장됩니다.

 

adj_list[0] 은 정점 0의 인접 리스트, adj_list[1]은 정점 1의 연결리스트 ... 를 나타냅니다. 그리고 정점의 개수를 나타내는 n 변수가 있는데 이 변수를 통해 정점 접근(포인터 배열 인덱스 접근) 을 해서 삽입/출력을 하게 될 겁니다.

 

초기화는 인접 행렬방식과 유사하게 맨 처음 정점의 개수는 0개이므로 n 을 0으로 초기화 시켜주고, 각 배열의 head 포인터를 NULL 포인터로 초기화 해줍니다. 그리고 만약 간선이 추가된다면 이 포인터들이 새로운 노드를 가리키게 됩니다.

 

정점 삽입 연산 : insert_vertex()

void insert_vertex(graph* g, int v)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "최대 정점 개수 초과\n");
		return;
	}
	g->n++;
}

정점 삽입 연산은 인접 행렬로 구현할 때와 완전히 동일합니다. 인접 행렬로 구현할 때 배열의 인덱스 조합이 간선을 결정했기 때문에 정점이 몇개인지를 나타내는 n을 1 증가시키기만 하면 정점 추가 연산이 끝났습니다. 인접 리스트도 간선의 표현 방식이 변화했을 뿐이라 인접 행렬과 동일합니다.

 

간선 삽입 연산 : insert_vertex()

void insert_edge(graph* g, int u, int v) 
{
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "정점 번호 오류\n");
		return;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->next = g->adj_list[u];
	g->adj_list[u] = node;
}

간선 삽입 연산은 인접 행렬과 인접 리스트가 많이 다릅니다. 

간선 삽입 함수가 호출되면 뒤에 붙이는 것이 아니라 위처럼 중간에 노드를 삽입합니다. 간선을 삽입한다는 것은 새로운 노드를 만들어야 하는 것이기 때문에 메모리 할당을 받은 이후 노드에 값 대입, 그리고 새로 할당 받은 노드의 포인터를 adj_list 배열의 head 포인터가 가리키는 노드, 즉 첫번째 노드를 가리키게 합니다. 위 사진은 조금 예시가 다른데 과정은 동일하니 이해용으로만 참고해주시면 됩니다.

먼저 새로 할당한 노드의 포인터를 설정하고, 그 다음에 head 포인터를 새로 할당한 노드를 가리키게 해야 오류가 발생하지 않습니다. 만약 이 순서를 반대로 한다면 새로 할당받은 노드의 포인터로 원래 있던 노드를 가리킬 수 없기 때문에 연결 리스트에서의 중간 노드 삽입은 순서를 꼭 지켜서 수행되어야 합니다.

 

전체 코드 및 실행 결과

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 20
typedef struct GraphNode {
	int vertex;
	struct GraphNode* next;
}graphnode;

typedef struct Graph {
	int n; // 정점의 개수
	GraphNode* adj_list[MAX_VERTICES];
}graph;

// 그래프 초기화
void init(graph* g)
{
	g->n = 0;
	for (int v = 0; v < MAX_VERTICES; v++)
		g->adj_list[v] = NULL;
}

// 정점 삽입 연산
void insert_vertex(graph* g, int v)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "최대 정점 개수 초과\n");
		return;
	}
	g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입
void insert_edge(graph* g, int u, int v) 
{
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "정점 번호 오류\n");
		return;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->next = g->adj_list[u];
	g->adj_list[u] = node;
}

void print_adj_list(graph* g)
{
	for (int i = 0; i < g->n; i++)
	{
		GraphNode* ptr = g->adj_list[i];
		printf("정점 %d의 인접 리스트 ", i);
		while (ptr != NULL) {
			printf("-> %d ", ptr->vertex);
			ptr = ptr->next;
		}
		printf("\n");
	}
}

int main()
{
	Graph* g;
	g = (Graph*)malloc(sizeof(Graph));
	init(g);
	for (int i = 0; i < 4; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 3);
	insert_edge(g, 3, 0);
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 0);
	insert_edge(g, 0, 1);
	insert_edge(g, 1, 0);
	insert_edge(g, 3, 2);	
	insert_edge(g, 2, 3);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 1);
	print_adj_list(g);
	free(g);
	return 0;
}

 

이로써 처음 만들고자 했던 그래프의 연결리스트 구현을 마쳤습니다. 인접 행렬과 인접 리스트 구현 방식은 비슷한 부분이 많기 때문에 어느 부분이 다른가를 중점으로 보시면 둘 다 금방 이해하고 다룰 수 있습니다. 감사합니다. 

 

 

 

 

참고 : C언어로 쉽게 풀어쓴 자료구조 - 생능출판