[자료구조] - C언어를 활용한 그래프의 구현

1. 개요

 

 소프트웨어 마에스트로 코딩테스트를 봤다. 사실상 네문제를 풀었지만... 제출을 못해서 세문제... 처참한 결과였다. 정식적으로 알고리즘을 공부하려다 보니 DFS와 BFS를 만나게 되었는데, 이를 공부하면서 그래프라는 자료구조를 또 만나게 되었다. 사실 DFS 알고리즘인지를 모르고 사용한 적이 있었는데, 이를 더 공부해볼 생각이다. 다음은 내가 푼 문제이다.

---

apape1225.tistory.com/61

[백준 알고리즘] 1012번 - 유기농 배추 (DFS 알고리즘)

---

 2. 이론

 

- 그래프란?

 

 백문이불여일견! 다음과 같은 그래프를 본적이 있다면 그래프를 본것이다.

---

---

 뭔 거미줄 같이 생기긴 했지만, 조금 관점을 다르게 정의할 수 있다. 그래프는 '정점의 모음'과 이 정점을 잇는 '간선의 모음'과의 결합이다. (뇌를 자극하는 알고리즘, 박상현 저) 그림을 보면 숫자(정점) 들이 선(간선)으로 연결된 모습을 볼 수 있는데, 이것 자체가 그래프이다. 여기서 간선으로 연결되어 있는 점은 서로 인접해있다고 한다. 이 외에 경로와 사이클같은 개념은 알고리즘을 설명할 때 게시하도록 하겠다.

 

 이제 그래프의 기본적인 형태를 알았으니 가장중요한 문제를 해결해보자. 바로 코드로 그래프를 표현하는 것이다. 코드로 그래프를 표현 ( 혹은 구현 )하는 방법은 두가지가있다. 하나는 행렬로 표현하는 방법이고 나머지 하나는 리스트로 표현하는 방법이다. 이 글에서는 리스트로 그래프를 표현하는 방법을 다룰것이다.

 

- 리스트로 구현하는 그래프

 

 이론은 간단하다. 모든 정점들을 리스트로 표현하고, 그 정점과 인접된 정점들을 옆에 나열하는 것이다. 위의 그래프를 리스트로 표현하자면 다음과 같을 것이다.

---

---

 그림을 연보라색으로 표현된 각 정점들 옆으로 정점에 인접해있는 정점들이 나열되어있다. 이렇게 연결 리스트로 그래프를 표현할 수 있다. 이번에는 방향성 그래프를 알아보도록 하자. 다음은 방향성 그래프의 그림이다.

---

---

 이 그래프를 보도록 하자. 첫번째로 본 그래프와는 뭐가 다를까? 바로 방향이다. 첫번째 그래프는 정점들끼리 연결만 되어있지만 이 방향성 그래프는 한 정점이 다른 정점을 가리킨다는 것이 가장 큰 차이이다. 그럼 이 그래프를 리스트로 표현하려면 어떻게 해야할까? 무방향성 그래프 즉 우리가 처음으로 살펴본 그래프는 한 정점과 인접한 정점은 전부 옆에 연결시켰다. 하지만 방향성 그래프는 한정점이 가리키는 정점만 옆에다 두는 것이다. 

 

 예를 들어서 1이 가리키는 정점은 2와 4이므로 1옆에는 2와 4만이 존재하면 되는 것이다. 이렇게 따지면 4는 2만을 가리키고 있으므로 4옆에는 2만이 존재하면 된다. 그림으로 표현하자면 다음과 같다.

---

---

 이렇게 가리키는 정점들만을 옆에 두어 그래프를 구현한다. 자 이제 코드측면으로 보자. 위의 그림과 아래의 그림을 비교해보자.

---

---

 방향성 그래프를 구현한 리스트와 위의 트리는 그냥 똑같은 수준이다. 문제는 정점과 인접하고있는 정점 이 두가지 정점의 분류가 매우 희박해진다는 것이다. 결국 우리는 모든 정점을 표시한 '정점'과 그 정점옆에 나열되어야할 '인접해있는  정점' 을 구분해줘야 한다는 것이다. 나는 책과 인터넷을 참고하여 서로 다른 구조체를 정의해 코드를 작성하였다. 조금 더 깔끔하게 그림으로 표현해보았다.

---

---

 자 위의 그림을 보자. 모든 정점을 표현하는 정점은 Vertex 구조체로 구현하였고 그 옆에 나열되어있는 점은 Edge 구조체로 구현하였다. 그리고 이 전체를 가리키는 Graph 구조체가 있다. 다음은 코드의 구현이다.

 

3. 코드구현

 

- Graph.h

 

#pragma once

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

typedef char ElementType;

typedef struct str_Graph {
	
	struct str_Vertex* graph;
	int vertexCount;

}Graph, *GraphPtr;

