<div id="readability-page-1" class="page"><div><h2 id="그래프란">그래프란?</h2>
그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조이다. 그래프는 1736년에 수학자 오일러가 “Konigsber의 다리” 문제를 해결하기 위해 처음으로 사용했다고 한다.
그래프로 표현할 수 있는 것들로는 도로, 미로, 네트워크 등이 있다.
<h2 id="그래프의-정의-및-용어">그래프의 정의 및 용어</h2>
그래프는 정점(vertex)와 간선(edge)들의 유한 집합이라 할 수 있다.
<h3 id="정점">정점</h3>
정점은 노드(node)라고도 불리며 여러 가지 특성을 가질 수 있는 객체를 의미
<h3 id="간선">간선</h3>
간선은 링크(link)라고도 불리며 정점들 간의 관계를 의미한다.
<h3 id="무방향-그래프">무방향 그래프</h3>
간선을 통해서 양방향으로 갈 수 있는 그래프를 말한다. 예를 들어 정점 A와 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현하는데, 여기서 (A, B), (B, A)는 동일한 간선이 된다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/d3c6e220-a1c4-434b-8961-95a9636ecd72/image.png">
<h3 id="방향-그래프">방향 그래프</h3>
간선에 방향성이 존재하는 그래프로서 도로의 일방통행길처럼 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나타낸다. 정점 A에서 B로만 갈 수 있는 간선은 &lt;A, B&gt;로 표시한다. 즉, &lt;A, B&gt;와 &lt;B, A&gt;는 서로 다른 간선이다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/30e0a495-14ef-45c9-ac79-e79b257a477a/image.png">
<h3 id="가중치-그래프네트워크">가중치 그래프(네트워크)</h3>
간선에 가중치를 할당하면 간선의 역할이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있게 된다.
이런 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 네트워크(network)라 한다.
<h3 id="부분-그래프">부분 그래프</h3>
어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 말한다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/65373786-e93a-42f3-917f-316526387942/image.png">
즉, 그래프 b를 그래프 a에 포함되는 부분 그래프라고 한다.
<h2 id="정점의-차수">정점의 차수</h2>
하나의 정점에서 간선에 의해 직접 연결된 정점을 말한다.
위 그림에서 점점 0의 인점 정점은 정점 1, 정점 2, 정점 3이다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/636e1c7d-5f44-4597-bd11-99fe016c264c/image.png">
<h3 id="무방향-그래프의-차수">무방향 그래프의 차수</h3>
무방향 그래프에서 정점의 차수(degree)는 그 정점에 인접한 정점의 수를 말한다. 또한 모든 정점의 차수를 합하면 간선 수의 2배가 된다. 하나의 간선이 두개의 정점과 모두 연결되어 있기 때문이다.
<h3 id="방향-그래프의-차수">방향 그래프의 차수</h3>
방향 그래프에서는 진입 차수와 진출 차수로 나뉜다.
<ul>
<li>진입 차수(in-degree): 외부에서 오는 간선의 수</li>
<li>진출 차수(out-degree): 외부로 향하는 간선의 수</li>
</ul>
<img src="https://velog.velcdn.com/images/jwlee010523/post/0bcbbf63-fd70-48d2-acd8-b172c142d2a9/image.png">
G3 그래프에서 정점 1의 내차수는 1개이고, 외차수는 2개이다. 그리고 방향 그래프의 모든 진입(진출) 차수의 합은 간선의 수이다.
<h2 id="경로">경로</h2>
무방향 그래프에서 정점 s로부터 정점 e까지의 경는 정점의 자열 s, v1, v2, …, vk, e로서, 나열된 정점들 간에는 반드시 간선 (s, v1), (v1, v2), … , (vk, e)가 존재한다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/48eb971d-f357-43b0-91b0-c1e6228f0f22/image.png">
예를 들어 왼쪽 그래프에서 0, 1, 2, 3은 경로지만 0, 1, 3, 2는 경로가 아니다. 왜냐하면 간선(1, 3)이 존재하지 않기 때문이다.
<h3 id="단순-경로">단순 경로</h3>
경로 중에서 반복되는 간선이 없을 경우 단순 경로라고 한다.
즉, 정점간을 잇는 간선이 단 하나인 경우를 말한다.
<h3 id="사이클">사이클</h3>
<img src="https://velog.velcdn.com/images/jwlee010523/post/ec6b0198-594c-4c9b-b5ed-3f546997acd2/image.png">
단순 경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클이라고 한다.
(트리에서는 사이클 허용 x)
<h2 id="연결-그래프">연결 그래프</h2>
무방향 그래프에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면, 이러한 무방향 그래프를 연결 그래프라고 한다. 그렇지 않은 그래프는 비연결 그래프라고 한다.
트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프이다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/3e02a086-3d4e-418d-a27d-f6b0e96fe19a/image.png">
<h2 id="완전-그래프">완전 그래프</h2>
<img src="https://velog.velcdn.com/images/jwlee010523/post/8cdca101-2ea7-450a-90fd-b40dcbf98069/image.png">
모든 정점이 서로 연결되어 있는 그래프를 말한다.
정점의 수는 n개이며, 하나의 정점은 n-1개의 다른 정점으로 연결된다.
간선의 수는 n(n-1)/2개가 된다.
왼쪽에 있는 그래프의 간선의 수는 6이다.
<h2 id="그래프의-표현-방법">그래프의 표현 방법</h2>
<h2 id="인접-행렬adjacency-matrix">인접 행렬(Adjacency matrix)</h2>
2차원 배열을 사용하여 그래프를 표현하는 방법이다. 무방향 그래프의 간선(i, j)는 정점 i에서 정점 j로의 연결뿐만 아니라 정점 j로의 연결뿐만 아니라 정점 i로의 연결을 동시에 의미한다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/60f16d32-3627-46eb-aacc-922049cc6423/image.png">
n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수와 무관하게 항상 n^2의 메모리 공간이 필요하다. 이데 인접 행렬은 a와 같이 그래프에 간선이 많이 존재하는 밀집 그래프를 표현하는 경우에는 적합하나 b와 같이 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 에는 메모리 낭비가 크므로 적절하지 않다.
인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 파악하는 시간복잡도는 O(1)으로 즉시 알 수 있다는 장점이 있다.
또한 행렬의 크기는 노드의 개수로 결정된다. a의 경우 노드의 개수가 4이므로 4x4 행렬로 나타내는 것이다.
<h3 id="예제-코드">예제 코드</h3>
<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#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-&gt;n = 0;
	for (r = 0; r &lt; MAX_VERTICES; r++)
		for (c = 0; c &lt; MAX_VERTICES; c++)
			g-&gt;adj_mat[r][c] = 0;
}

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

