C언어로 쉽게 풀어쓴 자료구조 11장 해설(3판/천인국)

소개글

1. 본 파일의 정답 및 해설은 공식 정답이 아닌 직접 풀어서 작성한 것이며 오타, 오답 및 프로그램에 버그가 존재할 수 있으므로 반드시 확인하시길 바랍니다.
2. 간단한 문제는 해설이 생략되었을 수 있습니다.
3. 프로그램의 설명은 주석을 참조하시길 바랍니다.
4. 작성자가 과제로 지정된 문제의 해설만을 작성한것으로 일부 문제가 누락되었을 수 있습니다. 본문내용의 포함된 문제를 반드시 확인하시길 바랍니다.

목차

1. 다음의 그래프에서 가능한 신장 트리를 모두 나열하라.
2. 아래의 네트워크에 대하여 Kruskal의 MST 알고리즘을 ... 보여라.
3. 앞의 네트워크에 대하여 Prim의 MST 알고리즘을 ... (A번 정점으로 시작할 것).
4. Prim의 함수에서 distance[ ]와 selected[ ]의 값을 ... 설명하라.
5. 다음의 방향그래프에서 정점 0에서 다른 모든 정점까지의 ... 정점들을 나타내어라.
6. 5번의 그래프에 대하여 Floyd 알고리즘을 ... 출력하라.
7. Dijkstra의 최단 경로 함수를 ... 재작성하라.
8. 최단 경로 함수를 ... 수정하라.
9. 최단 경로 함수에서 distance[ ]의 내용을 ... 설명하라.
10. 다음의 그래프에 ... 구하라.

본문내용

정답 코드
void print(GraphType* g)
{
printf("distance[ ] = [ ");
for (int a = 0; a < g->n; a++)
printf("%d ", distance[a]);
//거리를 반복하여 출력
printf("]\nselected[ ] = [ ");
for (int a = 0; a < g->n; a++)
printf("%d ", selected[a]);
//포함여부를 반복하여 출력
printf("]\n");
}
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;
if (distance[u] == INF) return;
printf("정점 %d 추가\n", u);
print(g);
//distance, selected를 출력할 수 있게 포함시킨다.
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];

참고 자료

없음