C언어 행렬과 연결리스트로 그래프 구현하기

matrix로 그래프 구현하기

행 정점에서 열 정점(vertext)으로 가는 길(edge)이 있다면 1로, 없다면 0으로 구현하려고 한다.
무방향 그래프라면 행렬이 대칭으로 나타날 것이다.
그래프는 구조체로 선언하고 내부에 정점의 개수와 2차원 배열을 멤버 변수로 선언할 것이다.

typedef struct GraphType {
	int n;	// 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

필요한 함수

1. init
2. insert_vertex
3. insert_edge
4. print_adj_mat

함수 설명

1) init

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

이중 반복으로 행렬을 0으로 채웠다.

2) insert_vertex

// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

정수 v 정점을 받고 GraphType 구조체의 정점 개수 n을 증가시켜 준다.

3) insert_edge

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

 

4) print_adj_mat

void print_adj_mat(GraphType* g)
{
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			printf("%2d ", g->adj_mat[i][j]);
		}
		printf("\n");
	}
}

5) main 함수

void main()
{
	GraphType *g;
	g = (GraphType *)malloc(sizeof(GraphType));
	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_adj_mat(g);

	free(g);
}

GraphType 구조체를 포인터형으로 선언하고 메모리를 할당했다.
insert_vertex 함수를 이용해 0에서 4까지 정점을 만든다.
그리고 insert_edge 함수로 정점 사이에 간선(edge)을 만들어준다.
마지막으로 출력함수를 이용해 2차원 배열을 출력한다.

---

연결리스트로 그래프 구현하기

GraphNode 구조체와 GraphType 구조체를 선언할 것이다.
GraphType 에는 정점의 개수 n과 GraphNode 포인터형의 리스트가 있다.

typedef struct GraphNode{
	int vertex;
	struct GraphNode* link;
} GraphNode;

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

GraphType에 있는 n은 정점의 개수를 가리키고, adj_list는 그래프노드를 가리킬 것이다.

필요한 함수

1. init
2. insert_vertex
3. insert_edge
4. print_adj_list

함수 설명

1) init

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

정점의 개수 n을 0으로 업데이트 한 뒤 adj_list 배열의 값을 전부 NULL로 바꾸었다.

2) insert_vertex

void insert_vertex(GraphType* g, int v)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

정수 v 정점을 받고 GraphType 구조체의 정점 개수 n을 증가시켜 준다.

3) insert_edge

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

새로운 노드를 만들고 메모리를 할당한 뒤 adj_list가 node를 가리키도록 한다. 즉 배열 바로 뒤에 노드를 추가하는 것이다.

4) print_adj_list

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

adj_list를 순회하며 NULL이 아닐때까지 돌아가며 출력한다.

5) main 함수

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

GraphType 구조체를 포인터형으로 선언하고 메모리를 할당했다.
insert_vertex 함수를 이용해 0에서 4까지 정점을 만든다.
그리고 insert_edge 함수로 정점 사이에 간선(edge)을 만들어준다.
마지막으로 출력함수를 이용해 연결리스트로 구성된 그래프를 출력한다.