void insert_edge(GraphType* g, int start, int end) {
	g-&gt;adj_mat[start][end] = 1;
	g-&gt;adj_mat[end][start] = 1;
}

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

int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	for (int i = 0; i &lt; 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;
}</code></pre>
<h2 id="인접-리스트">인접 리스트</h2>
인접한 정점들을 연결 리스트로 표시한 것이다. 각 연결 리스트의 노드들은 인접 정점을 저장하게 된다.
무방향 그래프의 경우 정점 i와 정점 j를 연결하는 간선(i, j)는 정점 i의 연결 리스트에 인접 정점 j로 한번 표현되고, 정점 j의 연결 리스트에 인접 정점 i로 다시 한번 표현된다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/c8249e46-c15f-4ec2-a30c-a437188f1011/image.png">
인접 리스트의 시간 복잡도는 O(n + e)이다. n개의 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하기 때문이다.
<h3 id="예제-코드-1">예제 코드</h3>
<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#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-&gt;n = 0;
	for (v = 0; v &lt; MAX_VERTICES; v++)
		g-&gt;adj_list[v] = NULL;
}

void insert_vertex(GraphType* g, int v) {
	g-&gt;n++;
}

// 삽입 쉽게 하기 위해 맨 처음에 노드 삽입
void insert_edge(GraphType* g, int u, int v) {
	GraphNode* node;
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node-&gt;vertex = v;
	node-&gt;link = g-&gt;adj_list[u];
	g-&gt;adj_list[u] = node;
}

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

int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	for (int i = 0; i &lt; 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;
}</code></pre>
위 코드를 그림으로 나타내면 다음과 같다.
<img src="https://velog.velcdn.com/images/jwlee010523/post/1f1a878a-a86a-457a-8708-0612b62ea914/image.png">
<blockquote>
출처 
C언어로 쉽게 풀어쓴 자료구조 - 천인구
</blockquote></div></div>

jwlee010523.log

