Q&A
プリム法とはなんのことでしょうか
クルスカルのアルゴリズムを勉強して、次にプリム法を勉強して仕組みは理解できたのですが、実際に打てなかったので実装例を教えていただきたいです。下のクルスカルのソースコードを一部書き換える形で実装したいです。
コード #include <stdio.h> #include <stdlib.h> #define ASIZE 12 #define ESIZE 40 int p[ASIZE]; int rank[ASIZE]; struct edge{ int u; int v; int weight; }; struct element { int vertex; int weight; struct element *next; }; struct element *newl() { return((struct element *) malloc(sizeof(struct element))); } struct element *create() { struct element *p; p = newl(); p->next = NULL; return(p); } void append(struct element *l, int v, int w) { struct element *p; if (l->next != NULL) append(l->next, v, w); else { p = newl(); p->vertex = v; p->weight = w; p->next = NULL; l->next = p; } } void printlist(struct element *l) { if(l->next != NULL){ printf(" (v%d,%d)", l->next->vertex, l->next->weight); printlist(l->next); } } void createadjlist(struct element *a[], int n) { int i; for (i = 1;i <= n; i++) a[i] = create(); } void printadjlist(struct element *a[], int n) { int i; for (i = 1; i <= n; i++){ printf("a[v%d",i); printf("] = "); printlist(a[i]); printf("\n"); } } int makegraph(struct element *a[]) { createadjlist(a, 5); append(a[1], 2, 1); append(a[1], 3, 3); append(a[1], 5, 5); append(a[2], 1, 1); append(a[2], 3, 2); append(a[2], 5, 2); append(a[3], 1, 3); append(a[3], 2, 2); append(a[3], 4, 7); append(a[4], 3, 7); append(a[4], 5, 4); append(a[5], 1, 5); append(a[5], 2, 2); append(a[5], 4, 4); return 5; } int makegraph2(struct element *a[]) { createadjlist(a, 10); append(a[1], 2, 4); append(a[1], 10, 3); append(a[2], 4, 1); append(a[2], 3, 2); append(a[2], 5, 1); append(a[2], 1, 4); append(a[3], 2, 2); append(a[3], 4, 3); append(a[4], 2, 1); append(a[4], 3, 3); append(a[5], 2, 1); append(a[5], 10, 3); append(a[5], 6, 4); append(a[6], 5, 4); append(a[6], 7, 5); append(a[6], 8, 3); append(a[6], 9, 6); append(a[7], 6, 5); append(a[7], 8, 4); append(a[8], 6, 3); append(a[8], 7, 4); append(a[8], 9, 2); append(a[9], 6, 6); append(a[9], 8, 2); append(a[10], 1, 3); append(a[10], 5, 3); return 10; } int makeedgearray(struct element *a[], struct edge E[], int n) { int i,j; struct element *p; j = 0; for (i = 1; i <= n; i++){ p = a[i]->next; while (p != NULL){ E[++j].u = i; E[j].v = p->vertex; E[j].weight = p->weight; p = p->next; } } return j; } void printedgearray(struct edge E[], int m) { int i; for (i =1; i <= m; i++) printf("(%d,%d) %d\n", E[i].u, E[i].v, E[i].weight); printf("\n"); } void swap(struct edge *e1, struct edge *e2) { struct edge temp; temp=*e1; *e1=*e2; *e2=temp; } void sortedgearray(struct edge E[], int m) { int i,j,min; for(j = 1; j <= m-1; j++){ min = j; for (i = j+1; i <= m; i++) if (E[min].weight > E[i].weight) min = i; swap(&E[j], &E[min]); } } void add(struct element *T[], struct edge e) { append(T[e.u], e.v, e.weight); append(T[e.v], e.u, e.weight); } void initializeuf(int n) { int i; for (i = 1; i <= n; i++){ p[i] = i; rank[i] = 0; } } void unions(int s1,int s2) { if (rank[s1] < rank[s2]) p[s1] = s2; else p[s2] = s1; if (rank[s1] == rank[s2]) ++rank[s1]; } int find(int i) { if (p[i] == i) return(i); else return(find(p[i])); } void kruskal(struct edge E[], struct element *T[], int m, int n) { int i, sizeofT; struct edge e; sortedgearray(E, m); i = 0; createadjlist(T, n); sizeofT = 0; initializeuf(n); while (sizeofT < n-1){ e = E[++i]; if (find(e.u) != find(e.v)){ add(T, e); ++sizeofT; unions(find(e.u), find(e.v)); } } } int main() { int n, m; struct element *a[ASIZE], *T[ASIZE]; struct edge E[ESIZE]; n = makegraph(a); printf("adjlist of G\n"); printadjlist(a, n); m = makeedgearray(a, E, n); sortedgearray(E, m); kruskal(E, T, m, n); printf("adjlist of T\n"); printadjlist(T, n); }
うん。今の時間になぜあがってきたのか疑問だが、どんな結果になるか答えられないと誰もわからないです。法則がわかっているのなら、自力で組み立てられるかもですが解けないのはどこかにわからない部分があるのか、半分理解しているが、時間的な制約があって理解できないのかどちらかだと推測します。
teratailの中で、ググってみたら問題としては最小全域木で与えられた重み付きグラフに対する最小全域木の辺の重みの総和を計算するプログラムを作成すると言うものです、とでてきた。（探索関係なのだろうか）難しそう。私には難しそうなので、解けないが。
回答1件
0
ベストアンサー
私独自のやり方ですが以前にプリム法を用いてコードを作成したことがあったので参考程度に載せておきます。実行時に引数としてファイル名を指定してください。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define NAME_MAX 256 // ファイル名の最大 int main( int argc, char *argv[] ) { int i, j, k; // ループ用変数 int n = 0; int N = 0; // 点の数 int **adjacent; // 隣接行列 2次元配列ポインタ double **dist; // 距離行列 int n1, n2; // ファイルから一時的に読み込む点番号 double n3; // ファイルから一時的に読み込む点番号 FILE *fp; // ファイルポインタ char fn[NAME_MAX]; // ファイル名 int start; int x; // 一時的な点の値 double min_dist; int parent; if ( argc != 2 ) { fprintf( stderr, "Usage: %s graph_file\n", argv[0] ); exit( 1 ); } strcpy( fn, argv[1] ); if (( fp = fopen( fn, "r" )) == NULL ) { fprintf( stderr, "File open error %s\n", fn ); exit( 1 ); } fscanf( fp, "%d", &N ); int MST[N]; int find[N]; //確定点 dist = (double **)malloc(sizeof(double *)*N); adjacent = (int **)malloc(sizeof(int *)*N); for(i=0;i<N;i++){ adjacent[i] = (int *)malloc(sizeof(int)*N); dist[i] = (double *)malloc(sizeof(double)*N); } for(i=0;i<N;i++) for(j=i;j<N;j++) adjacent[i][j] = adjacent[j][i] = 0; while( fscanf( fp, "%d %d %lf", &n1, &n2, &n3 ) != EOF ) { adjacent[n1][n2]++; adjacent[n2][n1]++; dist[n1][n2] = dist[n2][n1] = n3; } fclose(fp); printf("任意点の入力："); scanf("%d",&start); x = start; for(i=0;i<N-1;i++){ find[x] = 1; min_dist = 9999; for(j=0;j<N;j++){ if(find[j] != 1)continue; for(k=0;k<N;k++){ if(find[k]==1 || adjacent[j][k]!=1 )continue; if( min_dist > dist[j][k] ){ min_dist = dist[j][k]; x = k; parent = j; } } } MST[n] = parent; n++; MST[n] = x; n++; } for(i=0;i<n;i++){ printf("( %d, ",MST[i]); printf("%d )\n",MST[i+1]); i++; } for(i=0;i<N;i++){ free(adjacent[i]); free(dist[i]); } free(adjacent); free(dist); return 0; }
10 0 2 21.3 0 3 52.4 0 4 33.4 0 6 67.2 0 7 82.4 0 8 41.1 1 8 16.7 2 3 43.9 2 4 34.3 2 8 65.0 3 9 24.7 4 5 11.3 4 6 77.0 4 7 89.9 5 9 98.7
投稿2020/07/23 16:31
総合スコア48
あなたの回答
tips
プレビュー
