[C언어] graph - 배열 구현편

Graph

우선, 방향이 존재하지 않은 그래프를 배열로 표현을 하게 된다면 위 사진과 같은 형식으로 표현을 할 수 있다.

0은 1과 2를 가르키고 있으니 해당 칸에 1로 표기하는 방식이다.

 

위 사진은 앞서 나온 그래프와 다르게 방향이 존재한다.

그렇기 때문에 0이 1을 가르켰기 때문에, 1행에서 2번째 데이터에 1을 표기하면 된다.

 

마지막 사진으로 보게되면, 방향과 가중치를 모두 가진 그래프로 표현을 하기 위해서는 앞서 말한 1행 2번째 데이터에 1이 아닌 가중치를 표기하면 된다.

 

이제 이러한 상황에서 구조체에서 구현을 해야 되는 것을 보게되면,

• 최대 노드 개수
• 현재 노드 개수
• 그래프 종류
• 노드 저장을 위한 배열 포인터
• 간선 저장을 위한 배열 포인터

 

구조체를 했으니 이제는 구현해야하는 함수를 보게되면,

• 그래프의 생성
• 노드 추가
• 간선 추가
• 노드와 간선의 제거
• 그래프 Display

 

구현

#include "linkedlist.h"
typedef struct DirectLinkedGraphType
{
int nodeCount;
LinkedList** ppAdjEdge;
} DirectLinkedGraph;
DirectLinkedGraph* createDirectLinkedGraph(int nodeCount) // 그래프의 생성
{
int i = 0;
DirectLinkedGraph* pReturn = NULL;
if (nodeCount > 0) {
pReturn = (DirectLinkedGraph*)malloc(sizeof( DirectLinkedGraph));
if (pReturn == NULL) {
printf("오류, 메모리 할당(1), in createLinkedGraph()\n");
return NULL;
}
pReturn->nodeCount = nodeCount;
}
else {
printf("오류, 최대 노드 개수는 0보다 커야합니다\n");
return NULL;
}
pReturn->ppAdjEdge = (LinkedList**)malloc(sizeof(LinkedList*) * nodeCount);
if (pReturn->ppAdjEdge == NULL) {
printf("오류, 메모리 할당(3), in createLinkedGraph()\n");
if (pReturn != NULL) free(pReturn);
return NULL;
}
for (i = 0; i < nodeCount; ++i) {
pReturn->ppAdjEdge[i] = createLinkedList();
if (pReturn->ppAdjEdge[i] == NULL) {
printf("오류, 메모리 할당(4), in createLinkedGraph()\n");
if (pReturn->ppAdjEdge != NULL) free(pReturn->ppAdjEdge);
if (pReturn != NULL) free(pReturn);
return NULL;
}
}
return pReturn;
}
int checkVertexValid(DirectLinkedGraph* pGraph, int node)
{
if (pGraph != NULL && node >= 0 && node < pGraph->nodeCount) {
return 1;
}
else {
return 0;
}
}
int addEdgeDLG(DirectLinkedGraph* pGraph, int fromNode, int toNode) // 간선의 추가
{
int ret = 0;
if (pGraph != NULL
&& checkVertexValid(pGraph, fromNode)
&& checkVertexValid(pGraph, toNode)) {
addLinkedListData(pGraph->ppAdjEdge[fromNode], 0, toNode);
}
else {
ret = -1;
}
return ret;
}
int removeEdgeDLG(DirectLinkedGraph* pGraph, int fromNode, int toNode)
{
int ret = -1;
LinkedList* pList = NULL;
int i = 0, count = 0;
if (pGraph != NULL
&& checkVertexValid(pGraph, fromNode)
&& checkVertexValid(pGraph, toNode)) {
pList = pGraph->ppAdjEdge[fromNode];
count = getLinkedLength(pList);
for (i = 0; i < count; i++) {
if (getLinkedListData(pList, 1) == toNode) {
removeLinkedListData(pList, i);
ret = 0;
break;
}
}
}
else {
ret = -1;
}
return ret;
}
int getEdgeDLG(DirectLinkedGraph* pGraph, int fromNode, int toNode)
{
int ret = 0;
LinkedList* pList = NULL;
int i = 0, count = 0;
if (pGraph != NULL
&& checkVertexValid(pGraph, fromNode)
&& checkVertexValid(pGraph, toNode)) {
pList = pGraph->ppAdjEdge[fromNode];
count = getLinkedLength(pList);
for (i = 0; i < count; i++) {
if (getLinkedListData(pList, 1) == toNode) {
ret = 1;
break;
}
}
}
return ret;
}
void displayGraphDLG(DirectLinkedGraph* pGraph)
{
int i = 0, j = 0, count = 0;
if (pGraph != NULL) {
count = pGraph->nodeCount;
for (i = 0; i < count; i++) {
for (j = 0; j < count; j++) {
if (getEdgeDLG(pGraph, i, j)) {
printf("1 ");
}
else
printf("0 ");
}
printf("\n");
}
}
}
void deleteGraphDLG(DirectLinkedGraph* pGraph)
{
int i = 0;
if (pGraph != NULL) {
for (i = 0; i < pGraph->nodeCount; i++) {
deleteLinkedList(pGraph->ppAdjEdge[i]);
}
if (pGraph->ppAdjEdge != NULL) free(pGraph->ppAdjEdge);
free(pGraph);
}
}
int main(int argc, char* argv[])
{
int nodeCount = 6;
DirectLinkedGraph* pG2 = createDirectLinkedGraph(nodeCount);
if (pG2 != NULL) {
addEdgeDLG(pG2, 0, 1);
addEdgeDLG(pG2, 1, 2);
addEdgeDLG(pG2, 2, 0);
addEdgeDLG(pG2, 2, 3);
addEdgeDLG(pG2, 3, 2);
addEdgeDLG(pG2, 3, 4);
addEdgeDLG(pG2, 4, 5);
addEdgeDLG(pG2, 5, 3);
printf("G2 : 방향그래프\n");
displayGraphDLG(pG2);
deleteGraphDLG(pG2);
}
return 0;
}