[C언어로 쉽게 풀어쓴 자료구조] Chapter 10 - 그래프1

그래프(graph) : 객체 사이의 연결 관계를 표현할 수 있는 자료구조

 

그래프를 표현하는 방법 

1. 인접행렬 : 2차원 배열을 사용하여 그래프를 표현

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++; // 정점 +1
}
// 간선 삽입 연산
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]); // %2d : 두자리 이하의 수이면, 여백을 추가해 2자리 확보 후 출력
		}
		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);
}
/* 출력값 
 0  1  1  1
 1  0  1  0
 1  1  0  1
 1  0  1  0
 */

 

 

 

// 인접 리스트를 이용한 그래프 구현

// 인접 리스트를 이용한 그래프 구현
#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; // 그래프의 정점의 개수를 0으로 초기화
    // 정점과 인접한 정점을 가리키는 포인터(그래프 내의 모든 정점에 대하여)
	for (v = 0; v<MAX_VERTICES; v++)
		g->adj_list[v] = NULL; // NULL로 설정하여 모든 간선을 삭제
}

// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{	// 정점을 추가 하였을때, 설정한 최대 정점 개수 보다 많을때
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과"); 
		return;
	}
	g->n++; // 그래프 내의 정점의 개수를 +1
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType* g, int u, int v)
{
    // v와 u간의 간선 삽입
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v; // v를 간선의 시작점
	node->link = g->adj_list[u]; // link 필드가 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;
}
/*출력값
정점 0의 인접 리스트 -> 3 -> 2 -> 1
정점 1의 인접 리스트 -> 2 -> 0
정점 2의 인접 리스트 -> 3 -> 1 -> 0
정점 3의 인접 리스트 -> 2 -> 0
*/

 

 

// 그래프의 탐색

* 깊이 우선 탐색 (DFS : Depth First Search)

: 그래프의 시작 정점에서 시작 -> 아직 방문하지 않은 인접 정점으로 이동 -> 이동한 정점에서 깊이 우선 탐색 실행

=> 한 정점에서 한 방향으로 끝까지 먼저 들어가는 탐색 방식

 

* 너비 우선 탐색 (BFS : Breadth Frist Search)

: 그래프의 시작 정점에서 시작 -> 인접한 정점들을 모두 방문(1) -> (1)에서 방문한 정점들과 아직 방문하지 않은 인접한 정점들을 방문 -> 모든 정점들을 방문할 때 까지 반복

=> 트리에서 레벨 순으로 노드들을 방문 (같은 레벨에서는 왼쪽에서 오른쪽으로 우선 순위)

 

 

// 깊이 우선 탐색 (인접 배열)

// 깊이 우선 탐색 (인접 배열)
#include <stdio.h>
#include <stdlib.h>

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

int visited[MAX_VERTICES]; // 방문한 정점을 표시하기 위한 리스트

// 그래프 초기화
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;
}

// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색 (순환을 사용)
// 그래프 g에서 깊이 우선 탐색을 정점 v 부터 시작
void dfs_mat(GraphType* g, int v)
{
	int w;
	visited[v] = TRUE;		// 정점 v의 방문 표시
	printf("정점 %d -> ", v);		// 방문한 정점 출력
	for (w = 0; w<g->n; w++) 		// 인접 정점 탐색
        // (정점 v와 인접한 정점w) and (아직 방문하지 않은 정점 : visited[w]=false)
		if (g->adj_mat[v][w] && !visited[w])
			dfs_mat(g, w);	//정점 w에서 DFS 새로 시작(순환)
}

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

	//       0
	//     / | \
	//    /  |  \
	//   1 - 2 - 3


	printf("깊이 우선 탐색\n");
	dfs_mat(g, 0);
	printf("\n");
	free(g);
	return 0;
}

/*출력값
깊이 우선 탐색
정점 0 -> 정점 1 -> 정점 2 -> 정점 3 ->
*/

 

 

// 깊이 우선 탐색 (인접 리스트)

// 인접 리스트를 이용한 그래프 구현
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

