[Data Structure] 그래프 표현 방법 2) 인접 리스트

그래프의 표현방법

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

---

인접 리스트

- 각 연결 리스트들의 노드는 인접 정점들을 저장

- 각 연결 리스트들은 헤더 노드를 보유 → 헤더 노드는 배열로 구성 → 배열의 인덱스를 이용해서 각 정점의 연결 리스트에 접근

---

그래프 인접리스트 구현 

#define MAX_VERTEX 50

typedef struct graphnode {
	int vertex; // 각 노드의 정점
	struct graphnode* link; // 정점들간에 연결해주는 link
}graphnode;

typedef struct graph {
	int n; // 정점의 개수
	graphnode* list[MAX_VERTEX]; // 하나의 연결리스트 안에 존재하는 정점들의 배열
}graph;

 

Example) 위의 그림을 예제로

- graphnode : (1, link), (2, link), (3, link), (4, link), (5, link) 존재

- graph (graphnode* list[MAX_VERTEX]) : 위의 예제의 연결리스트 5개를 각각 하나로 인식하고 배열에 추가

• list[0] : 1→2→3→4→5→NULL
• list[1] : 2→1→3→5→NULL
• list[2] : 3→1→2→NULL
• list[3] : 4→1→5→NULL
• list[4] : 5→1→2→4→NULL

 

1. 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;
	}
	graphnode* new_node = (graphnode*)malloc(sizeof(graphnode));
	new_node->vertex = v; new_node->link = NULL;
	g->list[g->n++] = new_node;
}

1. vertex를 insert하는 연산 = graph의 list포인터 배열에 vertex를 insert
2. new_node 동적 할당 → new_node의 vertex, link(NULL)에 정보를 insert하고 배열에 new_node를 그대로 추가

 

 

2. Edge 삽입 연산

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

void insert_edge(graph* g, int start, int end) {
	if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) {
		fprintf(stderr, "그래프에 해당 정점은 없습니다\n\n");
		return;
	}
	graphnode* new_node = (graphnode*)malloc(sizeof(graphnode));
	new_node->vertex = end;
	new_node->link = g->list[start]->link;
	g->list[start]->link = new_node;
}

1. 편의상으로 edge를 insert할 때, 인접 리스트 맨 처음에 추가
2. 그러면 new_node의 link는 원래 해당 리스트의 정점이 가리키던 노드를 가리켜야 한다
3. 그리고 해당 리스트의 정점은 new_node를 가리켜야 한다

 

 

3. Full Code

#include <stdio.h>
#include <stdlib.h>
// 인접 리스트 (무방향 그래프)

#define MAX_VERTEX 50

typedef struct graphnode {
	int vertex; // 각 노드의 정점
	struct graphnode* link; // 정점들간에 연결해주는 link
}graphnode;

typedef struct graph {
	int n; // 정점의 개수
	graphnode* list[MAX_VERTEX]; // 하나의 연결리스트 안에 존재하는 정점들의 배열
}graph;

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

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

void init_graph(graph* g) {
	g->n = 0;
	for (int i = 0; i < MAX_VERTEX; i++)
		g->list[i] = NULL;
}

int bool_vertex(graph* g, int v) {
	// 그래프에 정점 v가 존재하는지 판별
	int flag = 1;
	for (int i = 0; i < g->n; i++) {
		if (g->list[i]->vertex == v)
			flag = 0;
	}
	if (flag == 0) return 0; // 존재 O
	else return 1; // 존재 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;
	}
	graphnode* new_node = (graphnode*)malloc(sizeof(graphnode));
	new_node->vertex = v; new_node->link = NULL;
	g->list[g->n++] = new_node;
}

void insert_edge(graph* g, int start, int end) {
	if (bool_vertex(g, start) == 1 || bool_vertex(g, end) == 1) {
		fprintf(stderr, "그래프에 해당 정점은 없습니다\n\n");
		return;
	}
	graphnode* new_node = (graphnode*)malloc(sizeof(graphnode));
	new_node->vertex = end;
	new_node->link = g->list[start]->link;
	g->list[start]->link = new_node;
}

void print_list(graph* g) {
	graphnode* p;
	for (int i = 0; i < g->n; i++) {
		graphnode* p = g->list[i];
		printf("정점 %d의 인접 리스트 : V", i);
		while (p != NULL) {
			printf("%d -> ", p->vertex);
			p = p->link;
		}
		printf(" NULL\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, 1, 0);
	insert_edge(g1, 0, 2);
	insert_edge(g1, 2, 0);
	insert_edge(g1, 0, 3);
	insert_edge(g1, 3, 0);
	insert_edge(g1, 1, 2);
	insert_edge(g1, 2, 1);
	insert_edge(g1, 2, 3);
	insert_edge(g1, 3, 2);

	print_list(g1);

	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, 1, 0);
	insert_edge(g2, 0, 2);
	insert_edge(g2, 2, 0);
	insert_edge(g2, 0, 3);
	insert_edge(g2, 3, 0);
	insert_edge(g2, 1, 2);
	insert_edge(g2, 2, 1);
	insert_edge(g2, 1, 4);
	insert_edge(g2, 4, 1);
	insert_edge(g2, 2, 3);
	insert_edge(g2, 3, 2);
	insert_edge(g2, 3, 4);
	insert_edge(g2, 4, 3);

	print_list(g2);

	free(g1); free(g2);

	return 0;
}