그래프란?
그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조이다. 그래프는 1736년에 수학자 오일러가 “Konigsber의 다리” 문제를 해결하기 위해 처음으로 사용했다고 한다.
그래프로 표현할 수 있는 것들로는 도로, 미로, 네트워크 등이 있다.
그래프의 정의 및 용어
그래프는 정점(vertex)와 간선(edge)들의 유한 집합이라 할 수 있다.
정점
정점은 노드(node)라고도 불리며 여러 가지 특성을 가질 수 있는 객체를 의미
간선
간선은 링크(link)라고도 불리며 정점들 간의 관계를 의미한다.
무방향 그래프
간선을 통해서 양방향으로 갈 수 있는 그래프를 말한다. 예를 들어 정점 A와 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현하는데, 여기서 (A, B), (B, A)는 동일한 간선이 된다.
방향 그래프
간선에 방향성이 존재하는 그래프로서 도로의 일방통행길처럼 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나타낸다. 정점 A에서 B로만 갈 수 있는 간선은 <A, B>로 표시한다. 즉, <A, B>와 <B, A>는 서로 다른 간선이다.
가중치 그래프(네트워크)
간선에 가중치를 할당하면 간선의 역할이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있게 된다.
이런 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 네트워크(network)라 한다.
부분 그래프
어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 말한다.
즉, 그래프 b를 그래프 a에 포함되는 부분 그래프라고 한다.
정점의 차수
하나의 정점에서 간선에 의해 직접 연결된 정점을 말한다.
위 그림에서 점점 0의 인점 정점은 정점 1, 정점 2, 정점 3이다.
무방향 그래프의 차수
무방향 그래프에서 정점의 차수(degree)는 그 정점에 인접한 정점의 수를 말한다. 또한 모든 정점의 차수를 합하면 간선 수의 2배가 된다. 하나의 간선이 두개의 정점과 모두 연결되어 있기 때문이다.
방향 그래프의 차수
방향 그래프에서는 진입 차수와 진출 차수로 나뉜다.
진입 차수(in-degree): 외부에서 오는 간선의 수
진출 차수(out-degree): 외부로 향하는 간선의 수
G3 그래프에서 정점 1의 내차수는 1개이고, 외차수는 2개이다. 그리고 방향 그래프의 모든 진입(진출) 차수의 합은 간선의 수이다.
경로
무방향 그래프에서 정점 s로부터 정점 e까지의 경는 정점의 자열 s, v1, v2, …, vk, e로서, 나열된 정점들 간에는 반드시 간선 (s, v1), (v1, v2), … , (vk, e)가 존재한다.
예를 들어 왼쪽 그래프에서 0, 1, 2, 3은 경로지만 0, 1, 3, 2는 경로가 아니다. 왜냐하면 간선(1, 3)이 존재하지 않기 때문이다.
단순 경로
경로 중에서 반복되는 간선이 없을 경우 단순 경로라고 한다.
즉, 정점간을 잇는 간선이 단 하나인 경우를 말한다.
사이클
단순 경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클이라고 한다.
(트리에서는 사이클 허용 x)
연결 그래프
무방향 그래프에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면, 이러한 무방향 그래프를 연결 그래프라고 한다. 그렇지 않은 그래프는 비연결 그래프라고 한다.
트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프이다.
완전 그래프
모든 정점이 서로 연결되어 있는 그래프를 말한다.
정점의 수는 n개이며, 하나의 정점은 n-1개의 다른 정점으로 연결된다.
간선의 수는 n(n-1)/2개가 된다.
왼쪽에 있는 그래프의 간선의 수는 6이다.
그래프의 표현 방법
인접 행렬(Adjacency matrix)
2차원 배열을 사용하여 그래프를 표현하는 방법이다. 무방향 그래프의 간선(i, j)는 정점 i에서 정점 j로의 연결뿐만 아니라 정점 j로의 연결뿐만 아니라 정점 i로의 연결을 동시에 의미한다.
n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수와 무관하게 항상 n^2의 메모리 공간이 필요하다. 이데 인접 행렬은 a와 같이 그래프에 간선이 많이 존재하는 밀집 그래프를 표현하는 경우에는 적합하나 b와 같이 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 에는 메모리 낭비가 크므로 적절하지 않다.
인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 파악하는 시간복잡도는 O(1)으로 즉시 알 수 있다는 장점이 있다.
또한 행렬의 크기는 노드의 개수로 결정된다. a의 경우 노드의 개수가 4이므로 4x4 행렬로 나타내는 것이다.
예제 코드
#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) {
 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() {
 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;
}
인접 리스트
인접한 정점들을 연결 리스트로 표시한 것이다. 각 연결 리스트의 노드들은 인접 정점을 저장하게 된다.
무방향 그래프의 경우 정점 i와 정점 j를 연결하는 간선(i, j)는 정점 i의 연결 리스트에 인접 정점 j로 한번 표현되고, 정점 j의 연결 리스트에 인접 정점 i로 다시 한번 표현된다.
인접 리스트의 시간 복잡도는 O(n + e)이다. 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) {
 g->n++;
}
// 삽입 쉽게 하기 위해 맨 처음에 노드 삽입
void insert_edge(GraphType* g, int u, int v) {
 GraphNode* node;
 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;
}
위 코드를 그림으로 나타내면 다음과 같다.
출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

그래프(Graph

댓글