반응형
728x90
반응형

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

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

 

C Data Structure - 그래프란?

드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의 정리이다. 그래프란? 먼

typingdog.tistory.com

 

 

C Data Structure - 연결 리스트

하 코딩해놓고 묵혀뒀다가 포스팅하느라 다시 보고 시간 버리는게 너무 아깝다 앞으로는 정말 열심히 바로바로 정리해서 올려야겠다. 그래도 다시 복습할 기회가 되었으니 의미있는 시간이라

typingdog.tistory.com

 

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

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

그래프 초기화 및 정점 추가

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

간선 추가 

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

그래프 출력

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

출력 결과는 다음과 같다.

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

그래프 소멸

 

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

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

---

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

그래프 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#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;
}
 cs

 

리스트 자료구조 헤더 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#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;
}
 
 
 cs
728x90
반응형
저작자표시

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 깊이 우선 탐색(Depth First Search Graph)  (0) 2021.01.29
C Data Structure - 땡땡 우선 탐색(Depth or Breadth First Search Graph)  (0) 2021.01.29
C Data Structure - 그래프란?  (0) 2021.01.28
C Data Structure - 이진 탐색 트리 4 (마지막)  (0) 2021.01.24
C Data Structure - 이진 탐색 트리 3  (0) 2021.01.24
728x90
반응형

드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의 정리이다.

그래프란?

먼저, 그래프란 아래의 설명과 같다.

비선형 자료구조, 즉, 트리 또한 그래프의 일종이라는 것을 알 수 있다!

이러한 그래프에는 간선의 방향성이라든가, 가중치, 부분 집합에 따라서 그래프의 종류가 나뉜다 이를 하나씩 나열해 볼 것이다.

무방향 / 방향 그래프

간선에 방향이 없고, 있고의 차이이다.

완전 그래프

정점 별로 모든 정점과 연결되어 있는 그래프를 완전 그래프라고 하는데, 이 때, 방향 완전 그래프는 무방향 완전 그래프보다 간선의 수가 2배 많다.

가중치 그래프와 부분 그래프

가중치 그래프는 간선에 가중치를 두고, 예를 들어, A에서 C로 가려면 3+1 혹은 4+5 비용이 든다고 표현할 수 있다. 부분 그래프는 말 그대로 그래프의 부분만을 그려낸 것이다.

그래프의 집합 표시

이러한 그래프를 집합 형태로 표현을 할 수 있다

그래프를 코드로 표현하기 위한 약속

그래프는 진짜 들쑥 날쑥인데 어떻게 표현하지 싶었는데, 사람들은 참 머리가 좋은 것 같다.

그래프가 어떻게 생겼든, 크기가 어떻든 정점 사이가 얼마나 멀든 좁든 간에 각 정점과 그 사이의 간선만 표현할 수 있다면, (예를 들어 어느 점과 어느 점이 어떤 선으로 연결되어 있는지 등의 정보) 오케이이다.

그 정점과 간선 등의 관계를 표현하는 방법은 위 그림에서처럼 인접 행렬, 인접 리스트가 그 방법이다. 방법은 그림으로 보는 것이 자세하고 편해서 그림으로 표현을 해 보았다.

728x90
반응형
저작자표시

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 땡땡 우선 탐색(Depth or Breadth First Search Graph)  (0) 2021.01.29
C Data Structure - 그래프의 기본  (0) 2021.01.28
C Data Structure - 이진 탐색 트리 4 (마지막)  (0) 2021.01.24
C Data Structure - 이진 탐색 트리 3  (0) 2021.01.24
C Data Structure - 이진 탐색 트리 2  (0) 2021.01.24

+ Recent posts

티스토리툴바