typedef struct str_Vertex {

	ElementType data;
	struct str_Vertex* Next;
	struct str_Edge* Edges;

	int index;
	int visited;

}Vertex, *VertexPtr;

typedef struct str_Edge {

	struct str_Vertex* start;
	struct str_Vertex* end;

	struct str_Edge* Next;
	int weight;

}Edge, *EdgePtr;

GraphPtr createGraph();
void deleteGraph(GraphPtr G);

VertexPtr createVertex(ElementType data);
void deleteVertex(VertexPtr V);

EdgePtr createEdge(VertexPtr start, VertexPtr end, int weight);
void deleteEdge(EdgePtr E);

void addVertex(GraphPtr G, VertexPtr V);
void addEdge(VertexPtr V, EdgePtr E);

void printGraph(GraphPtr G);

 

 앞서 말한 구조체 부분들을 정의하고 각 메소드들을 정의하였다. 아직 알고리즘을 구현하지 않았기에 기본적으로 정점을 추가하고 Edge를 추가하는 부분을 만들었다. 그리고 마지막으로 그래프를 출력하는 코드 또한 선언하였다. 다음은 코드 구현부분이다.

 

- Graph.c

 

#include "Graph.h"

GraphPtr createGraph() {
	GraphPtr G = (GraphPtr)malloc(sizeof(Graph));
	G->graph = NULL;
	G->vertexCount = 0;

	return G;
}

VertexPtr createVertex(ElementType data) {

	VertexPtr nVertex = (VertexPtr)malloc(sizeof(Vertex));
	nVertex->data = data;
	nVertex->Edges = nVertex->Next = NULL;
	nVertex->visited = 0;
	nVertex->index = -1;

	return nVertex;
}

void deleteVertex(VertexPtr V) {
	VertexPtr delV = V;
	EdgePtr edge = V->Edges->Next;
	while (edge) {
		deleteEdge(V->Edges);
		V->Edges = edge;
		edge = edge->Next;
	}
	deleteEdge(V->Edges);

	free(delV);
}

EdgePtr createEdge(VertexPtr start, VertexPtr end, int weight) {
	EdgePtr edge = (EdgePtr)malloc(sizeof(Edge));
	edge->start = start;
	edge->end = end;
	edge->Next = NULL;
	edge->weight = weight;
}

void deleteEdge(EdgePtr E) {
	free(E);
}


//여기서부터 구현해라 창규야 ^^

void deleteGraph(GraphPtr G) {
	if (G->graph) {
		VertexPtr V = G->graph;
		while (V) {
			VertexPtr Next = V->Next;
			deleteVertex(V);
			V = Next;
		}
	}
}

void addVertex(GraphPtr G, VertexPtr V) {
	
	V->index = G->vertexCount + 1;

	if (G->graph) {
		VertexPtr buff = G->graph;
		while (buff->Next)
			buff = buff->Next;
		buff->Next = V;
	}
	else {
		G->graph = V;
	}
}

void addEdge(VertexPtr V, EdgePtr E) {

	if (V->Edges) {
		EdgePtr buff = V->Edges;
		if (buff->Next)
			buff = buff->Next;
		buff->Next = E;
	}
	else {
		V->Edges = E;
	}
}

void printGraph(GraphPtr G) {
	
	if (G->graph) {
		VertexPtr V = G->graph;
		while (V) {
			printf("[%c] : ", V->data);
			EdgePtr E = V->Edges;
			while (E) {
				printf("-> [%c] ", E->end->data);
				E = E->Next;
			}
			printf("\n");
			V = V->Next;
		}
	}

	return 0;
}

 

 각 정점과 인접된 정점의 구분이 확실하다면 코드구현이 그렇게 까다롭지 않다는 것을 알 수 있다. 물론 나같은 사람은 조금 오래 걸릴수도 있지만... 다음은 위의 그래프를 사용해보는 main함수와 실행결과이다.

 

- 실행결과

 

#include "Graph.h"

int main(void) {
	
	GraphPtr G = createGraph();
	//printf("!");

	VertexPtr V1 = createVertex('1');
	VertexPtr V2 = createVertex('2');
	VertexPtr V3 = createVertex('3');
	VertexPtr V4 = createVertex('4');
	
	addVertex(G, V1);
	addVertex(G, V2);
	addVertex(G, V3);
	addVertex(G, V4);

	addEdge(V1, createEdge(V1, V2, 0));
	addEdge(V1, createEdge(V1, V4, 0));
	addEdge(V2, createEdge(V2, V3, 0));
	addEdge(V3, createEdge(V3, V4, 0));
	addEdge(V4, createEdge(V4, V2, 0));

	printGraph(G);
	deleteGraph(G);

	return 0;
}

---

---

4. 결어

 

 다음은 본격적으로 알고리즘에 대해 포스팅할것이다. 하필 개강도 겹쳐서 공부할 것이 많지만, 최대한 꾸준히 올려볼 것이다.