C Data Structure - 그래프의 기본

드디어 그래프의 기본 코드이다.

이전 포스팅에서 설명했듯이, 그래프를 표현하는 방법 중 인접 리스트 방법을 이용하여 기본적인 그래프를 구현해 볼 것이다. 그 인접 리스트에 해당하는 방법 또한 이미 이전에 포스팅 한 코드를 기반으로 만들 것이다. 해당 리스트 코드는 따로 첨부하도록 할 것이다.

C Data Structure - 그래프란?

 

C Data Structure - 연결 리스트

 

먼저, 그래프를 만드는데 있어서 연결 리스트 자료구조를 이용한다. 그래서.. 하 골치 아프게거니 하다가 C++ STL의 리스트를 그냥 활용할까 했는데, 그래도 내가 전에 만든거 테스트도 할 겸, 그걸로 하자! 라고 생각해서 내가 만든 리스트를 100% 신뢰하며 쓰기로 결정했다. 

이미 구현된 자료구조는 100% 신뢰하며 쓰는 것이 국룰이다.

그래프 초기화 및 정점 추가

그래프를 초기화 한다는 것은 코드 작성자 나름이고 기능에 따라 더 무언가 있겠지만, 나는 정점을 추가하는 용도로 사용되었다. 

간선 추가 

이런 식으로 간선이 연결되며 연결된 그래프의 모양은 대충 다음과 같다.

그래프 출력

각 정점 노드 별로 리스트 내에 제공하는 show 관련 함수를 이용하여 출력을 해주면 된다!

출력 결과는 다음과 같다.

리스트 구현할 때, 헤드 부분을 바보 같이 잘못 이해하고 잘못 구현했었다.. 그냥 가리키는 포인터로 두면 될 것을 노드로 처리해버려서.. 아무튼 노란 부분은 무시해도 전혀 문제 없다.

그래프 소멸

 

그래프가 겁나 어려울 줄 알았는데 생각보다 구현하기 쉬웠다. 다만 탐색에 대한 부분들이 들어가 있지 않기 때문에 모르고 하는 소리일 수 있으나, 진짜 생각했던 것 만큼 어렵지는 않다. 다만 그래프는 이전 자료구조들을 많이 활용하기 때문에 처음부터 구현하기에는 조금 까다로운 것은 사실이다.

다음 포스팅은 탐색에 대해서 하나하나 기록해볼 것이다.

---

코드들이다. 그래프 실행 결과는 이미 위에 있기 때문에 코드만 업로드한다.

그래프 코드

#include "NonPublishing/Graph/linkedlistforgraph.h"
 
struct DefaultGraph
{
    int vertex_number; // 정점의 수
    int edge_number; // 간선의 수
    ListManager* lm; // 간선을 관리하는 매니저들
};
typedef struct DefaultGraph dgraph;
 
void GraphInit(dgraph* graph, int vertex_number);
void AddEdge(dgraph* graph, int from, int to);
void ShowGraphEdgeInfo(dgraph* graph);
void DestroyGraph(dgraph* graph);
 
 
int main(void)
{
    dgraph graph;
    GraphInit(&graph, 5);
 
    //0 1 2 3 4
    AddEdge(&graph, 0, 1);
    AddEdge(&graph, 0, 3);
    AddEdge(&graph, 1, 2);
    AddEdge(&graph, 2, 3);
    AddEdge(&graph, 3, 4);
    AddEdge(&graph, 4, 0);
 
    ShowGraphEdgeInfo(&graph);
    DestroyGraph(&graph);
 
    return 0;
}
 
void GraphInit(dgraph* graph, int vertex_number)
{
    int i = 0;
    graph->vertex_number = vertex_number;
    graph->edge_number = 0;
    graph->lm = (ListManager*)malloc(sizeof(ListManager) * vertex_number);
 
    for (i = 0; i < vertex_number; i++)
        ListInit(&(graph->lm[i]));
 
    return;
}
 
void AddEdge(dgraph* graph, int from, int to)
{
    if ((from >= graph->vertex_number) || (to >= graph->vertex_number))
    {
        printf("초과된 vertex 값이 왔습니다. \n");
        return;
    }
 
    if (from == to)
    {
        printf("잘못된 vertex 값이 왔습니다. \n");
        return;
    }
 
    LInsert(&(graph->lm[from]), to);
    LInsert(&(graph->lm[to]), from);
    graph->edge_number++;
 
    return;
}
void ShowGraphEdgeInfo(dgraph* graph)
{
    int i = 0;
 
    for (i = 0; i < graph->vertex_number; i++)
    {
        printf("정점[%d] : ", i);
        ShowList(&(graph->lm[i]));
    }
    return;
}
 
