그래프 - 표현방법(인접행렬/인접리스트)

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

1. 인접행렬 adjacency matrix

# 개념, 특징

1) 2차원 배열 사용

 

2) 자체 간선 허용 X ==> 대각선 성분 = 0

 

3) 정점 i, j 에 대해 간선 (i,j) or <i,j>가 존재하면

- 무방향 그래프: Matrix[i][j] = Matrix[j][i] = 1 

- 방향 그래프: Matrix[i][j] = 1

 

4) 2차원 배열은 

- 무방향 그래프: 대칭 행렬 ==> 배열의 상위 삼각/하위 삼각만 저장하면 메모리 절약 가능

- 방향 그래프: 비대칭 행렬

 

5) 정점의 개수 = n 인 경우

간선의 개수와 무관, n*n개의 메모리 공간이 필요함

==> 밀집 그래프 표현에 적합 (메모리 낭비가 희소 그래프에 비해 덜함)

*밀집그래프 densed graph 간선의 개수가 많은 그래프

*희소그래프 sparse graph  간선의 개수가 적은 그래프

 

6) 시간 복잡도 (정점의 개수 = n)

- 간선의 존재 여부 = O(1)

- 정점의 차수 = O(n)

- 모든 간선의 개수 = O(n^2)

 

# c언어로 구현

#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; //정점의 개수는 0으로 초기화
	for (r = 0; r < MAX_VERTICES; r++) // 인접행렬의 모든 원소들 0으로 초기화
	{
		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, "그래프: 정점의 개수 초과\n");
		return;
	}
	g->n++; // 정점을 삽입하는 것은 실질적으로 행렬에 영향을 주지 않음
	// 그저 정점의 개수만 증가시켜 주면 된다.
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류\n");
		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");
	}
}
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);
}

# 결과

2. 인접리스트 adjacency list

# 개념, 특징

1) 연결 리스트(포인터) 사용

 

2) 구성

노드 + 포인터

= 정점 + 간선

*포인터: 인접 정점을 가리킨다

 

3) 정점 i, j에 대한 간선 (i,j) or <i,j>가 존재하면

정점 i의 연결 리스트에 추가된다. 

[그림1]&amp;amp;amp;nbsp;

[그림2]. [그림1]을 연결 리스트로 표현한다.

만약 위의 그래프가 무방향 그래프였다면,

간선 (1,2)는 노드 1과 2에 모두 추가된다.

 

이때 헤더노드는, [그림2]에서 0~3 인덱스를 갖고 있는 1차원 배열을 두고 하는 말이다. 

 

4) 정점의 개수 = n/ 간선의 개수 = e

- 무방향 그래프 ==> n개의 연결 리스트 필요 = n개의 헤더 노드 + 2e개의 노드 필요

 

5) 희소 그래프 표현에 적합함 (간선의 개수가 적기 때문)

 

6) 시간 복잡도 (정점 개수 = n, 간선의 개수 = e)

- 간선(i,j)의 존재 여부 = 정점 i의 차수 = (정점 i의 연결리스트를 탐색) = (정점차수만큼의 시간 필요)

- 전체 간선의 개수 = O(n+e)

 

# c언어로 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICE 50

// 각 정점마다 하나의 연결리스트가 필요하다
// 정점의 개수만큼의 포인터 배열(헤더노드)이 필요하다
// 하나의 노드 ==> GraphNode
// 포인터 배열의 이름 ==> adj_list
typedef struct GraphNode {
	int vertex; // 정점의 값을 저장할 곳
	struct GraphNode* link;  // 인접정점을 가리킬 포인터 
	// 가리킬 변수의 타입이 하나의 정점이기 때문에 GraphNode 타입으로 선언해야 한다.
} GraphNode;

typedef struct GraphType {
	int n;	// 해당 그래프의 정점의 개수
	GraphNode* adj_list[MAX_VERTICE]; // 정점들을 관리할 리스트; 헤더노드 집합
} GraphType;

// 그래프 초기화
void init_adjList(GraphType* g) {
	int v;
	g->n = 0; //그래프 정점의 개수 0으로 초기화
	for (v = 0; v < MAX_VERTICE; v++) {
		g->adj_list[v] = NULL;
	}
}
// 정점 삽입 연산: 값이 v인 정점을 삽입한다.
void insert_vertex_adjList(GraphType* g, int v) { // v: 삽입합 노드의 값
	if ((g->n) + 1 > MAX_VERTICE) {
		fprintf(stderr, "그래프: 정점의 개수 초과\n");
		return;
	}
	g->n++;
}
// 간선 삽입 연산: 정점 u와 v를 연결한다 : 정점 u에 간선 (u,v)를 맨 처음에 삽입
void insert_edge_adjList(GraphType* g, int u, int v) {
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류\n");
		return;
	}
	GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;	// adj_list의 한 원소는 GraphNode를 가리키는 포인터 타입이니까 할당 가능
}
// 그래프 출력 연산
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");
	}
}
void main()
{
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));

	init_adjList(g);

	for (int i = 0; i < 4; i++) {
		insert_vertex_adjList(g, i);
	}
	insert_edge_adjList(g, 0, 1);
	insert_edge_adjList(g, 1, 0);
	insert_edge_adjList(g, 0, 2);
	insert_edge_adjList(g, 2, 0);
	insert_edge_adjList(g, 0, 3);
	insert_edge_adjList(g, 3, 0);
	insert_edge_adjList(g, 1, 2);
	insert_edge_adjList(g, 2, 1);
	insert_edge_adjList(g, 2, 3);
	insert_edge_adjList(g, 3, 2);
	print_adj_list(g);
	free(g);
}

#결과