[자료구조] 그래프(Graph) 개념, 구현

그래프

 

 

그래프의 개념

 

객체 사이의 연결 관계를 표현할 수 있는 자료구조

정점(vertex)과 간선(edge)으로 이루어진 자료구조

 

 

그래프와 관련된 용어

 

• 정점(vertex): 노드(node)라고도 불리며, 여러가지 특성을 가질 수 있는 객체
• 간선(edge): 링크(link)라고도 불리며, 정점을 연결하는 선
• 인접 정점(adjecent vertex): 간선에 의해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수
• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경로

 

그래프 종류

 

무방향 그래프(Undirected Graph)

두 정점을 연결하는 간선에 방향이 없는 그래프

정점 A와 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)와 (B, A)는 동일한 간선이 된다.

 

 

방향 그래프(Directed Graph)

간선에 방향성이 존재하는 그래프로서 간선을 통하여 한 쪽 방향으로만 갈 수 있다.

정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시한다.

방향 그래프에서 <A,B>와 <B,A>는 서로 다른 간선이다.

 

 

부분 그래프(Subgraph)

어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프

 

 

그래프 G와 부분 그래프 G'

 

가중치 그래프(Weighted Graph)

간선에 비용이나 가중치가 할당된 그래프

네트워크(network)라고도 한다.

 

 

 

완전 그래프(Complete Graph)

그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프

무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n(n-1)/2가 된다.

 

 

 

연결 그래프(Connected Graph)

무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되었다고 하며,

이러한 무방향 그래프를 연결 그래프라 부른다.

트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프이다.

 

 

비연결 그래프(Unconnected Graph)

연결되지 않은 정점이 있는 그래프

 

 

 

그래프의 구현 방법

 

그래프를 구현하는 방법에는 2가지 방법이 있다. 각각 메모리 사용량과 처리 시간 등에서 장단점을 가진다.

 

인접 행렬

그래프의 정점 수가 n이라면 n x n의 2차원 배열인 인접 행렬로 표현한다.

간선 (i, j)가 그래프에 존재할 경우 `M[i][j] = 1` , 아닐 경우 `M[i][j] = 0`으로 표현한다.

 

인접행렬의 특징

• 두 정점을 연결하는 간선의 존재 여부를 `M[u][v]`의 값을 조사하여 O(1) 시간 안에 즉시 알 수 있다.
• 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산에 의해 알 수 있다.
  • 정점 i에 대한 차수는 인접 배열의 i번째 행에 있는 값을 모두 더하면 된다.
• 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야하므로 (On^2)의 시간이 요구된다.
• n개의 정점을 가지는 그래프를 표현하기 위해 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하다.
  • 간선이 많이 존재하는 밀집 그래프에 적합하다.
  • 적은 간선을 가지는 희소 그래프의 경우 메모리의 낭비가 크므로 적합하지 않다.

 

 

 

인접 행렬 구현

#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");
	}
}

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);
}

 

인접 리스트

그래프를 표현함에 있어 각각의 정점에 인접한 정점들을 연결리스트로 표시한 것이다.

정점의 리스트 배열로 관계를 설정하며 노드들간에 직접 연결이 되어 있으면 해당 노드의 인덱스에 그 노드를 삽입한다.

 

인접 리스트의 특징

• 정점의 수가 n개이고 간선의 수가 e개인 무방향 그래프를 표시하기 위해 n개의 연결리스트, n개의 헤더 노드, 2e개의 노드가 필요하다.
• 따라서 간선의 개수가 적은 희소 그래프의 표현에 적합하다.
• 두 정점을 연결하는 간선의 존재 여부를 확인할 때 O(e)시간이 걸린다.
• n개 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하므로 O(n+e)의 연산이 요구된다.

 

 

인접 리스트 구현

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

#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, "그래프: 정점의 개수 초과");
	}
	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;
	}
	// 정점 u에 간선 (u, v)를 삽입하는 연산
	// 정점 u의 인접리스트에 간선을 나타내는 노드를 생성하여 삽입
	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);
	return 0;
}