[C] 그래프를 표현하는 방법

C 로 그래프를 구현하는 중에 이해를 못하는 상황이 발생했다. 파이썬은 딕셔너리 구조를 이용해서 정말 쉽게 구현했고, 메모리 관리를 따로 안 해줘도 되니까 구조 자체에만 집중할 수 있었다. 

 

온라인 강의를 보면서 굉장히 비효율적인 공부를 하다가, 혼자 그래프를 그려보고 직접 생각하면서 이를 코드로 구현하는 게 역시나 정석인 것 같다고 판단했다.

 

결론: 노트에 구조를 그려보고, 여기에 맞춰서 코드를 짜는 게 오래 남는다.

 

---

코드로 그래프를 구현한다는 것은 사람이 눈으로 인식하는 것과는 차이가 있다.

 

 

 

출처: https://en.wikipedia.org/wiki/Graph_theory

 

그래프 구조의 특징은 노드가 가지는 숫자가 노드의 개수보다 크지 않고, 중간에 비는 숫자가 없다. (만약 노드가 갖는 숫자가 1부터 순차적인 숫자가 아니라 중간에 훅 건너 뛰는 경우는 배열의 크기를 늘리는 방법을 사용할 수 있다.)

 

그래프를 양방향이라고 가정하고 코드를 구현하면

 

노드[1] 2, 5

노드[2] 1, 3, 5

노드[3] 2, 4, 5

노드[4] 3 5 6

노드[5] 1 2 4

노드[6] 4

 

이런식으로 표현할 수 있다. 양방향으로 만들면 dfs, bfs를 구현하기에도 편할 것 같다.

 

C로 위와 같은 구조를 만들려면 어떻게 해야할까? 가장 직관적인 구조는 우선 배열을 만들고 그 배열의 인덱스에 루트 노드를 저장하고, 루트 노드부터 링크드 리스트 형태로 뻗어나가게 저장하는 것 같다. (2차원 배열로도 구현할 수 있겠다. 이것도 구현해봐야한다.)

 

우선 사용한 방법은 배열안에 링크드리스트를 활용한 경우다.

아래 방법은 배열의 각 인덱스를 Node 구조체로 할당한다. 단 값을 주진 않고 단순히 Root 로 활용하는 방법이다. 

 

[0] [1] [2] ... [n]

↓  　↓

값    값

↓  　↓

값    값

↓

값

 

이런식으로 배열을 동적할당하고 인덱스를 루트 노드로 삼아 링크드리스트 구조로 연결한다. 이렇게 구현하면 BFS, DFS를 구현할때 스택, 큐에 쉽게 적용할 수 있다. 

---

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

typedef struct {
	int data;
	struct Node* next;
} Node;

void addNode(Node* root, int data) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = root->next;
	root->next = node;
}

void showAll(Node* root) {
	Node* cur = root->next;
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

int main(void) {
	int n, line;
	scanf("%d %d", &n, &line);
	Node** array = (Node**)malloc(sizeof(Node*) * (n+1));
	for (int i = 1; i <= n; i++) {
		array[i] = (Node*)malloc(sizeof(Node));
		array[i]->next = NULL;
	}
	for (int i = 0; i < line; i++) {
		int root, new;
		scanf("%d %d", &root, &new);
		addNode(array[root], new);
        addNode(array[new], root);
	}
	for (int i = 1; i <= n; i++) {
		printf("Node[%d]: ", i);
		showAll(array[i]);
		printf("\n");
	}
	return 0;
}