자료구조 11장 연습문제

소개글

"자료구조 11장 연습문제"에 대한 내용입니다.

목차

없음

본문내용

1. 다음의 그래프에서 가능한 신장 트리를 모두 나열하라.

=> 가능한 신장 트리는 4개이다.

2. 아래의 네트워크에 대하여 kruskal의 MST 알고리즘을 이용해서 최소비용 신장 트리가 구성되는 과정을 보여라.

=> 따라서 최소 비용 신장 트리는 아래와 같다.

3. 앞의 네트워크에 대하여 Prim의 MST 알고리즘을 이용해서 최소비용 신장 트리가 구성되는 과정을 보여라(A번 정점으로 시작할 것)

4. Prim의 함수에서 distance[]화 selected[] 의 값을 출력하는 문장을 삽입하여 출력하여 보고 이들의 의미를 설명하라.
#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTICLES 100
#define INF 1000L

typedef struct GraphType {
int n;
int weight[MAX_VERTICLES][MAX_VERTICLES];
}GraphType
int selected[MAX_VERTICLES];
int distance[MAX_VERTICLES];
int get_min_vertex(int n) {
int v, i;
for (i = 0; i < n i++) {
v = i;
break
}
for (i = 0; i < n i++)
if (!selected[i] && (distance[i] < distance[v]))v = i;
return (v);
}
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] = 1;
if (distance[u] == INF)return

참고 자료

없음