[알고리즘] Assignment 5 - LCS 알고리즘, BFS 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘, Prim 알고리즘

1. LCS (Longest Common Subsequence, 최장 공통 부분 문자열)

#include <stdio.h>
#define MAX(a,b) ((a)>(b)? (a):(b))

int LCS_table[10][10] = { 0, };

void LCS_length(int str1_len, int str2_len, char* str1, char* str2) {
	for (int i = 1; i < str1_len; i++) {
		for (int j = 1; j < str2_len; j++) {
			if (str1[i] == str2[j]) {
				LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1;
			}
			else {
				LCS_table[i][j] = MAX(LCS_table[i - 1][j], LCS_table[i][j - 1]);
			}
		}
	}
}

void print_LCS(int str1_len, int str2_len, char* str2) {
	char LCS[10] = { '\0', };
	int LCS_len = LCS_table[str1_len - 1][str2_len - 1] - 1;

	int i = str1_len - 1;
	for (int j = str2_len - 1; j > 0;) {
		if (LCS_table[i][j] == LCS_table[i - 1][j]) i--;
		else if (LCS_table[i][j] == LCS_table[i][j - 1]) j--;
		else if (LCS_table[i - 1][j] == LCS_table[i][j - 1]) {
			LCS[LCS_len--] = str2[j--];
			i--;
		}
		else if (LCS_table[i - 1][j] == LCS_table[i][j - 1]) {
			LCS[LCS_len--] = str2[j--];
		}
	}

	printf("%d, LCS : %s\n", LCS_table[str1_len - 1][str2_len - 1], LCS);
}

int main() {
	int X_len = 8, Y_len = 7;
	char X[8] = {'\0',  'A', 'B', 'C', 'B', 'D', 'A', 'B' };
	char Y[7] = { '\0', 'B', 'D', 'C', 'A', 'B', 'A' };

	LCS_length(X_len, Y_len, X, Y);
	print_LCS(X_len, Y_len, Y);
}

 

 

2. BFS (Breadth-First Search, 너비 우선 탐색)

#include <stdio.h>

int mat[8][8] = { 0, };
int flag[8] = { 0, };
int pi[8] = { 10, }; // NIL
int V = 8, E = 10;
int edge_v[10 * 2] = { 0, 1, 0, 4, 1, 5, 2, 3, 2, 5, 2, 6, 3, 6, 3, 7, 5, 6, 6, 7 };

int BFS(int n, int k) {
	int queue[10];
	int front = -1;
	int rear = -1;
	queue[++rear] = n;
	flag[n] = 1;

	while (front != rear) {
		n = queue[++front];
		if (n == k) {
			return (flag[n] - 1);
		}
		for (int i = 0; i < V; i++)
		{
			if ((mat[n][i] == 1) && (flag[i] == 0))
			{
				queue[++rear] = i;
				flag[i] = flag[n] + 1;
				pi[i] = n;
			}
		}
	}
	return 0;
}

int main(void)
{
	for (int i = 0; i < E * 2; i += 2) {
		int start = edge_v[i], end = edge_v[i + 1];
		mat[start][end] = 1;
		mat[end][start] = 1;
	}

	printf("<d>\n");
	for (int i = 0; i < 8; i++) {
		printf("%c: ", 'r' + i);
		if (i == 1) {
			printf("0   ");
		}
		else {
			printf("%d   ", BFS(1, i));
			for (int j = 0; j < 8; j++) {
				flag[j] = 0;
			}
		}
	}
	printf("\n");

	printf("<pi>\n");
	for (int i = 0; i < 8; i++) {
		printf("%c: ", 'r' + i);
		if (i == 1) {
			printf("-   ");
		}
		else {
			printf("%c   ", 'r' + pi[i]);
		}
	}
	printf("\n");

	return 0;
}

 

 

3. Kruskal's Algorithm

 

 

4. Dijkstra's Algorithm

#include <stdio.h>
#include <limits.h>
#define INF 100
#define V 5

int cost[V][V] = {
    {0, 3, INF, 5, INF},
    {INF, 0, 6, 2, INF},
    {INF, INF, 0, INF, 2},
    {INF, 1, 4, 0, 6},
    {3, INF, 7, INF, 0}
};

int d[V]; int flag[V];

int find_min(int d[], int n, int flag[])
{
    int min, min_loc;
    min = INT_MAX;
    min_loc = -1;

    for (int i = 0; i < n; i++)
    {
        if (d[i] < min && flag[i] == 0)
        {
            min = d[i];
            min_loc = i;
        }
    }

    return min_loc;
}

void Dijkstra(int source, int last, int destiny) {

    int path[V][V] = { INF, };
    int cnt_path[V] = { 0, };

    for (int i = 0; i < last; i++)
    {
        d[i] = cost[source][i];
        flag[i] = 0;
        path[i][cnt_path[i]] = i;
        cnt_path[i]++;
    }
    
    flag[source] = 1;
    d[source] = 1;

    for (int i = 0; i < last - 1; i++)
    {
        int u = find_min(d, last, flag);
        flag[u] = 1;

        for (int j = 0; j < last; j++)
        {
            if (flag[j] == 0)
            {
                if (d[u] + cost[u][j] < d[j])
                {
                    d[j] = d[u] + cost[u][j];
                    path[j][cnt_path[j]] = u;
                    cnt_path[j]++;
                }
            }
        }
    }

    for (int i = V - 1; i > -1; i--) {
        if (path[destiny][i] == 0) continue;
        else if (path[destiny][i] < 2) {
            printf("(%d)", path[destiny][i]);
            printf("%c ", 's' + path[destiny][i]);
        }
        else {
            printf("(%d)", path[destiny][i]);
            printf("%c ", 'v' + path[destiny][i]);
        }
    }
    printf(" / cost = %d\n", d[destiny]);
}


int main()
{ 
    printf("from S to X : ");
    Dijkstra(0, V, 2);

    printf("form S to Z : ");
    Dijkstra(0, V, 4);

    return 0;
}

 

 

5. Prim's Algorithm