C로 만드는 자료구조 - 인접 행렬로 구현한 그래프

dsbook.tistory.com/280 (이전글)

C로 만드는 자료구조 - 그래프(Graph)란?

인접행렬을 이용한 그래프 구현

그래프 G의 각 도드 사이의 간선을 2차원 배열로 저장하는 것이다. 각 노드 사이에 간선이 존재할 경우 해당 배열의 값을 1로 없을때는 0으로 저장한다.  여기서 무방향 그래프라면 반대로 똑같이 1로 저장해주면 된다. 무방향 그래프의 이러한 성질을 대칭성(symmetry)라고 한다.

참고로 인접 행렬에서 각 노드의 차수를 구하고 싶다면 인접 행렬의 각 행 또는 열의 값의 합으로 구할 수 있다.

 이제 방향 그래프를 생각해보자 방향 그래프는 특정 노드로 들어오는 간선의 개수인 진입차수와 진출차수가 서로 다르다. 그렇다면 방향 그래프에서 진입차수,진출 차수를 구하려면 어떻게 해야할까? 무방향 그래프에서 차수를 구할 때와 마찬가지로 우리는 인접행렬을 이용할 것이다. 방향 그래프에서의 각 행은 나가는 간선 즉 진출 차수를 뜻하고 각 열은 들어오는 간선, 진입 차수를 뜻한다.

 마지막으로 가중 방향 그래프를 인접행렬로 저장할 때를 보자.  가중 방향 그래프를 인접행렬에 저장할 때는 간선의 유뮤(1,0)을 저장 하는 것이 아닌 가중치 값을 저장하면된다. 만약 (1,0) 간선의 가중치가 4라면 1대신 4를 저장하면 된다. 간선이 없는 경우는 기존과 마찬가지로 0을 저장한다. 단 가중 방향 그래프에서 진입/진출 차수를 구하려면 기존과는 다르게 0이 아닌 수가 몇 개인 세어 주면 된다.

아래 그림은 여러가지 그래프를 인접 행렬로 표현한 모습이다.

소스 파일 구성은 다음과 같다.

