[Data Structure] 그래프 표현 방법 1) 인접 행렬

그래프의 표현방법

• 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용
• 인접 리스트(Adjacency List) : 연결 리스트를 사용

---

인접 행렬

- 정점의 수 n개에 대해 n×n의 2차원 배열로 구성

- 간선 (i, j)가 그래프에 존재하면 m[i][j] = 1

- 간선 (i, j)가 그래프에 없으면 m[i][j] = 0

- n개의 정점이 존재하면 n²개의 메모리가 필요

• → 메모리 낭비가 크다

- 간선이 매우 많은 밀집 그래프에는 적합하다

- 간선이 적은 희소 그래프의 경우에는 메모리 낭비가 크므로 적합하지 않다

• 무방향 그래프 = 행렬이 대칭으로 구성

---

그래프 인접행렬 구현

#define MAX_VERTEX 50

typedef struct graph {
	int n; // 정점의 개수 count(vertex)
	int vertex[MAX_VERTEX]; // 정점 저장 배열
	int matrix[MAX_VERTEX][MAX_VERTEX]; // 인접 행렬 (2차원 배열)
}graph;

 

 

1. Vertex 삽입 연산

• 정점의 개수가 MAX_VERTEX에 도달하면 더 이상 INSERT X

void insert_vertex(graph* g, int v) {
	if (is_full(g)) {
		fprintf(stderr, "그래프 정점의 개수가 MAX에 도달하였습니다\n\n");
		return;
	}
	else if (bool_vertex(g, v) == 0) {
		fprintf(stderr, "해당 정점은 이미 그래프에 존재합니다.\n\n");
		return;
	}
	g->vertex[g->n++] = v;
}

 

 

2. Edge 삽입 연산

• 무방향 그래프에서는 대칭적으로 start-end / end-start에 1을 삽입
• 방향 그래프에서는 해당 방향만 1 삽입

int bool_vertex(graph* g, int v) {
	// 그래프에 정점 v가 존재하는지 판별
	int flag = 1;
	for (int i = 0; i < MAX_VERTEX; i++) {
		if (g->vertex[i] == v)
			flag = 0; // 존재 O
	}
	if (flag == 0) return 0; // 존재 O
	else return 1; // 존재 X
}

void insert_edge(graph* g, int start, int end) { // start - end를 연결하는 edge 생성
	if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) {
		fprintf(stderr, "그래프에 해당 정점은 없습니다\n\n");
		return;
	}
	g->matrix[start][end] = 1;
	g->matrix[end][start] = 1;
	// 무방향 그래프이기 때문에 대칭적으로 1 삽입
}

 

 

3. Edge 삭제 연산

void delete_edge(graph* g, int start, int end) { // start - end 연결하는 edge 삭제
	if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) {
		fprintf(stderr, "그래프에 해당 정점은 없습니다\n\n");
		return;
	}
	g->matrix[start][end] = 0;
	g->matrix[end][start] = 0;
}

 

 

4. Full Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 인접 행렬 (무방향 그래프)

#define MAX_VERTEX 50

typedef struct graph {
	int n; // 정점의 개수 count(vertex)
	int vertex[MAX_VERTEX]; // 정점 저장 배열
	int matrix[MAX_VERTEX][MAX_VERTEX]; // 인접 행렬 (2차원 배열)
}graph;

graph* create() { // 그래프 동적 할당
	return (graph*)malloc(sizeof(graph));
}

void init_graph(graph* g) { // 그래프 초기화
	int r, c; // row, col
	g->n = 0; // 정점의 개수 0으로 초기화
	for (r = 0; r < MAX_VERTEX; r++) {
		for (c = 0; c < MAX_VERTEX; c++) {
			g->matrix[r][c] = 0; // 2차원 배열 전부 0으로 초기화
		}
	}
}

int bool_vertex(graph* g, int v) {
	// 그래프에 정점 v가 존재하는지 판별
	int flag = 1;
	for (int i = 0; i < MAX_VERTEX; i++) {
		if (g->vertex[i] == v)
			flag = 0; // 존재 O
	}
	if (flag == 0) return 0; // 존재 O
	else return 1; // 존재 X
}

int is_full(graph* g) {
	return g->n == MAX_VERTEX;
}

void insert_vertex(graph* g, int v) {
	if (is_full(g)) {
		fprintf(stderr, "그래프 정점의 개수가 MAX에 도달하였습니다\n\n");
		return;
	}
	else if (bool_vertex(g, v) == 0) {
		fprintf(stderr, "해당 정점은 이미 그래프에 존재합니다.\n\n");
		return;
	}
	g->vertex[g->n++] = v;
}

void insert_edge(graph* g, int start, int end) { // start - end를 연결하는 edge 생성
	if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) {
		fprintf(stderr, "그래프에 해당 정점은 없습니다\n\n");
		return;
	}
	g->matrix[start][end] = 1;
	g->matrix[end][start] = 1;
	// 무방향 그래프이기 때문에 대칭적으로 1 삽입
}

void delete_edge(graph* g, int start, int end) { // start - end 연결하는 edge 삭제
	if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) {
		fprintf(stderr, "그래프에 해당 정점은 없습니다\n\n");
		return;
	}
	g->matrix[start][end] = 0;
	g->matrix[end][start] = 0;
}

void print_matrix(graph* g) {
	for (int i = 0; i < g->n; i++) {
		printf("%d |", g->vertex[i]);
		for (int j = 0; j < g->n; j++) {
			printf("%2d", g->matrix[i][j]);
		}
		printf("\n");
	}
}

int main(void) {
	graph* g1, *g2;
	g1 = create();
	g2 = create();
	init_graph(g1);
	init_graph(g2);

	printf("V : {0, 1, 2, 3}\n");
	printf("E : {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)\n\n");
	for (int i = 0; i < 4; i++)
		insert_vertex(g1, i);
	insert_edge(g1, 0, 1);
	insert_edge(g1, 0, 2);
	insert_edge(g1, 0, 3);
	insert_edge(g1, 1, 2);
	insert_edge(g1, 2, 3);

	// print
	printf("   ");
	for (int i = 0; i < g1->n; i++)
		printf("%2d", i);
	printf("\n   ");
	for (int i = 0; i < g1->n; i++)
		printf("--");
	printf("\n");
	print_matrix(g1);
	// print

	printf("----------------------------\n");
	printf("V : {0, 1, 2, 3, 4}\n");
	printf("E : {(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)\n\n");
	for (int i = 0; i < 5; i++)
		insert_vertex(g2, i);
	insert_edge(g2, 0, 1);
	insert_edge(g2, 0, 2);
	insert_edge(g2, 0, 3);
	insert_edge(g2, 1, 2);
	insert_edge(g2, 1, 4);
	insert_edge(g2, 2, 3);
	insert_edge(g2, 3, 4);

	// print
	printf("   ");
	for (int i = 0; i < g2->n; i++)
		printf("%2d", i);
	printf("\n   ");
	for (int i = 0; i < g2->n; i++)
		printf("--");
	printf("\n");
	print_matrix(g2);
	// print

	return 0;
}