#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)
{
    // v와 u간의 간선 삽입
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v; // v를 간선의 시작점
	node->link = g->adj_list[u]; // link 필드가 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 visited[MAX_VERTICES];

// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType* g, int v)
{
	GraphNode* w;
	visited[v] = TRUE;   		// 정점 v의 방문 표시
	printf("정점 %d -> ", v);		// 방문한 정점 출력
	for (w = g->adj_list[v]; w; w = w->link)// 인접 정점 탐색
		if (!visited[w->vertex])
			dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작
}

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

    //       0
	//     / | \
	//    /  |  \
	//   1 - 2 - 3

	printf("\n\n");
	dfs_list(g,0);
	free(g);
	return 0;
}
/*출력값
정점 0의 인접 리스트 -> 3 -> 2 -> 1
정점 1의 인접 리스트 -> 2 -> 0
정점 2의 인접 리스트 -> 3 -> 1 -> 0
정점 3의 인접 리스트 -> 2 -> 0


정점 0 -> 정점 3 -> 정점 2 -> 정점 1 ->
*/

 

 

// 너비 우선 탐색 (인접 배열)

// 너비 우선 탐색 (인접 행렬)
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10


// ========= 큐 정의 코드 시작 ==================
typedef int element;
typedef struct { // 큐 타입
	element  queue[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType; // 큐 정의

// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 공백 상태 검출 함수
void queue_init(QueueType *q)
{
	q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType *q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}
// ========= 큐 정의 코드 끝 ==================


// ========= 그래프 코드 시작 ==================
#define MAX_VERTICES 50 // 정점 개수 최댓값
typedef struct GraphType {
	int n;	// 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

// 그래프 초기화
void graph_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 bfs_mat(GraphType* g, int v)
{
	int w;
	QueueType q;

	queue_init(&q);     // 큐 초기화
	visited[v] = TRUE;          // 정점 v 방문 표시
	printf("%d  방문 -> ", v);
	enqueue(&q, v);			// 시작 정점을 큐에 저장
	while (!is_empty(&q)) { // 큐가 빌때까지 실행
		v = dequeue(&q);		// 큐에 정점 추출
		for (w = 0; w<g->n; w++)	// 인접 정점 탐색
			if (g->adj_mat[v][w] && !visited[w]) {
				visited[w] = TRUE;    // 방문 표시
				printf("%d 방문 -> ", w);
				enqueue(&q, w); 	// 방문한 정점을 큐에 저장
			}
	}
}

int main(void)
{
	GraphType *g;
	g = (GraphType *)malloc(sizeof(GraphType));
	graph_init(g);
	for (int i = 0; i<6; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 1);
	insert_edge(g, 2, 3);
	insert_edge(g, 0, 4);
	insert_edge(g, 4, 5);
	insert_edge(g, 1, 5);

	//              0
	//             / \
	//            2   4
	//           /|   |
	//          3 1---5

	printf("너비 우선 탐색\n");
	bfs_mat(g, 0);
	printf("\n");
	free(g);
	return 0;
}
/* 출력값
너비 우선 탐색
0  방문 -> 2 방문 -> 4 방문 -> 1 방문 -> 3 방문 -> 5 방문 ->

*/

 

 

 

// 너비 우선 탐색 (인접 리스트)

void bfs_list(GraphType* g, int v)
{
	GraphNode* w;
	QueueType q;

	init(&q);    				// 큐 초기 화 
	visited[v] = TRUE;      // 정점 v 방문 표시 
	printf("%d 방문 -> ", v);
	enqueue(&q, v);			// 시작정점을 큐에 저장 
	while (!is_empty(&q)) {
		v = dequeue(&q);		// 큐에 저장된 정점 선택 
		for (w = g->adj_list[v]; w; w = w->link) //인접 정점 탐색
			if (!visited[w->vertex]) {	// 미방문 정점 탐색 
				visited[w->vertex] = TRUE;   // 방문 표시
				printf("%d 방문 -> ", w->vextex);
				enqueue(&q, w->vertex);	//정점을 큐에 삽입
			}
	}
}