Chapter 14. 인접 리스트 기반의 그래프 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

그래프의 구현 관점에서 무방향 그래프와 방향 그래프의 유일한 차이점은 연결 리스트에 추가하는 노드의 수에 있기 때문에, 이 둘의 구현 방법에는 차이가 없다고 볼 수 있습니다. 굳이 따지자면 무방향 그래프를 구현할 때 연결 리스트에 추가해야 하는 노드의 수가 방향 그래프에 비해 두 배 많기 때문에 무방향 그래프의 구현이 좀 더 복잡하다고 할 수 있습니다. 그래서 무방향 그래프를 대상으로 구현해 보고자 합니다.

 

헤더 파일은 다음과 같습니다.

//ALGraph.h
//수정 날짜 : 2021.03.27
//작성자 : KOEY
#ifndef ALGRAPH_H
#define ALGRAPH_H

#include "LinkedList.h"

//정점의 이름을 상수화
enum {A, B, C, D, E, F, G, H, I, J, K};

typedef struct Ual
{
	int numV;
	int numE;
	List* adjList;
}ALGraph;

void GraphInit(ALGraph* pg, int nv);    //그래프의 초기화
void GraphDestroy(ALGraph* pg);    //그래프의 리소스 해제
void AddEdge(ALGraph* pg, int fromV, int toV);    //간선의 추가
void ShowGraphEdgeInfo(ALGraph* pg);    //간선의 정보 출력

#endif

인접 리스트의 핵심은 연결 리스트입니다. 따라서 앞서 구현했던 연결 리스트를 가져다 쓰기 위해서 LinkedList.h 헤더 파일을 인클루드 했습니다.

 

위의 헤더 파일에 선언된 함수들을 기반으로 그래프를 구성하는 main 함수와 그 실행결과를 보면서 각 함수들이 어떻게 동작할지 생각해 봅니다.

//main.c
//수정날짜 : 2021.03.27
//작성자 : KOEY
#include <stdio.h>
#include "ALGraph.h"

int main(void)
{
	ALGraph graph;    //그래프의 생성
	GraphInit(&graph, 5);    //그래프의 초기화

	AddEdge(&graph, A, B);    
	AddEdge(&graph, A, D);
	AddEdge(&graph, B, C);
	AddEdge(&graph, C, D);
	AddEdge(&graph, D, E);
	AddEdge(&graph, E, A);

	ShowGraphEdgeInfo(&graph);    //그래프의 간선 정보 출력
	GraphDestroy(&graph);    //그래프의 리소스 소멸

	return 0;
}

/*
실행결과

A와 연결된 정점 : B D E
B와 연결된 정점 : A C
C와 연결된 정점 : B D
D와 연결된 정점 : A C E
E와 연결된 정점 : A D

*/

GraphInit 함수를 호출할 때 두 번째 인자로 5를 주었습니다. 이에 5개의 정점을 생성하게 되고, 정점의 이름은 A, B, C, D, E가 됩니다. 그리고 GraphDestroy 함수는 GraphInit 함수로 인해 동적 할당된 메모리 공간을 반환하는 역할을 합니다.

 

이를 바탕으로 각 함수들을 구현해 봅니다. 아래는 제가 직접 구현해 본 함수들입니다.

//ALGreph.c
//수정날짜 : 2021.03.27
//작성자 : KOEY
#include "ALGraph.h"
#include <stdlib.h>
#include <stdio.h>

void GraphInit(ALGraph* pg, int nv)
{
	pg->adjList = (List*)malloc(sizeof(List) * nv);    //List 구조체 변수를 저장할 배열 생성
	if (pg->adjList == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}

	int i;
	for (i = 0; i < nv; i++)
	{
		ListInit(&(pg->adjList[i]));    //배열의 각각의 List 구조체 변수를 초기화
	}
	pg->numE = 0;
	pg->numV = nv;
}

void GraphDestroy(ALGraph* pg)
{
	if (pg->adjList == NULL)
	{
		return;
	}

	int i;
	for (i = 0; i < pg->numV; i++)
	{
		Data data;
		while (LFirst(&(pg->adjList[i]), &data))    //리스트에 노드가 존재한다면
		{
			LRemove(&(pg->adjList[i]));    //해당 노드 삭제
		}
	}

	free(pg->adjList);    //List 구조체 변수들을 저장하던 배열 삭제
	pg->numE = 0;
	pg->numV = 0;
}

void AddEdge(ALGraph* pg, int fromV, int toV) 
{
	LInsert(&(pg->adjList[fromV]), toV + 'A');
	LInsert(&(pg->adjList[toV]), fromV + 'A');    //무방향 그래프이므로 대칭되게 저장
	pg->numE++;
}

void ShowGraphEdgeInfo(ALGraph* pg)
{
	int i;
	for (i = 0; i < pg->numV; i++)    //모든 배열 요소에 대해
	{
		printf("%c와 연결된 정점 : ", i + 'A');

		Data data;
		if (LFirst(&(pg->adjList[i]), &data))
		{
			printf("%c ", data);
			while (LNext(&(pg->adjList[i]), &data))
			{
				printf("%c ", data);
			}
		}
		else
		{
			printf("없음");
		}
		printf("\n");
	}
}

그래프를 구현하고 다시 앞서 보인 main 함수를 실행해서 실행결과를 확인해 보겠습니다.

//main.c
//수정날짜 : 2021.03.27
//작성자 : KOEY
#include <stdio.h>
#include "ALGraph.h"

int main(void)
{
	ALGraph graph;    //그래프의 생성
	GraphInit(&graph, 5);    //그래프의 초기화

	AddEdge(&graph, A, B);    
	AddEdge(&graph, A, D);
	AddEdge(&graph, B, C);
	AddEdge(&graph, C, D);
	AddEdge(&graph, D, E);
	AddEdge(&graph, E, A);

	ShowGraphEdgeInfo(&graph);    //그래프의 간선 정보 출력
	GraphDestroy(&graph);    //그래프의 리소스 소멸

	return 0;
}

/*
실행결과

A와 연결된 정점 : E D B
B와 연결된 정점 : C A
C와 연결된 정점 : D B
D와 연결된 정점 : E C A
E와 연결된 정점 : A D

*/

책에서는 리스트에 값을 저장할 때 오름차순으로 정렬했지만 그래프에서 정렬은 불필요한 과정이므로, 정렬은 하지 않았습니다.