[C언어로 쉽게 풀어쓴 자료구조] 연습문제 11강

 

04

void prim(GraphType *g, int s){
	int i,u,v;
	for(u=0; u<g->n; u++){
		distance[u] = INF;
	}
	distance[s]=0;
	
	for(i=0; i<g->n; i++){
		u = get_min_vertex(g->n);
		selected[u] = TRUE;
        // 04 문제 프린트문 시작
		printf("selected[]= ");
		for(int j=0;j<g->n;j++){
			printf("%d ",selected[j]);
		}
		printf("\n");
		printf("distance[]= ");
		for(int j=0;j<g->n;j++){
			printf("%d ",distance[j]);
		}
        // 04 문제 프린트문 종료
		if(distance[u]==INF) return;
		printf("정점 %d 추가\n",u);
		for(v=0;v<g->n;v++){
			if(g->weight[u][v] !=INF){
				if(!selected[v] && g->weight[u][v]<distance[v]){
					distance[v] = g->weight[u][v];
				}
			}
		}
	}
}

 

결과:

selected[]= 1 0 0 0 0 1 0
distance[]= 0 29 1000 1000 1000 10 1000 정점 5 추가
selected[]= 1 0 0 0 1 1 0
distance[]= 0 29 1000 1000 27 10 1000 정점 4 추가
selected[]= 1 0 0 1 1 1 0
distance[]= 0 29 1000 22 27 10 25 정점 3 추가
selected[]= 1 0 1 1 1 1 0
distance[]= 0 29 12 22 27 10 18 정점 2 추가
selected[]= 1 1 1 1 1 1 0
distance[]= 0 16 12 22 27 10 18 정점 1 추가
selected[]= 1 1 1 1 1 1 1
distance[]= 0 16 12 22 27 10 15 정점 6 추가

distance[]는 정점이 갱신될 때마다 인접 정점들의 간선 가중치를 뜻하고

selected[]는 방문한 정점을 뜻한다.

 

 

07 08 09

08은 found의 1 출력 순서가 경로를 보이고,

09는 distance 배열을 출력하였다. distance[]배열은 정점이 갱신될 때마다 인접 정점들을 이은 간선들의

weight를 갱신해주어 가장 짧은 distance가 무엇인지 알게 해 준다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define TRUE 1
#define FALSE 0
#define INF 1000000

int found[MAX_VERTICES];
int distance[MAX_VERTICES];

typedef struct GraphNode {
    int vertex;
    int weight;
    struct GraphNode* link;
} GraphNode;

typedef struct GraphType {
    int n;
    GraphNode* adj_list[MAX_VERTICES];
} GraphType;


int choose(int distance[], int n, int found[]) {
    int i, min, minpos;
    min = INF;
    minpos = -1;
    for (i = 0; i < n; i++) {
        if (distance[i] < min && !found[i]) {
            min = distance[i];
            minpos = i;
        }
    }
    return minpos;
}  // 집합 S에 포함되지 않는 정점 중 distance가 가장 작은 정점 return

void print_status(GraphType* g) {
    static int step = 1;
    printf("STEP %d: ", step++);
    printf("distance: ");
    for (int i = 0; i < g->n; i++) {
        if (distance[i] == INF)
            printf(" * ");
        else
            printf("%2d ", distance[i]);
    }
    printf("\n");
    printf("found: ");
    for (int i = 0; i < g->n; i++) {
        printf("%2d ", found[i]);
    }
    printf("\n\n");
}

GraphNode* create_node(int vertex, int weight) {
    GraphNode* new_node = (GraphNode*)malloc(sizeof(GraphNode));
    if (new_node == NULL) {
        fprintf(stderr, "노드 생성 오류");
        exit(1);
    }
    new_node->vertex = vertex;
    new_node->weight = weight;
    new_node->link = NULL; 
    return new_node;
}

void insert_edge(GraphType* g, int u, int v, int weight) {
    GraphNode* new_node = create_node(v, weight);
    new_node->link = g->adj_list[u];
    g->adj_list[u] = new_node;
}

void shortest_path(GraphType* g, int start) {
    int i, u, w;
	GraphNode *node;
    for (i = 0; i < g->n; i++) {
		distance[i] = INF;
        found[i] = FALSE;
    }
	for(node=g->adj_list[start];node;node=node->link){
		int x = node->vertex;
		distance[x] = node->weight;
	} // distance[i] = INF 인채로 두면 안되지.. 리스트 받아서 초기화해줌.
	
    found[start] = TRUE;
    distance[start] = 0;

    for (i = 0; i < g->n; i++) {
        print_status(g);
        u = choose(distance, g->n, found);
        found[u] = TRUE;

        GraphNode* node = g->adj_list[u];
        while (node != NULL) {
            w = node->vertex;
            if (!found[w]) {
                if (distance[u] + node->weight < distance[w]) {
                    distance[w] = distance[u] + node->weight;
                }
            }
            node = node->link;
        }
    }
}

void print_list(GraphType *g,int v){
	GraphNode *w;
	found[v] = TRUE;
	printf("정점 %d -> ",v);
	for(w=g->adj_list[v];w;w=w->link){
		printf("%d-> ",w->vertex);
	}
	printf("\n");
}

void cleanup(GraphType* g) {
    for (int i = 0; i < g->n; i++) {
        GraphNode* current = g->adj_list[i];
        while (current != NULL) {
            GraphNode* temp = current;
            current = current->link;
            free(temp);
        }
    }
}

int main() {
    GraphType g = {7, {NULL}};

    insert_edge(&g, 0, 1, 7);
    insert_edge(&g, 0, 4, 3);
    insert_edge(&g, 0, 5, 10);
    insert_edge(&g, 1, 0, 7);
    insert_edge(&g, 1, 2, 4);
    insert_edge(&g, 1, 3, 10);
    insert_edge(&g, 1, 4, 2);
    insert_edge(&g, 1, 5, 6);
    insert_edge(&g, 2, 1, 4);
    insert_edge(&g, 2, 3, 2);
    insert_edge(&g, 3, 1, 10);
    insert_edge(&g, 3, 2, 10);
    insert_edge(&g, 3, 4, 11);
    insert_edge(&g, 3, 5, 9);
    insert_edge(&g, 3, 6, 4);
    insert_edge(&g, 4, 0, 3);
    insert_edge(&g, 4, 1, 2);
    insert_edge(&g, 4, 3, 11);
    insert_edge(&g, 4, 6, 5);
    insert_edge(&g, 5, 0, 10);
    insert_edge(&g, 5, 1, 6);
    insert_edge(&g, 5, 3, 9);
    insert_edge(&g, 6, 3, 4);
    insert_edge(&g, 6, 4, 5);

	
	for(int i=0;i<7;i++){
		print_list(&g,i);
	}
	
    shortest_path(&g, 0);

    cleanup(&g);

    return 0;
}