[자료구조] 그래프(Graph) 구현하기

그래프 개념

2021.12.21 - [📚 자료구조 및 알고리즘/그래프] - 그래프(Graph)란?

그래프(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를 제거한다.

---

 

 

그래프의 표현 방법 2가지

1. 인접행렬 (adjacent matrix) 방법

if(간선 (i, j)가 그래프에 존재)    M[i][j] = 1, 그렇지않으면 M[i][j] = 0

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

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

// 그래프 초기화
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;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
// 간선 삽입 연산
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;
}
//인접 행렬 출력 함수
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");
    }
}
int main(void)
{
    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);
    return 0;
}

2. 인접 리스트(adjacent list) 방법

각 정점에 인접한 정점들을 연결리스트로 표현

#include <stdio.h>
#pragma warning(disable:4996)
#define MAX_VERTICES 50
typedef struct GraphNode {
	int vertex;
	struct GraphNode* link;
}GraphNode;
typedef struct GraphType {
	int n;
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;
//그래프 초기화
void init(GraphType* g) {
	int v;
	g->n = 0;
	for (v = 0; v < MAX_VERTICES; v++) {
		g->adj_list[v] = NULL;
	}
}
//정점 삽입 연산
void insert_vertex(GraphType* g, int v) {
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}
//간선 삽입 연산, v를 u의 인접 리스트에 삽입
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;
}
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");
	}
}
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);
}