파일 명`	내용
arraygraph.h	구조체 및 함수 선언
arraygraph.cpp	함수 구현
arraygraphmain.cpp	main함수 실행

※ 앞으로 진행하는 인접행렬로 구현하는 그래프는 무방향/방향 그래프와 덧붙여 가중 그래프까지 구현할 수 있게 했다.

1.arraygraph.h

구현하기 앞서 그래프의 추상자료형을 다시 한번 보자

이름		입력 값	출력 값	설명
그래프 생성	createGraph()	최대 노드 개수 n	그래프 g	최대 n개의 노드를 가지는 그래프 g 생성
그래프 삭제	deleteGraph()	그래프 g	N/A	그래프 g의 모든 노드와 간선을 제거
노드 추가	addVertex()	그래프 g 노드 v	N/A	새로운 노드 v를 그래프 g에 추가
간선 추가	addEdge()	그래프 g 노드 u 노드 v	N/A	노드 u와 v를 연결하는 새로운 간선 e를 그래프 g에 추가
노드 제거	removeVertex()	그래프 g 노드 v	N/A	그래프 g의 노드 v와 v와 부속된 모든 간선들을 제거
간선 제거	removeEdge()	그래프 g 노드 u 노드 v	N/A	그래프 g의 노드 u,v 를 연결하는 간선 제거
인접 노드 반환	adjacentNode()	그래프 g 노드 v	노드의 목록	그래프 g에서 노드 v에 인접한 모든 노드들 반환

 주의해야 할점은 간선 추가/제거 시에 입력 노드가 2개의 순서이다. 만약 무방향 그래프라면 두 입력 노드의 순서는 바뀌어도 상관이 없지만 방향 그래프라면 순서가 매우 중요해 진다. 방향 그래프에서 순서가 바뀌면 전혀 다른 간선이 되기 때문이다. 따라서 방향 그래프 일때 간선 추가/제거 시에는 시작 노드와 종료 노드의 순서를 신경 써야 한다.

코드 구현은 다음과 같다.

#pragma once
#define TRUE 1
#define FALSE 0

struct ArrayGraph {

	int maxVertexCnt; // 최대 노드 개수
	int curVertexCnt; // 현재까지 사용된 노드 개수
	int graphType;   // 그래프의 종류- 1 -> 무방향 ,2 -> 방향 그래프
	int** ppAdjEdge; // 간선을 저장하는 2차원 배열
	int* pVertex;    // 노드를 저장하는 1차원 배열
};

ArrayGraph* createAG(int max);  //  무방향 그래프 생성
ArrayGraph* createADG(int max); // 방향 그래프 생성
void deleteAG(ArrayGraph* pGraph);// 그래프 제거
int isEmptyAG(ArrayGraph* pGraph); // 그래프의 노드 존재 유무
int addVertexAG(ArrayGraph* pGraph, int newVertex); // 그래프에 노드 추가하기
int addEdgeAG(ArrayGraph* pGraph, int fromVertex, int toVertex); // 그래프에 간선 추가하기
int addEdgeWeightAG(ArrayGraph* pGraph, int fromVertex, int toVertex, int weight); // 그래프에 가중치 간선 추가하기

int removeVertexAG(ArrayGraph* pGraph, int Vertex); // 그래프에서 노드 제거
int removeEdgeAG(ArrayGraph* pGraph, int fromVertex, int toVertex); // 그래프에서 간선 제거
void displayAG(ArrayGraph* pGraph); // 그래프의 인접행렬 출력

#define USED 1      // 노드 사용 유무 
#define NOT_USED 0  // 나타내기 위한 상수

#define SUCCESS 1  // 그래프 연산 성공 유무
#define FAIL 0     // 나타내기 위한 상수

#define GRAPH_UNDIRECTED 1 //무방향/방향 그래프
#define GRAPH_DIRECTED 2   // 구분하기 위한 상수

 그래프의 구조체 안에는 최대 노드 개수를 저장하는 값, 현재 까지 사용된 노드를 저장하는 값, 그래프의 종류를 저장하는 값, 간선을 저장하는 2차원 배열, 노드르 저장하는 1차원 배열로 구성되어 있다. 또한 편리한 구현을 위해 여러가지 상수 값을 선언했기 때문에 주석을 잘 읽어 보길 바란다.

 아래 그림에서 그래트 G를 표현하기 위해 구조체에 담는다고 생각하면 아래 그림과 같이 될 것이다.(최대 저장 노드는 5라고 가정)

 

2.arraygraph.cpp

 - createAG()

ArrayGraph* createAG(int max) { //  무방향 그래프 생성
	ArrayGraph* pReturn = NULL;
	if (max > 0) { // max가 0보다 크면 그래프 구조체 생성후 초기화
		pReturn = (ArrayGraph*)malloc(sizeof(ArrayGraph));
		 
		pReturn->graphType = GRAPH_UNDIRECTED;   // 무방향으로 설정
		pReturn->maxVertexCnt = max;
	}
	else{
		printf("최대 노드 개수는 0보다 커야 합니다\n");
		return NULL;
	}

	pReturn->pVertex = (int*)malloc(sizeof(int) * max); //노드의 사용 여부 저장하는 배열 메모리 할당
	memset(pReturn->pVertex, NOT_USED, sizeof(int) * max);// 노드의 사용 여부 배열을 NOT_USED로 초기화

	pReturn->ppAdjEdge = (int**)malloc(sizeof(int*) * max);//간선을 저장하는 배열 메모리 할당(포인터 변수(배열)들 저장하는 1차원 배열)
	for (int i = 0; i < max; i++) { // 간선을 저장하는 배열의 각 포인터(배열)들에 메모리 할당
		pReturn->ppAdjEdge[i] = (int*)malloc(sizeof(int) * max);
	}
	for (int i = 0; i < max; i++) { // 각 포인터(배열)들을 0으로 초기화
		memset(pReturn->ppAdjEdge[i], 0, sizeof(int) * max);
	}
	return pReturn;
}
ArrayGraph* createADG(int max) { // 방향 그래프 생성
	ArrayGraph* pReturn = NULL;
	pReturn = createAG(max);
	pReturn->graphType = GRAPH_DIRECTED;
	return pReturn;
}

 기본적으로 무방향 그래프 생성을 구현한 후 방향 그래프 생성 함수는 무방향 그래프 생성 함수를 이용했다. 굳이 별다른 이유는 없고 둘의 차이점은 단지 그래프 타입을 저장하는 변수 값 밖에 없기 때문이다. 생성 함수를 보면 간선을 저장하는 2차원 배열과 노드를 저장하는 배열에 메모리를 할당해줘야 하기 때문에 코드가 길어졌다. 포인터를 사용했기 때문에 그래프 제거시 메모리 할당에 주의해야 한다.

 - addVertexAG()

int addVertexAG(ArrayGraph* pGraph, int newVertex) { // 그래프에 노드 추가하기
	int ret = SUCCESS;

	if (pGraph != NULL) {
		if (newVertex < pGraph->maxVertexCnt && pGraph->pVertex[newVertex] == NOT_USED) {
			pGraph->pVertex[newVertex] = USED;
			pGraph->curVertexCnt++;
		}
		else {
			printf("이미 존재하는 노드거나 최대 노드 개수를 초과 했습니다.\n");
			ret = FAIL;
		}
	}
	return ret;
}

 노드를 추가하는 함수는 생각보다 간단하다. 생각 해줘야 하는 점은 단지 해당 노드의 값이 범위를 벗어 났는지 아닌지와 이미 존재하는지 아닌지만 확인해주는 것이다.

- addEdgeAG()

int addEdgeWeightAG(ArrayGraph* pGraph, int fromVertex, int toVertex, int weight) { // 그래프에 가중치 간선 추가하기
	// 기본 간선 추가함수보다 범용성이 크다! 
	int ret = SUCCESS;

	if (pGraph != NULL) {
		if (pGraph->pVertex[fromVertex] == USED && pGraph->pVertex[toVertex] == USED) { // 시작 노드와 종료 노드가 사용중인 노드인지 확인
			if (pGraph->ppAdjEdge[fromVertex][toVertex] == 0) { // 이미 사용중인 간선인지 확인
				pGraph->ppAdjEdge[fromVertex][toVertex] = weight; // 간선추가
				if (pGraph->graphType == GRAPH_UNDIRECTED) {// 무방향인경우 반대로도 추가
					pGraph->ppAdjEdge[toVertex][fromVertex] = weight;
				}
			}
			else {
				printf("이미 존재하는 간선입니다.\n");
				ret = FAIL;
			}
		}
		else {
			printf("시작 노드 또는 종료 노드가 존재하지 않습니다.\n");
			ret = FAIL;
		}
	}
	return ret;
}
int addEdgeAG(ArrayGraph* pGraph, int fromVertex, int toVertex) { // 그래프에 간선 추가하기
	return addEdgeWeightAG(pGraph, fromVertex, toVertex, 1);
}

 기본적으로 가중치 그래프의 간선 추가 함수를 이용하고 가중치 그래프가 아닌 경우는 가중치 그래프의 간선 함수를 이용한다. 가중치가 없는 경우 간선 추가시 간선 배열에 1로 저장하는데 이는 가중치 그래프에서 간선의 가중치의 값이 1인 경우와 마찬가지 이기 때문이다. 

 간선의 추가도 노드의 추가와 마찬가지로 먼저 간선 추가가 가능한지 확인을 해야한다. 입력받은 두 노드가 사용중인 노드인지. 간선이 이미 있는 간선인지 확인 후 간선 추가가 가능하다면 간선을 저장하는 배열에 weight값으로 저장한다. 이때 무방향 그래프라면 꼬리와 머리를 바꿨을 때도 추가해줘야 한다.

- removeVertexAG() , removeEdgeAG()

int removeVertexAG(ArrayGraph* pGraph, int Vertex) { // 그래프에서 노드 제거
	int ret = SUCCESS;

	if (pGraph != NULL) {
		if (pGraph->pVertex[Vertex] == USED) {
			for (int i = 0; i < pGraph->maxVertexCnt; i++) {
				pGraph->ppAdjEdge[Vertex][i] = 0;
				pGraph->ppAdjEdge[i][Vertex] = 0;
			}
			pGraph->pVertex[Vertex] == NOT_USED;
			pGraph->curVertexCnt--;
		}
		else {
			printf("이미 존재하지 않는 노드입니다\n");
			ret = FAIL;
		}
	}
	return ret;
}
int removeEdgeAG(ArrayGraph* pGraph, int fromVertex, int toVertex) { // 그래프에서 간선 제거
	int ret = SUCCESS;

	if (pGraph != NULL) {
		if (pGraph->pVertex[fromVertex] == USED && pGraph->pVertex[toVertex] == USED) { // 시작 노드와 종료 노드가 사용중인 노드인지 확인
			if (pGraph->ppAdjEdge[fromVertex][toVertex] != 0) { // 이미 사용중인 간선인지 확인
				pGraph->ppAdjEdge[fromVertex][toVertex] =0; // 간선제거
				if (pGraph->graphType == GRAPH_UNDIRECTED) {// 무방향인경우 반대로도 제거
					pGraph->ppAdjEdge[toVertex][fromVertex] = 0;
				}
			}
			else {
				printf("이미 존재하지 않은 간선입니다.\n");
				ret = FAIL;
			}
		}
		else {
			printf("시작 노드 또는 종료 노드가 존재하지 않습니다.\n");
			ret = FAIL;
		}
	}
	return ret;
}
int removeVertexAG_2(ArrayGraph* pGraph, int Vertex) { // 그래프에서 노드 제거
	int ret = SUCCESS;

	if (pGraph != NULL) {
		if (pGraph->pVertex[Vertex] == USED) {
			for (int i = 0; i < pGraph->maxVertexCnt; i++) {
				removeEdgeAG(pGraph, Vertex, i);
				removeEdgeAG(pGraph, i, Vertex);
			}
			
			pGraph->pVertex[Vertex] == NOT_USED;
			pGraph->curVertexCnt--;
		}
		else {
			printf("이미 존재하지 않는 노드입니다\n");
			ret = FAIL;
		}
	}
	return ret;
}

 그래츠에서의 노드와 간선 제거도 추가 할때와 마찬가지 이다. 가장 먼저 해당 노드와 간선이 존재하는지 부터 체크를 한 수 연산이 진행 된다. 간선 제거시에는 해당하는 간선만 간선을 저장하는 배열에서 값을 0으로 만들어 주면 되는데
노드를 제거하는 경우는 해당 노드와 연결된 모든 간선 또한 제거해야 하기 때문에 for문을 이용해 한바뀌 돌면서 제거할 노드에 부속된 노드가 있는지 확인 해줘야 한다. 이때 부속된 간선을 제거할때 앞서 구현한 간선제거 함수를 사용해도된다. 간선 제거 함수를 사용한 코드는 removeVertexAG_2() 이다.

- deleteAG()

void deleteAG(ArrayGraph* pGraph) {// 그래프 제거
	if (pGraph != NULL) {
		free(pGraph->pVertex);
		for (int i = 0; i < pGraph->maxVertexCnt; i++) {
			free(pGraph->ppAdjEdge[i]);
		}
		free(pGraph->ppAdjEdge);
		free(pGraph);
	}
}

 그래프의 메모리를 제거해 주는 함수이다. 차근차근 메모리를 해제 해주어야 하며 특히 간선을 저장하는 2차원 배열 메모리 해제를 주의해야 한다.