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
#include <stdio.h>
#include <malloc.h>
 
typedef struct Node
{
    int Data;
    struct Node* NextNode;
}Node;
 
/*  노드 생성 */
Node* SLL_CreateNode(int NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
 
    NewNode->Data = NewData;  /*  데이터를 저장한다. */
    NewNode->NextNode = NULL; /*  다음 노드에 대한 포인터는 NULL로 초기화 한다. */
 
    return NewNode;/*  노드의 주소를 반환한다. */
}
 
/*  노드 소멸 */
void SLL_DestroyNode(Node* Node)
{
    free(Node);
}
 
/*  노드 추가 */
void SLL_AppendNode(Node** Head, Node* NewNode)
{
    /*  헤드 노드가 NULL이라면 새로운 노드가 Head */
    if ((*Head) == NULL)
    {
        *Head = NewNode;
    }
    else
    {
        /*  테일을 찾아 NewNode를 연결한다. */
        Node* Tail = (*Head);
        while (Tail->NextNode != NULL)
        {
            Tail = Tail->NextNode;
        }
 
        Tail->NextNode = NewNode;
    }
}
 
/*  노드 삽입 */
void SLL_InsertAfter(Node* Current, Node* NewNode)
{
    NewNode->NextNode = Current->NextNode;
    Current->NextNode = NewNode;
}
 
void  SLL_InsertNewHead(Node** Head, Node* NewHead)
{
    if (Head == NULL)
    {
        (*Head) = NewHead;
    }
    else
    {
        NewHead->NextNode = (*Head);
        (*Head) = NewHead;
    }
}
 
void SLL_InsertBefore(Node** Head, Node* Current, Node* NewHead)
{
    if ((*Head) == Current)
    {
        SLL_InsertNewHead(Head, NewHead);
    }
    else
    {
        Node *BeforeCurrent = *Head;
        while (BeforeCurrent != NULL && BeforeCurrent->NextNode != Current)
        {
            BeforeCurrent = BeforeCurrent->NextNode;
        }
 
        if (BeforeCurrent != NULL)
        {
            NewHead->NextNode = Current;
            BeforeCurrent->NextNode = NewHead;
        }
    }
}
 
/*  노드 제거 */
void SLL_RemoveNode(Node** Head, Node* Remove)
{
    if (*Head == Remove)
    {
        *Head = Remove->NextNode;
    }
    else
    {
        Node* Current = *Head;
        while (Current != NULL && Current->NextNode != Remove)
        {
            Current = Current->NextNode;
        }
 
        if (Current != NULL)
            Current->NextNode = Remove->NextNode;
    }
    
    //SLL_DestroyNode(Remove);
}
 
/*  노드 탐색 */
Node* SLL_GetNodeAt(Node* Head, int Location)
{
    Node* Current = Head;
 
    while (Current != NULL && (--Location) >= 0)
    {
        Current = Current->NextNode;
    }
 
    return Current;
}
 
/*  노드 수 세기 */
int SLL_GetNodeCount(Node* Head)
{
    int   Count = 0;
    Node* Current = Head;
 
    while (Current != NULL)
    {
        Current = Current->NextNode;
        Count++;
    }
 
    return Count;
}
 
void SLL_DestroyAllNodes(Node** List)
{
 
}
 
int main()
{
    return 0;
}
cs


저작자표시

크루스칼 알고리즘은 최소신장트리(Minimum Spanning Tree)를 구하는 알고리즘이다.



최소신장트리는 위의 그림과 같이 어떤 그래프가 있을 때, 각 노드들을 최소 비용으로, 트리 구조로 연결한 것을 말한다. 트리는 (노드의 수 - 1)개의 간선을 갖고, 싸이클이 생기지 않는 구조를 갖는다.


크루스칼 알고리즘의 순서는 다음과 같다.


1. 간선(Edge)을 비용이 적은 순서대로 정렬한다.

2. 정렬된 간선을 순서대로 추가하는데, 이 때 싸이클이 생기지 않도록 하는 간선만 추가한다.

3. 이를 간선의 수가 노드의 수 - 1 개가 될 때까지 반복한다.


어떤 간선을 추가했을 때 싸이클이 생기는지의 여부는 Disjoint sets(분리집합, 상호배타적집합)을 이용한다. Disjoint sets를 표현하기 위한 자료구조로 disjoint-set data structure를 이용한다. (union–find data structure, merge–find set 라고도 불린다.)


 



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
#include <stdio.h>
#include <malloc.h>
 
#define N 100
 
int distance[N][N];
int n;
int p[N];
int rank[N];
int sum;
 
typedef struct Edge
{
    int x, y, k;
}Edge;
 
Edge edge[N * N];
int cnt;
 
int FindSet(int x)
{
    if (p[x] == x) return x;
    else p[x] = FindSet(p[x]);
}
 
void CreateSet()
{
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
        rank[i] = 0;
    }
}
 
void MergeSet(int x, int y)
{
    x = FindSet(x);
    y = FindSet(y);
 
    if (rank[x] > rank[y])
    {
        p[y] = x;
    }
    else
    {
        p[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }
 
}
 
void Merge(Edge *arr, int left, int mid, int right)
{
    int l_idx = left;
    int r_idx = mid + 1;
    int idx = left;
    Edge *temp = (Edge *)malloc(sizeof(Edge) * (right + 1));
 
    while (l_idx <= mid && r_idx <= right)
    {
        if (arr[l_idx].k > arr[r_idx].k) temp[idx++] = arr[r_idx++];
        else temp[idx++] = arr[l_idx++];
    }
 
    while (l_idx <= mid) temp[idx++] = arr[l_idx++];
    while (r_idx <= right) temp[idx++] = arr[r_idx++];
 
    for (int i = left; i <= right; i++) arr[i] = temp[i];
    free(temp);
}
 
void MergeSort(Edge *arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}
 
int main()
{
    int i, j;
 
    //freopen("input.txt", "r", stdin);
 
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &distance[i][j]);
    
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (j > i)
            {
                edge[cnt].x = i;
                edge[cnt].y = j;
                edge[cnt++].k = distance[i][j];
            }
        }
    }
 
    MergeSort(edge, 0, cnt);
    CreateSet();
 
    i = j = 0;
    
    while (i < n - 1)
    {
        int u = FindSet(edge[j].x);
        int v = FindSet(edge[j].y);
 
        // 싸이클이 안생길 떼
        if (u != v)
        {
            MergeSet(u, v);
            sum += edge[j].k;
            i++;
        }
        j++;
    }
    printf("%d\n", sum);
 
    return 0;
}
cs


저작자표시


Disjoint Set은 상호배타적 집합을 나타내는 자료구조를 말한다. disjoint-set data structure, union–find data structure, merge–find set 이라고도 불린다. 


크게 초기화, Union(Merge) 연산, Find 연산으로 나뉜다. 

랭크에 의한 최적화(union-by-rank), 경로 압축 최적화(path compression)를 통해 Find연산의 시간 복잡도를 줄일 수 있다.



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
#include <stdio.h>
#define N 100
 
int p[N];        // Parent
int rank[N];    // 트리의 높이
 
int FindSet(int x)
{
    if (p[x] == x) return x;
    else return p[x] = FindSet(p[x]);
}
 
void CreateSet()
{
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
        rank[i] = 0;
    }
}
 
void MergeSet(int x, int y)
{
    x = FindSet(x);
    y = FindSet(y);
 
    if (rank[x] > rank[y])
    {
        p[y] = x;
    }
    else
    {
        p[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }
}
cs


저작자표시

+ Recent posts

티스토리툴바