void DestroyGraph(dgraph* graph)
{
    int i = 0;
 
    if (graph->lm == NULL)
        return;
 
    for (i = 0; i < graph->vertex_number; i++)
        DeleteList(&(graph->lm[i])); // 내부 연결된 노드를 모두 제거.
    free(graph->lm); // 접점들 자체를 제거.
 
    return;
}

 

리스트 자료구조 헤더 코드

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
 
struct ListNode {
    int data;
    struct ListNode* link;
};
 
struct ListManager
{
    struct ListNode* head;
    struct ListNode* ci; // current index; 
    struct ListNode* pi; // previous index;
 
    int node_count; // data 값이 유효한 node의 수
    int malloc_count; // 할당된 수
};
 
void ListInit(struct ListManager* lm);
void LInsert(struct ListManager* lm, int data);
int LFirst(struct ListManager* lm, int* data);
int LNext(struct ListManager* lm, int* data);
int LCount(struct ListManager* lm);
int LRemove(struct ListManager* lm);
 
void* CreateNodeMemory(struct ListManager* lm, int len);
void ShowList(struct ListManager* lm);
void DeleteNode(struct ListManager* lm, struct ListNode* target);
void DeleteList(struct ListManager* lm);
 
 
 
void ListInit(struct ListManager* lm)
{
    // count 초기화
    lm->node_count = 0;
    lm->malloc_count = 0;
 
    // head 다음으로 항상 유지하는 빈 노드 생성
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    new_node->data = -1;
    new_node->link = NULL; // 제일 끝이므로 무조건 NULL을 갖는다.
 
    // 연결리스트 헤드 초기화
    lm->head = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    lm->head->data = -1;
    lm->head->link = new_node;
 
    // 인덱스 초기화
    lm->ci = NULL;
    lm->pi = NULL;
 
    return;
}
 
void LInsert(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
 
    // head 다음의 빈 노드에 값을 반영, 링크는 건들지 않는다.
    lm->head->link->data = data;
 
    // empty_node 설정
    new_node->data = -1;
    new_node->link = lm->head->link;
    lm->head->link = new_node;
 
    lm->node_count++;
    return;
}
 
int LFirst(struct ListManager* lm, int* data)
{
    if (lm->node_count == 0)
    {
        printf("순회할 노드가 없습니다.\n");
        return false;
    }
    lm->ci = lm->head->link->link;
    lm->pi = lm->head->link;
 
    *data = lm->ci->data;
    return true;
}
 
int LNext(struct ListManager* lm, int* data)
{
    if (lm->ci->link == NULL)
        return false;
 
    lm->pi = lm->ci;
    lm->ci = lm->ci->link;
    *data = lm->ci->data;
    return true;
}
 
int LCount(struct ListManager* lm)
{
    return lm->node_count;
}
 
int LRemove(struct ListManager* lm)
{
    int remove_value = lm->ci->data;
    struct ListNode* rtarget = lm->ci;
 
    lm->pi->link = rtarget->link;
    lm->ci = lm->pi;
 
    DeleteNode(lm, rtarget);
    return remove_value;
}
 
void* CreateNodeMemory(struct ListManager* lm, int len)
{
    lm->malloc_count++;
    return (void*)malloc(len);
}
 
void ShowList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
 
    if (lm->malloc_count == 0)
    {
        printf("head와 new node 및 일반 node들까지 모두 존재하지 않습니다.");
        return;
    }
    else if (lm->node_count == 0)
        printf("추가된 노드는 모두 제거된 상태이지만, head와 new node가 존재하고 추가 가능한 상태입니다.\n");
 
    for (index_node = lm->head; index_node != NULL; index_node = index_node->link)
    {
        printf("[%d|%p]", index_node->data, index_node);
        if (index_node->link != NULL)
            printf("->");
    }
    fputc('\n', stdout);
    return;
}
 
void DeleteNode(struct ListManager* lm, struct ListNode* target)
{
    if (target->data != -1)
        lm->node_count--;
 
    free(target);
    lm->malloc_count--;
 
    return;
}
 
void DeleteList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
    struct ListNode* next_node = NULL;
    for (index_node = lm->head; index_node != NULL; index_node = next_node)
    {
        next_node = index_node->link;
        DeleteNode(lm, index_node);
    }
    if (lm->malloc_count != 0)
        printf("메모리 해체에 문제가 있습니다\n");
    return;
}