void Union_gm(int s1, int s2) { // s1, s2를 같은 집합으로 넣어준다.
int u, v;
int p1, p2, s;
int tmp;
u = s1;
while (parent[u] != -1) { // s1과 연결된 노드 중에 가장 처음 연결된 노드를 찾는다.
u = parent[u]; // 즉, 연결된 노드를 줄 세웠을 때 가장 앞에 있는 노드이다.
}
v = s2;
while (parent[v] != -1) { // s2도 동일한 방법으로 집합의 가장 처음 노드를 찾아준다.
v = parent[v];
}
if (num[u] >= num[v]) { // 이때, u와 v는 s1, s2 각각 연결된 노드 중 가장 앞의 노드이다.
p1 = u; // 딸린 노드가 더 많은 노드를 p1으로 설정한다.
p2 = v;
s = s2;
}
else {
p1 = v;
p2 = u;
s = s1;
}
parent[p2] = p1; // 딸린 자식이 더 많은 노드 (p1)의 집합으로 p2가 추가된다.
num[p1] += num[p2] + 1; // p1은 p2가 가진 자식 노드와 p2를 포함하게 된다.
while (parent[s] != -1) {
// s는 p2의 자식이었고, 아래와 같은 방법으로 자신과 연결된 모든 노드의 부모 노드를 p1으로 초기화해준다.
tmp = parent[s];
parent[s] = p1;
s = tmp;
}
}
void Link_Vertex_gm(int s1, int s2, int key) {
// s1, s2의 합집합 여부를 판단한 뒤, 그래프 추가를 결정한다.
int u, v;
u = s1;
while (parent[u] != -1) { // s1의 부모노드가 나올 때까지 반복한다.
u = parent[u];
}
v = s2;
while (parent[v] != -1) { // s2의 부모노드가 나올 때까지 반복한다.
v = parent[v];
}
if (u != v) { // 두 노드의 부모노드가 같이 않음 == 합집합이 아님 == 사이클을 형성하지 않음
Union_gm(s1, s2);
printf("Success Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
else {
printf("Fail Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
}
void Init_Graph(Heap* h, int n) {
// n을 최대값으로 갖는 랜덤 변수를 생성하고, 그 값을 가중치로 한 간선을 만든다.
srand((unsigned int)time(NULL));
int ran_num;
for (int i = 0; i < MAX_VERTEX; i++) {
for (int j = 0; j < MAX_VERTEX; j++) {
ran_num = (rand() % n) + 1;
printf("n = %d\n", h->n);
printf("Random number: %d\n", ran_num);
Insert_Edge(i, j, ran_num, h); // 만들어진 간선을 구조체로 묶어준다.
}
}
}
void Insert_Edge(int v1, int v2, int key, Heap* h) {
// 랜덤 변수와 함께 만들어진 간선을 구조체로 묶고, 최소 힙 트리에 추가한다.
Edge* e = (Edge*)malloc(sizeof(Edge));
e->v1 = v1;
e->v2 = v2;
e->key = key;
Input_Heap(e, h);
}
Heap* Init_Heap(void) {
Heap* h = (Heap*)malloc(sizeof(Heap));
h->n = 0; // 힙 트리 내에 저장된 데이터의 갯수를 초기화해준다.
return h;
}
void Input_Heap(Edge* e, Heap* h) {
int i;
i = ++(h->n);
while (i != 1 && e->key < h->heap[i / 2]->key) {
// 첫번째 데이터는 제외하고,
// 새로 들어온 간선의 가중치가 부모 노드의 가중치 보다 작을 때 반복문이 동작한다.
h->heap[i] = h->heap[i / 2];
// 새로 들어갈 자리에 부모 노드의 주소가 저장된다.
i /= 2;
// 부모 노드와 자식 노드의 위치 변경 후에 i를 부모 노드 자리로 갱신해준다.
// 위로 올라가면서 부모와 자식 관계가 제대로 정렬될 때까지 반복한다.
}
h->heap[i] = e;
}
Edge* Delete_Heap(Heap* h) { // 힙 트리의 정점에 있는 최소 가중치를 가진 간선 정보를 반환합니다.
int pr, ch;
Edge* re;
Edge* tmp;
re = h->heap[1]; // 무조건 가장 처음의 노드가 반환 (return) 됩니다.
tmp = h->heap[(h->n)--];
// 항상 트리의 가장 마지막 노드가 가장 처음 노드로 올라가고,
// 자식 노드와 크기를 비교하면서 부모-자식 관계가 바르게 정렬될 때 까지 내려갑니다.
pr = 1; // 부모 노드는 1
ch = 2; // 자식 노드는 2로 설정합니다.
while (ch <= h->n) { // 자식 노드가 트리 안에 있어야 합니다.
if (ch < h->n && h->heap[ch]->key > h->heap[ch + 1]->key)
// 여기선 자식 노드의 크기를 비교할 것입니다.
// 부모 노드보다 자식 노드의 크기가 더 작을 때
// 더 작은 자식 노드와 부모 노드의 자리가 변경되야 합니다.
// 따라서 ch < h->n 일 때 ch의 옆자리가 있기 때문에 자식 노드끼리 크기 비교가가능합니다.
// ch는 항상 짝수이고,
// 최소 힙 트리는 완전 이진 트리기 때문에 ch+1은 같은 부모를 공유하는 옆 자식 노드입니다.
// 따라서 ch가 크기가 더 크면, ch를 옆자리 자식 노드의 인덱스로 변경해줍니다.
ch++;
if (tmp->key <= h->heap[ch]->key)
break;
// tmp에는 가장 마지막 자리의 노드였던 노드의 가중치가 저장되어있습니다.
// tmp가 자신이 있는 위치의 자식 노드 보다 작을 때 정렬이 바르게 되어 있으므로
// 정렬을 중지합니다.
// tmp
// ch ch+1
// 위와 같이 세 노드는 관계를 이루고 있습니다.
h->heap[pr] = h->heap[ch]; // 위에서 정지 되지 않았으면, 자식을 위로 올려줍니다.
pr = ch;
ch *= 2;
// 이제 위로 올라간 노드의 자식과 크기 비교를 하기 위해 ch를 갱신해줍니다.
}
return re;
}
void Print_Heap(Heap* h) {
if (h->n != 0) {
printf("\n");
int n = 1;
for (int i = 1; i <= h->n; i++) {
printf("%3d ", h->heap[i]->key);
if (i == (int)pow(2, n) - 1) {
printf("\n");
n++;
}
}
printf("\n\n");
}
}
void Start_Kruskal(Heap* h) {
Edge* tmp;
Init_Union();
int n = h->n;
printf("n = %d\n", n);
for (int i = 0; i < n; i++) {
tmp = Delete_Heap(h);
// printf("Deleted_Value = %d\n", tmp->key);
// Print_Heap(h);
Link_Vertex_gm(tmp->v1, tmp->v2, tmp->key);
}
}
/*-----------ADT------------*/
void Init_Union(void); // parent와 num 배열을 초기화 한다.
void Union_gm(int s1, int s2); // s1, s2를 합집합으로 구성한다.
void Link_Vertex_gm(int s1, int s2, int key); // s1, s2의 합집합 여부를 검사한 뒤 그래프에추가한다.
/*--------------------------*/
void Init_Graph(Heap* h, int n); // n은 랜덤으로 생성되는 가중치의 최대값
// 그래프에 사용될 간선과 가중치를 랜덤으로 생성한 뒤, 최소 힙에 저장한다.
void Insert_Edge(int v1, int v2, int key, Heap* h); // 생성된 간선을 힙에 저장한다.
Heap* Init_Heap(void); // 최소 힙 트리를 구성하기 위한 구조체를 초기화 한다.
void Input_Heap(Edge* e, Heap* h); // 랜덤으로 생성된 간선을 최소 힙 트리에 저장하고 정렬한다.
Edge* Delete_Heap(Heap* h); // 트리에서 가장 작은 가중치를 가진 간선 주소를 반환한다.
void Print_Heap(Heap* h); // 트리 구성 여부를 확인하기 위한 함수
/*--------------------------*/
void Start_Kruskal(Heap* h);
// 가중치가 최소이고 현재 그래프의 정점들과 사이클을 이루지 않는 정점부터 그래프를 구성한다.
/*--------------------------*/
// main.c
// Graph_MST_Kruskal
//
// Created by 김경민 on 2020/04/16.
// Copyright © 2020 김경민. All rights reserved.
// Kruskal 알고리즘을 사용해 최소 신장 트리를 구성한다.
// Minimum Spanning Tree
#include <stdio.h> // 표준 입출력 함수 라이브러리를 제공한다.
#include <stdlib.h> // malloc, rand, srand
#include <time.h> // time
#include <math.h> // pow
#define MAX_VERTEX 10
/*-----------Graph-----------*/ // 그래프의 각 정점과 연결되는 정점의 정보를 저장하기 위한 구조체
typedef struct LIST {
int vx; // 정점의 번호를 저장한다.
struct LIST* link; // 정점과 연결되는 모든 정점의 데이터를 저장한다.
}List;
typedef struct GRAPH {
int n; // 그래프에 연결되어 있는 정점의 갯수를 반환한다.
List* adj_list[MAX_VERTEX]; // 헤드 정점을 기준으로 인접한 정점의 데이터를 저장한다.
}Graph;
/*---------------------------*/
/*----------Kruskal----------*/
typedef struct EDGE { // 간선과 연결된 정점 데이터와 가중치를 저장하기 위한 구조체
int v1;
int v2;
int key;
}Edge;
typedef struct HEAP { // 가장 적은 비용을 가진 간선부터 차례로 그래프 포함 여부를 판별하기 위해서사용된다.
int n;
Edge* heap[MAX_VERTEX * MAX_VERTEX];
}Heap;
/*--------------------------*/
/*-----------Union-----------*/
// 그래프에 추가될 정점이 사이클을 이루는지 판별하기 위한 합집합 여부 검사 함수이다.
int parent[MAX_VERTEX];
int num[MAX_VERTEX];
/*---------------------------*/
/*-----------ADT------------*/
void Init_Union(void); // parent와 num 배열을 초기화 한다.
void Union_gm(int s1, int s2); // s1, s2를 합집합으로 구성한다.
void Link_Vertex_gm(int s1, int s2, int key); // s1, s2의 합집합 여부를 검사한 뒤 그래프에추가한다.
/*--------------------------*/
void Init_Graph(Heap* h, int n); // n은 랜덤으로 생성되는 가중치의 최대값
// 그래프에 사용될 간선과 가중치를 랜덤으로 생성한 뒤, 최소 힙에 저장한다.
void Insert_Edge(int v1, int v2, int key, Heap* h); // 생성된 간선을 힙에 저장한다.
Heap* Init_Heap(void); // 최소 힙 트리를 구성하기 위한 구조체를 초기화 한다.
void Input_Heap(Edge* e, Heap* h); // 랜덤으로 생성된 간선을 최소 힙 트리에 저장하고 정렬한다.
Edge* Delete_Heap(Heap* h); // 트리에서 가장 작은 가중치를 가진 간선 주소를 반환한다.
void Print_Heap(Heap* h); // 트리 구성 여부를 확인하기 위한 함수
/*--------------------------*/
void Start_Kruskal(Heap* h);
// 가중치가 최소이고 현재 그래프의 정점들과 사이클을 이루지 않는 정점부터 그래프를 구성한다.
/*--------------------------*/
int main(void) {
Heap* h = Init_Heap();
Init_Graph(h, 300); //
Print_Heap(h);
#if 0
Edge* tmp;
for (int i = 0; i < MAX_VERTEX * MAX_VERTEX; i++) {
tmp = Delete_Heap(h);
printf("deleted_value %d -- %d = %d\n", tmp->v1, tmp->v2, tmp->key);
Print_Heap(h);
}
#endif
Start_Kruskal(h);
return 0;
}
void Init_Union(void) { // parent를 -1로 num은 0으로 초기화 한다.
for (int i = 0; i < MAX_VERTEX; i++) {
parent[i] = -1;
num[i] = 0;
}
}
void Union_gm(int s1, int s2) { // s1, s2를 같은 집합으로 넣어준다.
int u, v;
int p1, p2, s;
int tmp;
u = s1;
while (parent[u] != -1) { // s1과 연결된 노드 중에 가장 처음 연결된 노드를 찾는다.
u = parent[u]; // 즉, 연결된 노드를 줄 세웠을 때 가장 앞에 있는 노드이다.
}
v = s2;
while (parent[v] != -1) { // s2도 동일한 방법으로 집합의 가장 처음 노드를 찾아준다.
v = parent[v];
}
if (num[u] >= num[v]) { // 이때, u와 v는 s1, s2 각각 연결된 노드 중 가장 앞의 노드이다.
p1 = u; // 딸린 노드가 더 많은 노드를 p1으로 설정한다.
p2 = v;
s = s2;
}
else {
p1 = v;
p2 = u;
s = s1;
}
parent[p2] = p1; // 딸린 자식이 더 많은 노드 (p1)의 집합으로 p2가 추가된다.
num[p1] += num[p2] + 1; // p1은 p2가 가진 자식 노드와 p2를 포함하게 된다.
while (parent[s] != -1) {
// s는 p2의 자식이었고, 아래와 같은 방법으로 자신과 연결된 모든 노드의 부모 노드를 p1으로 초기화해준다.
tmp = parent[s];
parent[s] = p1;
s = tmp;
}
}
void Link_Vertex_gm(int s1, int s2, int key) {
// s1, s2의 합집합 여부를 판단한 뒤, 그래프 추가를 결정한다.
int u, v;
u = s1;
while (parent[u] != -1) { // s1의 부모노드가 나올 때까지 반복한다.
u = parent[u];
}
v = s2;
while (parent[v] != -1) { // s2의 부모노드가 나올 때까지 반복한다.
v = parent[v];
}
if (u != v) { // 두 노드의 부모노드가 같이 않음 == 합집합이 아님 == 사이클을 형성하지 않음
Union_gm(s1, s2);
printf("Success Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
else {
printf("Fail Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
}
void Init_Graph(Heap* h, int n) {
// n을 최대값으로 갖는 랜덤 변수를 생성하고, 그 값을 가중치로 한 간선을 만든다.
srand((unsigned int)time(NULL));
int ran_num;
for (int i = 0; i < MAX_VERTEX; i++) {
for (int j = 0; j < MAX_VERTEX; j++) {
ran_num = (rand() % n) + 1;
printf("n = %d\n", h->n);
printf("Random number: %d\n", ran_num);
Insert_Edge(i, j, ran_num, h); // 만들어진 간선을 구조체로 묶어준다.
}
}
}
void Insert_Edge(int v1, int v2, int key, Heap* h) {
// 랜덤 변수와 함께 만들어진 간선을 구조체로 묶고, 최소 힙 트리에 추가한다.
Edge* e = (Edge*)malloc(sizeof(Edge));
e->v1 = v1;
e->v2 = v2;
e->key = key;
Input_Heap(e, h);
}
Heap* Init_Heap(void) {
Heap* h = (Heap*)malloc(sizeof(Heap));
h->n = 0; // 힙 트리 내에 저장된 데이터의 갯수를 초기화해준다.
return h;
}
void Input_Heap(Edge* e, Heap* h) {
int i;
i = ++(h->n);
while (i != 1 && e->key < h->heap[i / 2]->key) {
// 첫번째 데이터는 제외하고,
// 새로 들어온 간선의 가중치가 부모 노드의 가중치 보다 작을 때 반복문이 동작한다.
h->heap[i] = h->heap[i / 2];
// 새로 들어갈 자리에 부모 노드의 주소가 저장된다.
i /= 2;
// 부모 노드와 자식 노드의 위치 변경 후에 i를 부모 노드 자리로 갱신해준다.
// 위로 올라가면서 부모와 자식 관계가 제대로 정렬될 때까지 반복한다.
}
h->heap[i] = e;
}
#if 0 // 동일한 최소 힙 트리 알고리즘이지만, 좀 더 직관적입니다.
void Input_Heap(Edge* e, Heap* h) {
if (h->n == 0) {
h->n++;
h->heap[h->n] = e;
}
else {
h->n++;
h->heap[h->n] = e;
int i = h->n;
Edge* tmp;
while (h->heap[i]->key < h->heap[i / 2]->key) {
tmp = h->heap[i / 2];
h->heap[i / 2] = h->heap[i];
h->heap[i] = tmp;
i = i / 2;
if (i == 1)
break;
}
}
}
#endif
Edge* Delete_Heap(Heap* h) { // 힙 트리의 정점에 있는 최소 가중치를 가진 간선 정보를 반환합니다.
int pr, ch;
Edge* re;
Edge* tmp;
re = h->heap[1]; // 무조건 가장 처음의 노드가 반환 (return) 됩니다.
tmp = h->heap[(h->n)--];
// 항상 트리의 가장 마지막 노드가 가장 처음 노드로 올라가고,
// 자식 노드와 크기를 비교하면서 부모-자식 관계가 바르게 정렬될 때 까지 내려갑니다.
pr = 1; // 부모 노드는 1
ch = 2; // 자식 노드는 2로 설정합니다.
while (ch <= h->n) { // 자식 노드가 트리 안에 있어야 합니다.
if (ch < h->n && h->heap[ch]->key > h->heap[ch + 1]->key)
// 여기선 자식 노드의 크기를 비교할 것입니다.
// 부모 노드보다 자식 노드의 크기가 더 작을 때
// 더 작은 자식 노드와 부모 노드의 자리가 변경되야 합니다.
// 따라서 ch < h->n 일 때 ch의 옆자리가 있기 때문에 자식 노드끼리 크기 비교가가능합니다.
// ch는 항상 짝수이고,
// 최소 힙 트리는 완전 이진 트리기 때문에 ch+1은 같은 부모를 공유하는 옆 자식 노드입니다.
// 따라서 ch가 크기가 더 크면, ch를 옆자리 자식 노드의 인덱스로 변경해줍니다.
ch++;
if (tmp->key <= h->heap[ch]->key)
break;
// tmp에는 가장 마지막 자리의 노드였던 노드의 가중치가 저장되어있습니다.
// tmp가 자신이 있는 위치의 자식 노드 보다 작을 때 정렬이 바르게 되어 있으므로
// 정렬을 중지합니다.
// tmp
// ch ch+1
// 위와 같이 세 노드는 관계를 이루고 있습니다.
h->heap[pr] = h->heap[ch]; // 위에서 정지 되지 않았으면, 자식을 위로 올려줍니다.
pr = ch;
ch *= 2;
// 이제 위로 올라간 노드의 자식과 크기 비교를 하기 위해 ch를 갱신해줍니다.
}
return re;
}
#if 0 // 마찬가지로 위 함수와 동일한 역할을 하지만, 보다 직관적입니다.
Edge* Delete_Heap(Heap* h) {
Edge* re;
re = h->heap[1];
h->heap[1] = h->heap[h->n--];
int i = 1;
Edge* tmp;
int u;
while (1) {
if (2 * i > h->n) {
break;
}
else {
u = 2 * i;
if (2 * i + 1 <= h->n) {
if (h->heap[2 * i]->key >= h->heap[2 * i + 1]->key) {
u = 2 * i + 1;
}
}
if (h->heap[i]->key > h->heap[u]->key) {
tmp = h->heap[u];
h->heap[u] = h->heap[i];
h->heap[i] = tmp;
i = u;
}
else {
break;
}
}
}
return re;
}
#endif
void Print_Heap(Heap* h) {
if (h->n != 0) {
printf("\n");
int n = 1;
for (int i = 1; i <= h->n; i++) {
printf("%3d ", h->heap[i]->key);
if (i == (int)pow(2, n) - 1) {
printf("\n");
n++;
}
}
printf("\n\n");
}
}
void Start_Kruskal(Heap* h) {
Edge* tmp;
Init_Union();
int n = h->n;
printf("n = %d\n", n);
for (int i = 0; i < n; i++) {
tmp = Delete_Heap(h);
// printf("Deleted_Value = %d\n", tmp->key);
// Print_Heap(h);
Link_Vertex_gm(tmp->v1, tmp->v2, tmp->key);
}
}
아아아아아아아아아아아아아아아아아아아아아아아아아아
/*-------Lecture Note-------*/
int get_min_vertex(int n) // 선택된 애들이 아닌 애들 중에 가장 dist가 작은 애를 반환한다.
{
int v, i;
v = -1;
for (i = 0; i < n; i++)
if (!selected[i]) { // 그래프에 선택된 정점이 아닌 걸 발견할 때까지 반복합니다.
v = i;
break;
}
for (i = 0; i < n; i++)
if (!selected[i] && (dist[i] < dist[v])) // 선택되지 않은 간선 중에 더 작은 간선이 발견될때까지 반복한다.
v = i;
return v;
}
void prim(Edge* e, int s, int n) // s는 시작점, n은 전체 갯수
{
int i, u, v;
for (u = 0; u < n; u++){
dist[u] = INF;
selected[u] = 0;
}
dist[s] = 0;
for (i = 0; i < n; i++) {
u = get_min_vertex(n); // 무조건 처음엔 시작 정점이 선택된다.
selected[u] = 1; // 항상 그래프의 모든 정점 중에 선택되지 않고, 제일 가중치가 작은 정점이선택된다.
if (dist[u] == INF) // 위에서 선택된 애가 제일 작은데 무한대면, 반복문을 중지 합니다.
return;
printf("%d ", u);
for (v = 0; v < n; v++)
if (e->key[u][v] != INF) // 시작 정점과 다른 정점이 끊기지 않고,
if (!selected[v] && e->key[u][v] < dist[v])
// 이전에 선택된 적이 없고, 다른 가중치보다 시작점에서 가는게 빠를 때
dist[v] = e->key[u][v]; // 시작점에서 가는걸 dist로 갱신한다.
// 이걸 시작점과 모든 정점에 대해 진행한다.
// 자연스럽게 끊긴 애들은 무한대가 유지되어 위에 if문으로 제외된다.
}
printf("\n\n");
}
/*--------------------------*/
Edge* Init_Edge(int max_vertex) {// MAX_VERTEX*MAX_VERTEX 크기의 key 행렬 생성
Edge* e;
e = (Edge*)malloc(sizeof(Edge));
e->n = 0;
e->key = (int**)malloc(sizeof(int*) * max_vertex);
// 이중 포인터를 이중 배열로 사용하기 위해 메모리를 할당한다.
// 즉, 10x10 배열을 사용할 때, 10개의 행을 만들어주는 것과 같다.
for (int i = 0; i < max_vertex; i++) {
e->key[i] = (int*)malloc(sizeof(int) * max_vertex);
// 여기선 각 행 마다 10개의 열을 만들어주는 것과 같다.
memset(e->key[i], 0, sizeof(int) * max_vertex);
// 할당된 메모리를 NULL로 초기화 해준다.
}
return e;
}
void Insert_Edge(Edge* e, int v1, int v2, int weight) {
// 랜덤하게 생성된 가중치를 이용해, v1과 v2를 잇는 간선 정보를 설정한다.
e->key[v1][v2] = weight;
e->key[v2][v1] = weight;
}
void Init_Graph(Edge* e, int n) {
srand((unsigned int)time(NULL));
int ran_num;
for (int i = 0; i < MAX_VERTEX; i++) {
for (int j = i; j < MAX_VERTEX; j++) {
if (j != i) { // i, j를 잇는 간선 정보를 생성한다.
// i->j 가 한번 생기고, j->i가 또 한번 생기는데
// 결국 후자로 초기화된다
ran_num = (rand() % n) + 1;
printf("[%d] and [%d]: %d\n", i, j, ran_num);
Insert_Edge(e, i, j, ran_num);
}
else { // 같은 정점에 대한 간선은 없으므로, 가중치를 0으로 설정한다.
printf("[%d] and [%d]: %d\n", i, j, 0);
Insert_Edge(e, i, j, 0);
}
}
printf("Finish [%d]\n\n", i);
}
printf("\nInit graph complete\n\n");
}
int Check_Weight(Edge* e, int v1, int v2) {
int tmp;
tmp = e->key[v1][v2];
return tmp;
}
void Prim(Edge* e, int start_vertex) {
int u = start_vertex;
if (e->n == 0) {
Add_Queue(u); // start_vertex를 큐에 저장한다.
e->n++;
Prim(e, start_vertex); // 다시 prim을 실행한다. (재귀함수)
}
else if (e->n <= MAX_VERTEX) {
int a;
int cur;
int tmp = 1000;
int tmp1;
int v1, v2;
int cnt;
for (int i = 0; i < e->n; i++) {
// e->n까지 큐에 있는 데이터를 가져온다.
// 즉, 큐에 있는 모든 데이터가 나올 때까지 반복한다.
a = Delete_Queue();
for (int j = 0; j < MAX_VERTEX; j++) { // 모든 정점에 대해 큐에서 나온 정점과의가중치를 검사한다.
if (j != a) { // 당연히 본인을 제외하고
cur = Check_Weight(e, a, j); // 가중치를 반환하고
if (cur < tmp) { // 최솟값을 찾기 위해 검사 이전까지의 최소값과 비교한다.
v1 = a;
v2 = j;
tmp = cur; // 최소값을 갱신해준다.
}
}
}
Add_Queue(a); // 사용했던 걸 다시 큐에 넣어준다
// 나중에 연결된 모든 정점에 대해 또 검사를 해줘야하기 때문에 빼냈던 데이터를 다시 큐에저장한다.
}
printf("[%d] and [%d] are connected: %3d\n", v1, v2, e->key[v1][v2]);
Add_Queue(v2); // 최소 가중치를 가졌던 정점을 큐에 추가한다. (그래프에도 추가된다는 의미를가진다.)
e->n++;
Insert_Edge(e, v1, v2, 1000); // 한번 연결된 간선을 다시 검사하지 않기 위해, 가중치를증가시킨다.
// 한번 선택된 간선은 다시 선택되지 않도록 가중치를 높여준다.
Prim(e, start_vertex); // 마찬가지로 재귀 함수를 활용한다.
}
}
// 항상 front가 가리키는 배열은 비어있다.
void Add_Queue(int n) {
if ((rear + 1) % MAX_QUEUE == front) {
// puts("Queue is full.");
}
else {
rear = (rear + 1) % MAX_QUEUE;
queue[rear] = n; // 1번부터 찬다.
}
}
int Delete_Queue(void) {
int tmp = -1;
if (front == rear) {
// puts("Queue is empty.");
}
else {
front = (front + 1) % MAX_QUEUE;
tmp = queue[front];
}
return tmp;
}
/*---------Graph ADT---------*/
Edge* Init_Edge(int max_vertex); // 이중 포인터를 사용하기 위해 초기화 한다.
void Insert_Edge(Edge* e, int v1, int v2, int weight); // 생성된 랜덤 가중치를 사용해 간선정보를 설정한다.
void Init_Graph(Edge* e, int n); // n을 최대값으로 갖는 랜덤 변수를 생성하고, 간선 정보를 생성한다.
int Check_Weight(Edge* e, int v1, int v2); // 특정 간선의 가중치를 반환한다.
void Prim(Edge* e, int start_vertex); // Prim 알고리즘을 실행한다.
/*---------------------------*/
void Add_Queue(int n); // Prim 알고리즘에서 그래프에 추가된 모든 정점이 큐에 저장됐다가 하나씩 빠져나오며연결된 최소의 간선을 찾는다
int Delete_Queue(void); // 큐에 저장된 데이터를 반환한다.
/*---------------------------*/
// main.c
// Graph_MST_Prim
//
// Created by 김경민 on 2020/04/16.
// Copyright © 2020 김경민. All rights reserved.
//
// Prim 알고리즘을 사용하여 MST를 구현한다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h> // memset
#define MAX_VERTEX 10
#define MAX_QUEUE 11
#define INF 1000L
/*------------Prim------------*/
typedef struct EDGE {
int n;
int** key;
}Edge;
/*----------------------------*/
/*---------Graph ADT---------*/
Edge* Init_Edge(int max_vertex); // 이중 포인터를 사용하기 위해 초기화 한다.
void Insert_Edge(Edge* e, int v1, int v2, int weight); // 생성된 랜덤 가중치를 사용해 간선정보를 설정한다.
void Init_Graph(Edge* e, int n); // n을 최대값으로 갖는 랜덤 변수를 생성하고, 간선 정보를 생성한다.
int Check_Weight(Edge* e, int v1, int v2); // 특정 간선의 가중치를 반환한다.
void Prim(Edge* e, int start_vertex); // Prim 알고리즘을 실행한다.
/*---------------------------*/
void Add_Queue(int n); // Prim 알고리즘에서 그래프에 추가된 모든 정점이 큐에 저장됐다가 하나씩 빠져나오며연결된 최소의 간선을 찾는다
int Delete_Queue(void); // 큐에 저장된 데이터를 반환한다.
/*---------------------------*/
/*-----------Queue-----------*/
int front = 0;
int rear = 0;
int queue[MAX_QUEUE];
/*---------------------------*/
/*-------Lecture Note-------*/
// 강의 노트에 있는 Prim 알고리즘
int selected[MAX_VERTEX];
int dist[MAX_VERTEX];
int get_min_vertex(int n);
void prim(int s, int n);
/*--------------------------*/
int main(void) {
Edge* e = Init_Edge(MAX_VERTEX);
Init_Graph(e, 300);
#if 0
int v1 = 0;
int v2 = 0;
printf("[%d] and [%d]'s key: %d\n", v1, v2, e->key[v1][v2]);
printf("[%d] and [%d]'s key: %d\n", v2, v1, e->key[v2][v1]);
#endif
prim(e, 0, MAX_VERTEX);
Prim(e, 0);
// printf("%d\n", 1000L);
return 0;
}
/*-------Lecture Note-------*/
int get_min_vertex(int n) // 선택된 애들이 아닌 애들 중에 가장 dist가 작은 애를 반환한다.
{
int v, i;
v = -1;
for (i = 0; i < n; i++)
if (!selected[i]) { // 그래프에 선택된 정점이 아닌 걸 발견할 때까지 반복합니다.
v = i;
break;
}
for (i = 0; i < n; i++)
if (!selected[i] && (dist[i] < dist[v])) // 선택되지 않은 간선 중에 더 작은 간선이 발견될때까지 반복한다.
v = i;
return v;
}
void prim(Edge* e, int s, int n) // s는 시작점, n은 전체 갯수
{
int i, u, v;
for (u = 0; u < n; u++){
dist[u] = INF;
selected[u] = 0;
}
dist[s] = 0;
for (i = 0; i < n; i++) {
u = get_min_vertex(n); // 무조건 처음엔 시작 정점이 선택된다.
selected[u] = 1; // 항상 그래프의 모든 정점 중에 선택되지 않고, 제일 가중치가 작은 정점이선택된다.
if (dist[u] == INF) // 위에서 선택된 애가 제일 작은데 무한대면, 반복문을 중지 합니다.
return;
printf("%d ", u);
for (v = 0; v < n; v++)
if (e->key[u][v] != INF) // 시작 정점과 다른 정점이 끊기지 않고,
if (!selected[v] && e->key[u][v] < dist[v])
// 이전에 선택된 적이 없고, 다른 가중치보다 시작점에서 가는게 빠를 때
dist[v] = e->key[u][v]; // 시작점에서 가는걸 dist로 갱신한다.
// 이걸 시작점과 모든 정점에 대해 진행한다.
// 자연스럽게 끊긴 애들은 무한대가 유지되어 위에 if문으로 제외된다.
}
printf("\n\n");
}
/*--------------------------*/
Edge* Init_Edge(int max_vertex) {// MAX_VERTEX*MAX_VERTEX 크기의 key 행렬 생성
Edge* e;
e = (Edge*)malloc(sizeof(Edge));
e->n = 0;
e->key = (int**)malloc(sizeof(int*) * max_vertex);
// 이중 포인터를 이중 배열로 사용하기 위해 메모리를 할당한다.
// 즉, 10x10 배열을 사용할 때, 10개의 행을 만들어주는 것과 같다.
for (int i = 0; i < max_vertex; i++) {
e->key[i] = (int*)malloc(sizeof(int) * max_vertex);
// 여기선 각 행 마다 10개의 열을 만들어주는 것과 같다.
memset(e->key[i], 0, sizeof(int) * max_vertex);
// 할당된 메모리를 NULL로 초기화 해준다.
}
return e;
}
void Insert_Edge(Edge* e, int v1, int v2, int weight) {
// 랜덤하게 생성된 가중치를 이용해, v1과 v2를 잇는 간선 정보를 설정한다.
e->key[v1][v2] = weight;
e->key[v2][v1] = weight;
}
void Init_Graph(Edge* e, int n) {
srand((unsigned int)time(NULL));
int ran_num;
for (int i = 0; i < MAX_VERTEX; i++) {
for (int j = i; j < MAX_VERTEX; j++) {
if (j != i) { // i, j를 잇는 간선 정보를 생성한다.
// i->j 가 한번 생기고, j->i가 또 한번 생기는데
// 결국 후자로 초기화된다
ran_num = (rand() % n) + 1;
printf("[%d] and [%d]: %d\n", i, j, ran_num);
Insert_Edge(e, i, j, ran_num);
}
else { // 같은 정점에 대한 간선은 없으므로, 가중치를 0으로 설정한다.
printf("[%d] and [%d]: %d\n", i, j, 0);
Insert_Edge(e, i, j, 0);
}
}
printf("Finish [%d]\n\n", i);
}
printf("\nInit graph complete\n\n");
}
int Check_Weight(Edge* e, int v1, int v2) {
int tmp;
tmp = e->key[v1][v2];
return tmp;
}
void Prim(Edge* e, int start_vertex) {
int u = start_vertex;
if (e->n == 0) {
Add_Queue(u); // start_vertex를 큐에 저장한다.
e->n++;
Prim(e, start_vertex); // 다시 prim을 실행한다. (재귀함수)
}
else if (e->n <= MAX_VERTEX) {
int a;
int cur;
int tmp = 1000;
int tmp1;
int v1, v2;
int cnt;
for (int i = 0; i < e->n; i++) {
// e->n까지 큐에 있는 데이터를 가져온다.
// 즉, 큐에 있는 모든 데이터가 나올 때까지 반복한다.
a = Delete_Queue();
for (int j = 0; j < MAX_VERTEX; j++) { // 모든 정점에 대해 큐에서 나온 정점과의가중치를 검사한다.
if (j != a) { // 당연히 본인을 제외하고
cur = Check_Weight(e, a, j); // 가중치를 반환하고
if (cur < tmp) { // 최솟값을 찾기 위해 검사 이전까지의 최소값과 비교한다.
v1 = a;
v2 = j;
tmp = cur; // 최소값을 갱신해준다.
}
}
}
Add_Queue(a); // 사용했던 걸 다시 큐에 넣어준다
// 나중에 연결된 모든 정점에 대해 또 검사를 해줘야하기 때문에 빼냈던 데이터를 다시 큐에저장한다.
}
printf("[%d] and [%d] are connected: %3d\n", v1, v2, e->key[v1][v2]);
Add_Queue(v2); // 최소 가중치를 가졌던 정점을 큐에 추가한다. (그래프에도 추가된다는 의미를가진다.)
e->n++;
Insert_Edge(e, v1, v2, 1000); // 한번 연결된 간선을 다시 검사하지 않기 위해, 가중치를증가시킨다.
// 한번 선택된 간선은 다시 선택되지 않도록 가중치를 높여준다.
Prim(e, start_vertex); // 마찬가지로 재귀 함수를 활용한다.
}
}
// 항상 front가 가리키는 배열은 비어있다.
void Add_Queue(int n) {
if ((rear + 1) % MAX_QUEUE == front) {
// puts("Queue is full.");
}
else {
rear = (rear + 1) % MAX_QUEUE;
queue[rear] = n; // 1번부터 찬다.
}
}
int Delete_Queue(void) {
int tmp = -1;
if (front == rear) {
// puts("Queue is empty.");
}
else {
front = (front + 1) % MAX_QUEUE;
tmp = queue[front];
}
return tmp;
}
여기까지 MST입니다 123123
아아아아아아아아아아아아아아아아아아아아아아아아아아
int choose(int distance[], int n, int found[]) {
int min;
int min_pos;
min = INT_MAX;
min_pos = -1;
for (int i = 0; i < n; i++) {
if (distance[i] < min && found[i] == FALSE) {
min = distance[i];
min_pos = i;
}
}
return min_pos;
}
void shortest_path(int start, int n) { // daijkstra 알고리즘으로 최단 경로를 구한다.
// 해당 알고리즘은 특정한 시작 정점으로 부터 각 정점까지 가는 최단 경로를 구합니다.
for (int i = 0; i < n; i++) {
distance[i] = weight[start][I]; // 시작 정점으로부터 다른 모든 정점까지의 거리로초기화해줍니다.
found[i] = FALSE; // found도 0으로 초기화해줍니다.
}
found[start] = TRUE; // 시작 정점을 고려하지 않기 위해 미리 발견됐다고 설정해줍니다.
for (int i = 0; i < n - 1; i++) {
int u = choose(distance, n, found); // 아직 찾아지지 않고, 시작 정점과 거리가 가장 짧은노드를 반환합니다.
found[u] = TRUE; // 찾아졌으니까 found를 1로 업데이트
printf("found u = %d\n", u);
for (int j = 0; j < n; j++) {
if (found[j] == FALSE) { // 현재까지 찾아진 노드가 아닌 애들에 대해서
if (distance[u] + weight[u][j] < distance[j]) {
// 시작 정점에서 j로 바로 가는게 빠를지, u를 거쳐서 가는게 빠를지 판단 합니다.
printf("Before_distance update: distance[%d] = %d\n", j, distance[j]);
distance[j] = distance[u] + weight[u][j];
printf("After_distance update: distance[%d] = %d\n", j, distance[j]);
}
}
}
}
}
void shortest_path2(void) { // Floyd 알고리즘으로 최단 경로를 구한다.
// 해당 알고리즘은 모든 정점간의 최다 경로를 구합니다.
int d[MAX_VERTICES][MAX_VERTICES];
for (int u = 0; u < MAX_VERTICES; u++) {
for (int v = 0; v < MAX_VERTICES; v++) {
d[u][v] = weight[u][v];
}
}
for (int m = 0; m < MAX_VERTICES; m++) { // m이 기준이 됩니다.
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
if (d[i][j] > d[i][m] + d[m][j]) {
// i에서 j로 바로 가는게 빠를지, m을 거쳐서 가는게 빠를지 판단합니다.
// m을 거쳐서 가는게 빠르다면, 아래 d[i][j] 업데이트 후 d[i][j]의 의미는 i->m->j를내포합니다.
printf("Before_distance update: distance[%d][%d] = %d\n", i, j, d[i][j]);
d[i][j] = d[i][m] + d[m][j];
printf("After_distance update: distance[%d][%d] = %d\n\n", i, j, d[i][j]);
}
}
}
}
}
// main.c
// Graph_Shortest_Path_Daijkstra_And_Floyd
//
// Created by 김경민 on 2020/04/20.
// Copyright © 2020 김경민. All rights reserved.
//
// 최단 경로 탐색 알고리즘을 구현한다.
// choose 함수에 우선 순위 큐를 사용하면 효율을 높일 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define INT_MAX 2147483647 // 최대 정수
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 4 // 정점의 수
#define INF 1000 // 무한대 (연결이 없는 경우)
//int weight[MAX_VERTICES][MAX_VERTICES] = {
// {0,7,INF,INF,3,10,INF},
// {7,0,4,10,2,6,INF},
// {INF,4,0,2,INF,INF,INF},
// {INF,10,2,0,11,9,4},
// {3,2,INF,11,0,INF,5},
// {10,6,INF,9,INF,0,INF},
// {INF,INF,INF,4,5,INF,0}
//};
int weight[4][4] = {
{0,1,8,INF},
{1,0,7,2},
{8,7,0,3},
{INF,2,3,0}
};
int distance[MAX_VERTICES];
int found[MAX_VERTICES];
int choose(int distance[], int n, int found[]) {
int min;
int min_pos;
min = INT_MAX;
min_pos = -1;
for (int i = 0; i < n; i++) {
if (distance[i] < min && found[i] == FALSE) {
min = distance[i];
min_pos = i;
}
}
return min_pos;
}
void shortest_path(int start, int n) { // daijkstra 알고리즘으로 최단 경로를 구한다.
// 해당 알고리즘은 특정한 시작 정점으로 부터 각 정점까지 가는 최단 경로를 구합니다.
for (int i = 0; i < n; i++) {
distance[i] = weight[start][I]; // 시작 정점으로부터 다른 모든 정점까지의 거리로초기화해줍니다.
found[i] = FALSE; // found도 0으로 초기화해줍니다.
}
found[start] = TRUE; // 시작 정점을 고려하지 않기 위해 미리 발견됐다고 설정해줍니다.
for (int i = 0; i < n - 1; i++) {
int u = choose(distance, n, found); // 아직 찾아지지 않고, 시작 정점과 거리가 가장 짧은노드를 반환합니다.
found[u] = TRUE; // 찾아졌으니까 found를 1로 업데이트
printf("found u = %d\n", u);
for (int j = 0; j < n; j++) {
if (found[j] == FALSE) { // 현재까지 찾아진 노드가 아닌 애들에 대해서
if (distance[u] + weight[u][j] < distance[j]) {
// 시작 정점에서 j로 바로 가는게 빠를지, u를 거쳐서 가는게 빠를지 판단 합니다.
printf("Before_distance update: distance[%d] = %d\n", j, distance[j]);
distance[j] = distance[u] + weight[u][j];
printf("After_distance update: distance[%d] = %d\n", j, distance[j]);
}
}
}
}
}
void shortest_path2(void) { // Floyd 알고리즘으로 최단 경로를 구한다.
// 해당 알고리즘은 모든 정점간의 최다 경로를 구합니다.
int d[MAX_VERTICES][MAX_VERTICES];
for (int u = 0; u < MAX_VERTICES; u++) {
for (int v = 0; v < MAX_VERTICES; v++) {
d[u][v] = weight[u][v];
}
}
for (int m = 0; m < MAX_VERTICES; m++) { // m이 기준이 됩니다.
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
if (d[i][j] > d[i][m] + d[m][j]) {
// i에서 j로 바로 가는게 빠를지, m을 거쳐서 가는게 빠를지 판단합니다.
// m을 거쳐서 가는게 빠르다면, 아래 d[i][j] 업데이트 후 d[i][j]의 의미는 i->m->j를내포합니다.
printf("Before_distance update: distance[%d][%d] = %d\n", i, j, d[i][j]);
d[i][j] = d[i][m] + d[m][j];
printf("After_distance update: distance[%d][%d] = %d\n\n", i, j, d[i][j]);
}
}
}
}
}
int main(void) {
for (int i = 0; i < MAX_VERTICES; i++) {
printf("B_distance[%d] = %d\n", i, distance[i]);
}
// shortest_path(0, MAX_VERTICES);
shortest_path2();
printf("\n");
for (int i = 0; i < MAX_VERTICES; i++) {
printf("A_distance[%d] = %d\n", i, distance[i]);
}
return 0;
}
아아아아아아아아아아아아아아아아아아아아아아아아아아
Headnodes graph[MAX_VERTICES];
Headnodes inverted_graph[MAX_VERTICES];
/*-----------ADT------------*/
void Init_Headnodes(void);
Node* Init_Vertex(int vertex);
void Input_Head_2_Node(int u, int v);
void Activity_On_Vertex(void);
void Cal_EST(void);
void Inverting_Graph(void);
void Cal_LST(void);
/*--------------------------*/
void Init_Headnodes(void) {
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i].count = 0;
graph[i].weight= 0;
graph[i].EST = 0;
graph[i].link = NULL;
}
}
Node* Init_Vertex(int vertex) {
Node* tmp = (Node*)malloc(sizeof(Node));
tmp->vertex = vertex;
tmp->link = NULL;
return tmp;
}
void Input_Head_2_Node(int u, int v) { // 헤드 노드에서 다른 노드로 가는 경로를 이어줍니다.
Node* cur = Init_Vertex(v);
Node* tmp;
tmp = graph[u].link; // tmp는 기존에 헤드 노드에 연결되어있던 노드입니다.
graph[u].link = cur; // 헤드 노드에 현재 이어주고자 하는 노드를 연결해주고
cur->link = tmp; // 현재 이어주고자 하는 노드 뒤에 기존에 헤드 노드에 연결되어 있던 노드를연결해줍니다.
graph[v].count++; // 연결이 된 정점의 count를 증가시켜준다.
// count는 해당 노드가 다른 노드에 연결된 갯수를 저장합니다.
// 즉, 헤드 노드 u가 아닌 헤드 노드 v의 count를 증가시켜줍니다.
}
/*--------Stack---------*/
int top = -1;
int stack[MAX_VERTICES];
void Input_Stack(int n) {
if (top == MAX_VERTICES) {
printf("Stack is full\n");
}
else {
stack[++top] = n;
printf("Input stack[%d] = %d\n", top, n);
}
}
int Delete_Stack(void) {
int n = -1;
if (top == -1) {
printf("Stack is empty\n");
}
else {
n = stack[top--];
printf("Deleted stack[%d] = %d\n", top + 1, n);
}
return n;
}
/*----------------------*/
void Activity_On_Vertex(void) { // aov 네트워크에 대한 위상 정렬을 실시합니다.
int i, j;
for (j = 0; j < MAX_VERTICES; j++) {
if (graph[j].count == 0) // count가 0인 것은 해당 노드 이전에 해야할 작업이 없다는 것을뜻합니다.
Input_Stack(j); // 초기 설정 상 0번 노드만 count가 0이므로 스택에 저장됩니다.
}
int n;
Node* tmp;
Node* cur;
while (top != -1) { // 스택에 저장된 데이터가 없을 때까지 반복합니다.
n = Delete_Stack(); // 스택에 저장된 데이터를 하나 꺼내고
cur = graph[n].link;
while (cur != NULL) { // 해당 노드에 연결된 데이터가 없을 때까지 반복합니다.
//printf("cur->vertex = %d\n", cur->vertex);
graph[cur->vertex].count--; // 스택에서 나온 노드와 연결된 노드의 count를 감소 시킵니다.
if (graph[cur->vertex].count == 0) // 만약 연결된 노드의 count가 0이 되면 스택에입력해줍니다.
Input_Stack(cur->vertex); // 이 부분 때문에 가장 바깥 while문이 다시 한번반복됩니다.
cur = cur->link;
}
}
}
void Cal_EST(void) { // aov를 기준으로 EST를 구하는 알고리즘입니다.
int i = 0;
Node* tmp;
Node* cur;
int max = 0;
while (i < MAX_VERTICES) { // 여기를 for문으로 구성해도 됩니다.
cur = graph[i].link; // 0번째 노드 부터 시작합니다.
printf("111graph[%d].EST = %d\n", i, graph[i].EST);
while (cur != NULL) {
if (graph[cur->vertex].EST < graph[i].EST + graph[i].weight) { // i와 연결된노드의 EST가 i의 EST+i의 작업 시간 보다 작을 때, i와 연결된 노드의 EST를 업데이트해준다.
graph[cur->vertex].EST = graph[i].EST + graph[i].weight;
printf("222graph[%d].EST = %d\n", cur->vertex, graph[cur->vertex].EST);
if (graph[cur->vertex].EST >= max) {
max = graph[cur->vertex].EST; // 나중에 LST 계산을 위해 설정해줍니다.
}
}
cur = cur->link;
}
i++;
}
for (int j = 0; j < MAX_VERTICES; j++) {
//if (graph[j].EST == max) {
inverted_graph[j].LST = max; // LST는 EST의 max 보다 항상 작거나 같기 때문에 이와같이 초기화 합니다.
printf("inverted_graph[%d].LST = %d\n", j, inverted_graph[j].LST);
//}
}
}
// LST: 가장 늦게 시작할 수 있는 시간
void Inverting_Graph(void) { // 그래프의 리스트를 역순으로 다시 정렬해줍니다.
// EX) 괄호 안은 count 입니다.
// 0 (0) -> 1 (1)
// 0 (0) -> 2 (1)
// Invert 하면 다음과 같습니다.
// 1 (0) -> 0 (1)
// 2 (0) -> 0 (2)
int u;
int i = 0;
int j;
Node* tmp;
Node* cur;
Node* tmp1;
for (i = 0; i < MAX_VERTICES; i++) {
cur = graph[i].link;
while (cur != NULL) {
tmp = (Node*)malloc(sizeof(Node));
u = cur->vertex;
tmp->vertex = i;
tmp->link = NULL;
tmp1 = inverted_graph[u].link;
inverted_graph[u].link = tmp;
tmp->link = tmp1;
cur = cur->link;
}
}
}
void Cal_LST(void) { // aov의 역인접 리스트를 이용하여 LST를 계한합니다.
int i = MAX_VERTICES - 1; // 리스트의 가장 마지막 노드부터 시작합니다.
//graph[i].LST = inverted_graph[i].LST;
Node* tmp;
for (; i >= 0; i--) { // EST와 if 문의 조건문과 역순으로 진행되는 것을 제외하고 모두 동일합니다.
graph[i].LST = inverted_graph[i].LST; // graph에도 LST 정보를 업데이트 하기 위함
tmp = inverted_graph[i].link;
printf("111inverted_graph[%d].LST = %d\n", i, inverted_graph[i].LST);
while (tmp != NULL) {
int u = tmp->vertex;
printf("i = %d, u = %d\n", i, u);
if (inverted_graph[u].LST > inverted_graph[i].LST - inverted_graph[u].weight) {
// EST에서도 마찬가지로, if 문을 통과하며 u가 연결된 모든 노드에 대해 LST의 최소값을찾아줄 수 있습니다.
// EST에서는 최대값
inverted_graph[u].LST = inverted_graph[i].LST - inverted_graph[u].weight;
graph[u].LST = inverted_graph[u].LST;
}
printf("222inverted_graph[%d].LST = %d\n", u, inverted_graph[u].LST);
tmp = tmp->link;
}
}
}
// main.c
// Network_AoE_AoV
//
// Created by 김경민 on 2020/04/21.
// Copyright © 2020 김경민. All rights reserved.
//
// aov와 aoe를 활용한 임계 작업 시간 검색 방법을 구현한다
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 6
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
typedef struct NODE { // 헤드노드에 연결되는 노드 데이터를 저장합니다.
int vertex;
struct NODE* link;
}Node;
typedef struct HEADNODES { // 헤드노드에 대한 데이터를 저장합니다.
int count;
int weight;
int EST; // 작업을 시작할 수 있는 가장 빠른 시간입니다.
int LST; // 작업을 시작할 수 있는 가장 느린 시간입니다.
// 무조건 A와 B가 끝나야 C를 할 수 있다고 가정합니다.
// A는 7분이 걸리고, B는 10분이 걸립니다.
// C는 A와 B를 시작한지 무조건 10분 이상은 지나야 실시 가능합니다. (10분이 C의 EST)
// 작업을 전부 완료하려면 C가 실시되어야 합니다.
// B가 A 보다 3분 늦게 끝나니까
// A는 B보다 3분 늦게 시작해도 C가 시작되는 시간은 동일합니다. (3분이 A의 LST, 0분이 B의 LST)
Node* link;
} Headnodes;
Headnodes graph[MAX_VERTICES];
Headnodes inverted_graph[MAX_VERTICES];
/*-----------ADT------------*/
void Init_Headnodes(void);
Node* Init_Vertex(int vertex);
void Input_Head_2_Node(int u, int v);
void Activity_On_Vertex(void);
void Cal_EST(void);
void Inverting_Graph(void);
void Cal_LST(void);
/*--------------------------*/
void Init_Headnodes(void) {
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i].count = 0;
graph[i].weight= 0;
graph[i].EST = 0;
graph[i].link = NULL;
}
}
Node* Init_Vertex(int vertex) {
Node* tmp = (Node*)malloc(sizeof(Node));
tmp->vertex = vertex;
tmp->link = NULL;
return tmp;
}
void Input_Head_2_Node(int u, int v) { // 헤드 노드에서 다른 노드로 가는 경로를 이어줍니다.
Node* cur = Init_Vertex(v);
Node* tmp;
tmp = graph[u].link; // tmp는 기존에 헤드 노드에 연결되어있던 노드입니다.
graph[u].link = cur; // 헤드 노드에 현재 이어주고자 하는 노드를 연결해주고
cur->link = tmp; // 현재 이어주고자 하는 노드 뒤에 기존에 헤드 노드에 연결되어 있던 노드를연결해줍니다.
graph[v].count++; // 연결이 된 정점의 count를 증가시켜준다.
// count는 해당 노드가 다른 노드에 연결된 갯수를 저장합니다.
// 즉, 헤드 노드 u가 아닌 헤드 노드 v의 count를 증가시켜줍니다.
}
/*--------Stack---------*/
int top = -1;
int stack[MAX_VERTICES];
void Input_Stack(int n) {
if (top == MAX_VERTICES) {
printf("Stack is full\n");
}
else {
stack[++top] = n;
printf("Input stack[%d] = %d\n", top, n);
}
}
int Delete_Stack(void) {
int n = -1;
if (top == -1) {
printf("Stack is empty\n");
}
else {
n = stack[top--];
printf("Deleted stack[%d] = %d\n", top + 1, n);
}
return n;
}
/*----------------------*/
void Activity_On_Vertex(void) { // aov 네트워크에 대한 위상 정렬을 실시합니다.
int i, j;
for (j = 0; j < MAX_VERTICES; j++) {
if (graph[j].count == 0) // count가 0인 것은 해당 노드 이전에 해야할 작업이 없다는 것을뜻합니다.
Input_Stack(j); // 초기 설정 상 0번 노드만 count가 0이므로 스택에 저장됩니다.
}
int n;
Node* tmp;
Node* cur;
while (top != -1) { // 스택에 저장된 데이터가 없을 때까지 반복합니다.
n = Delete_Stack(); // 스택에 저장된 데이터를 하나 꺼내고
cur = graph[n].link;
while (cur != NULL) { // 해당 노드에 연결된 데이터가 없을 때까지 반복합니다.
//printf("cur->vertex = %d\n", cur->vertex);
graph[cur->vertex].count--; // 스택에서 나온 노드와 연결된 노드의 count를 감소 시킵니다.
if (graph[cur->vertex].count == 0) // 만약 연결된 노드의 count가 0이 되면 스택에입력해줍니다.
Input_Stack(cur->vertex); // 이 부분 때문에 가장 바깥 while문이 다시 한번반복됩니다.
cur = cur->link;
}
}
}
void Cal_EST(void) { // aov를 기준으로 EST를 구하는 알고리즘입니다.
int i = 0;
Node* tmp;
Node* cur;
int max = 0;
while (i < MAX_VERTICES) { // 여기를 for문으로 구성해도 됩니다.
cur = graph[i].link; // 0번째 노드 부터 시작합니다.
printf("111graph[%d].EST = %d\n", i, graph[i].EST);
while (cur != NULL) {
if (graph[cur->vertex].EST < graph[i].EST + graph[i].weight) { // i와 연결된노드의 EST가 i의 EST+i의 작업 시간 보다 작을 때, i와 연결된 노드의 EST를 업데이트해준다.
graph[cur->vertex].EST = graph[i].EST + graph[i].weight;
printf("222graph[%d].EST = %d\n", cur->vertex, graph[cur->vertex].EST);
if (graph[cur->vertex].EST >= max) {
max = graph[cur->vertex].EST; // 나중에 LST 계산을 위해 설정해줍니다.
}
}
cur = cur->link;
}
i++;
}
for (int j = 0; j < MAX_VERTICES; j++) {
//if (graph[j].EST == max) {
inverted_graph[j].LST = max; // LST는 EST의 max 보다 항상 작거나 같기 때문에 이와같이 초기화 합니다.
printf("inverted_graph[%d].LST = %d\n", j, inverted_graph[j].LST);
//}
}
}
// LST: 가장 늦게 시작할 수 있는 시간
void Inverting_Graph(void) { // 그래프의 리스트를 역순으로 다시 정렬해줍니다.
// EX) 괄호 안은 count 입니다.
// 0 (0) -> 1 (1)
// 0 (0) -> 2 (1)
// Invert 하면 다음과 같습니다.
// 1 (0) -> 0 (1)
// 2 (0) -> 0 (2)
int u;
int i = 0;
int j;
Node* tmp;
Node* cur;
Node* tmp1;
for (i = 0; i < MAX_VERTICES; i++) {
cur = graph[i].link;
while (cur != NULL) {
tmp = (Node*)malloc(sizeof(Node));
u = cur->vertex;
tmp->vertex = i;
tmp->link = NULL;
tmp1 = inverted_graph[u].link;
inverted_graph[u].link = tmp;
tmp->link = tmp1;
cur = cur->link;
}
}
}
void Cal_LST(void) { // aov의 역인접 리스트를 이용하여 LST를 계한합니다.
int i = MAX_VERTICES - 1; // 리스트의 가장 마지막 노드부터 시작합니다.
//graph[i].LST = inverted_graph[i].LST;
Node* tmp;
for (; i >= 0; i--) { // EST와 if 문의 조건문과 역순으로 진행되는 것을 제외하고 모두 동일합니다.
graph[i].LST = inverted_graph[i].LST; // graph에도 LST 정보를 업데이트 하기 위함
tmp = inverted_graph[i].link;
printf("111inverted_graph[%d].LST = %d\n", i, inverted_graph[i].LST);
while (tmp != NULL) {
int u = tmp->vertex;
printf("i = %d, u = %d\n", i, u);
if (inverted_graph[u].LST > inverted_graph[i].LST - inverted_graph[u].weight) {
// EST에서도 마찬가지로, if 문을 통과하며 u가 연결된 모든 노드에 대해 LST의 최소값을찾아줄 수 있습니다.
// EST에서는 최대값
inverted_graph[u].LST = inverted_graph[i].LST - inverted_graph[u].weight;
graph[u].LST = inverted_graph[u].LST;
}
printf("222inverted_graph[%d].LST = %d\n", u, inverted_graph[u].LST);
tmp = tmp->link;
}
}
}
int main(void) {
// 가중치를 설정해붑니다.
// 이부분을 다른 그래프 함수에 사용된 랜덤 변수로 설정하셔도 됩니다.
graph[0].weight = 7;
graph[1].weight = 5;
graph[2].weight = 10;
graph[3].weight = 8;
graph[4].weight = 3;
graph[5].weight = 5;
for (int j = 0; j < MAX_VERTICES; j++) {
inverted_graph[j].count = 0;
inverted_graph[j].weight = graph[j].weight;
inverted_graph[j].link = NULL;
inverted_graph[j].LST = 0;
}
// 노드를 연결해줍니다.
// 마찬가지로 랜덤 변수를 사용할 수 있을 것 같습니다.
Input_Head_2_Node(0, 1);
Input_Head_2_Node(0, 2);
Input_Head_2_Node(0, 3);
Input_Head_2_Node(1, 4);
Input_Head_2_Node(2, 4);
Input_Head_2_Node(2, 5);
Input_Head_2_Node(3, 4);
Input_Head_2_Node(3, 5);
Inverting_Graph();
//printf("inverted_graph[%d] = %d\n", 4, inverted_graph[4].link->link->vertex);
Cal_EST();
Cal_LST();
for (int i = 0; i < MAX_VERTICES; i++) {
printf("graph[%d].EST = %d, graph[%d].LST = %d\n", i, graph[i].EST, i, graph[i].LST);
}
//Activity_On_Vertex();
return 0;
}
//
// main.c
// Graph_New_BFS_DFS
//
// Created by 김경민 on 2020/05/11.
// Copyright © 2020 김경민. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 10
#define MAX_QUEUE MAX_VERTEX+1
int check[MAX_VERTEX];
/*-----------Graph-----------*/
typedef struct LIST {
int vx;
struct LIST* link;
}List;
typedef struct GRAPH {
int n;
List* adj_list[MAX_VERTEX];
}Graph;
/*---------------------------*/
/*---------Graph ADT---------*/
Graph* Init_Graph(void);
void Add_Vertex(Graph* g);
void Add_Edge(Graph* g, int u, int v);
void Check_Link(Graph* g, int u, int v);
void Delete_Vertex(Graph* g, int u);
void Delete_Edge(Graph* g, int u, int v);
void DFS(Graph *g, int n);
void Depth_First_Search(Graph* g, int n);
void BFS(Graph *g, int n);
void Breath_First_Search(Graph* g, int n);
void Add_Queue(int n);
int Delete_Queue(void);
/*---------------------------*/
/*-----------Queue-----------*/
int front = 0;
int rear = 0;
int queue[MAX_QUEUE];
/*---------------------------*/
int main(void) {
Graph* g = Init_Graph();
for(int i = 0; i < 5; i++){
Add_Vertex(g);
}
Add_Edge(g, 0, 1);
Add_Edge(g, 0, 2);
Add_Edge(g, 0, 3);
Add_Edge(g, 1, 2);
Add_Edge(g, 1, 3);
Add_Edge(g, 1, 4);
Check_Link(g, 1, 3);
#if 0
Delete_Vertex(g, 3);
Check_Link(g, 1, 3);
Check_Link(g, 3, 0);
#endif
#if 0
Delete_Edge(g, 1, 0);
Check_Link(g, 1, 0);
Check_Link(g, 0, 1);
#endif
DFS(g, 0);
BFS(g, 0);
return 0;
}
Graph* Init_Graph(void){
Graph* g = (Graph*)malloc(sizeof(Graph));
g->n = 0;
for(int i = 0; i < MAX_VERTEX; i++)
g->adj_list[i] = NULL;
return g;
}
void Add_Vertex(Graph* g){
g->adj_list[g->n] = (List*)malloc(sizeof(List));
g->adj_list[g->n]->vx = -1;
g->adj_list[g->n]->link = NULL;
g->n++;
}
void Add_Edge(Graph* g, int u, int v){
if(u >= g->n || v >= g->n){
printf("Out of Graph.\n\n");
}
else{
List* tmp_u = (List*)malloc(sizeof(List));
List* tmp_v = (List*)malloc(sizeof(List));
tmp_u->vx = u;
tmp_v->vx = v;
tmp_v->link = g->adj_list[u]->link;
g->adj_list[u]->link = tmp_v;
tmp_u->link = g->adj_list[v]->link;
g->adj_list[v]->link = tmp_u;
// 이렇게 하면 바로 연결 안 되고, root 노드가 생긴 느낌으로 연결된다.
}
}
void Check_Link(Graph* g, int u, int v){
if(u >= g->n || v >= g->n){
printf("Out of Graph.\n\n");
}
else{
List* cur;
List* tmp;
cur = g->adj_list[u]->link;
while(cur != NULL){
tmp = cur->link;
if(cur->vx == v){
printf("Connected!! [%d]--[%d]\n", u, v);
return;
}
cur = tmp;
}
printf("Disconnected!! [%d]\\[%d]\n", u, v);
}
}
void Delete_Vertex(Graph* g, int u){
if(u >= g->n){
printf("Out of Graph.\n\n");
}
else{
List* cur;
List* pre;
List* tmp;
for(int i = 0; i < g->n && i != u; i++){
pre = g->adj_list[i];
cur = pre->link;
while(cur != NULL){
tmp = cur->link;
if(cur->vx == u){
pre->link = cur->link;
free(cur);
break;
}
pre = cur;
cur = tmp;
}
}
pre = g->adj_list[u];
cur = g->adj_list[u]->link;
while(cur != NULL){
tmp = cur->link;
free(cur);
cur = tmp;
}
pre->link = NULL;
}
}
void Delete_Edge(Graph* g, int u, int v){
if(u >= g->n){
printf("Out of Graph.\n\n");
}
else{
List* cur;
List* pre;
List* tmp;
pre = g->adj_list[u];
cur = g->adj_list[u]->link;
while(cur != NULL){
tmp = cur->link;
if(cur->vx == v){
pre->link = cur->link;
free(cur);
break;
}
pre = cur;
cur = tmp;
}
pre = g->adj_list[v];
cur = g->adj_list[v]->link;
while(cur != NULL){
tmp = cur->link;
if(cur->vx == u){
pre->link = cur->link;
free(cur);
break;
}
pre = cur;
cur = tmp;
}
}
}
void DFS(Graph *g, int n){
for(int i = 0; i < MAX_VERTEX; i++){
check[i] = 0;
}
Depth_First_Search(g, n);
printf("\n");
}
void Depth_First_Search(Graph* g, int n){
// 노드1의 노드2의 노드3의 노드4를 방문하고, 더이상 없으면 다시 노드3의 노드 3-1, 3-2, 3-3을 방문하고, 더이상 없으면 노드2의 노드2-1, 2-2, 2-3을 방문하고, 더이상 없으면 노드1의 노드 1-1, 1-2, 1-3을 방문하며 반복
if(check[n] == 0){
List* cur;
List* tmp;
cur = g->adj_list[n]->link;
printf("%2d ", n);
check[n] = 1;
while(cur != NULL){
tmp = cur->link;
if(check[cur->vx] == 0)
Depth_First_Search(g, cur->vx);
cur = tmp;
}
}
}
void BFS(Graph *g, int n){
for(int i = 0; i < MAX_VERTEX; i++){
check[i] = 0;
}
front = 0;
rear = 0;
Breath_First_Search(g, n);
printf("\n");
}
void Breath_First_Search(Graph* g, int n){
// 기준 노드와 연결된 노드 쫙 탐색, 연결된 노드에 연결된 노드를 차례대로 쫙 탐색
List* cur;
List* tmp;
int queue_out;
cur = g->adj_list[n]->link;
if(check[n] == 0){
printf("%2d ", n);
check[n] = 1;
}
while(cur != NULL){
tmp = cur->link;
if(check[cur->vx] == 0){
printf("%2d ", cur->vx);
check[cur->vx] = 1;
Add_Queue(cur->vx);
}
cur = tmp;
}
queue_out = Delete_Queue();
while(queue_out != -1){
Breath_First_Search(g, queue_out);
queue_out = Delete_Queue();
}
}
void Add_Queue(int n){
if((rear+1)%MAX_QUEUE == front){
puts("Queue is full.");
}
else{
rear = (rear+1)%MAX_QUEUE;
queue[rear] = n; // 1번부터 찬다.
}
}
int Delete_Queue(void){
int tmp = -1;
if(front == rear){
// puts("Queue is empty.");
}
else{
front = (front+1)%MAX_QUEUE;
tmp = queue[front];
}
return tmp;
}
'기타(임시)' 카테고리의 다른 글
| 프로젝트에 관하여 (0) | 2020.05.21 |
|---|---|
| [자료구조 C 언어] 부록 - 4: 네트워크 - AOV, AOE, EST, LST, Topological Sort, Critical Path (0) | 2020.05.14 |
| BFS_DFS 임시 (0) | 2020.05.13 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 21 : 해싱 (Hasing) (0) | 2020.03.19 |
| Dynamic Programming (DP) (0) | 2019.10.31 |