# Đề tài: [ Solved ]Giải thuật Prim !

1.  Thành viên mới Ngày gia nhập
04 2008
Bài viết
1

## [ Solved ]Giải thuật Prim !

các anh ơi,cho em hỏi để viết chương trình bài toán tìm đường đi ngắn nhất bằng giải thuật prim viết trên ngôn ngữ lập trình c thì phải làm sao.xin cho em 1 vd cu thể giúp e với

Vui lòng post Tiếng Việt có dấu cho tiêu đề nhé cậu ! Thân !
Đã được chỉnh sửa lần cuối bởi rox_rook : 23-04-2008 lúc 09:23 AM. 2. Nguyên bản được gửi bởi phubaby các anh ơi,cho em hỏi để viết chương trình bài toán tìm đường đi ngắn nhất bằng giải thuật prim viết trên ngôn ngữ lập trình c thì phải làm sao.
Bạn cần phải

- Trình bày giải thuật bằng ngôn ngữ tự nhiên (tiếng Việt) hay giả mã (ngôn ngữ pha trộn giữa ngôn ngữ lập trình và ngôn ngữ tự nhiên).

- Nêu rõ những điểm nào trong giải thuật đã làm bạn thắc mắc và cần giúp đỡ để diễn đạt bằng ngôn ngữ C. 3. There C Code:
1. #include <cstdio>
2.
3. /*The input file :
4.         4
5.         0 0 0 21
6.         0 0 8 17
7.         0 8 0 16
8.         21 17 16 0
9.
10.     The first line contains n, the number of nodes.
11.     Next is an nxn matrix containg the distances between the nodes
12.     NOTE: The distance between a node and itself should be 0
13. */
14.
15. int n; /* The number of nodes in the graph */
16.
17. int weight; /* weight[i][j] is the distance between node i and node j;
18.             if there is no path between i and j, weight[i][j] should
19.             be 0 */
20.
21. char inTree; /* inTree[i] is 1 if the node i is already in the minimum
22.             spanning tree; 0 otherwise*/
23.
24. int d; /* d[i] is the distance between node i and the minimum spanning
25.         tree; this is initially infinity (100000); if i is already in
26.         the tree, then d[i] is undefined;
27.         this is just a temporary variable. It's not necessary but speeds
28.         up execution considerably (by a factor of n) */
29.
30. int whoTo; /* whoTo[i] holds the index of the node i would have to be
31.             linked to in order to get a distance of d[i] */
32.
33. /* updateDistances(int target)
34.     should be called immediately after target is added to the tree;
35.     updates d so that the values are correct (goes through target's
36.     neighbours making sure that the distances between them and the tree
37.     are indeed minimum)
38. */
39. void updateDistances(int target){
40.     int i;
41.     for (i = 0; i < n; ++i)
42.         if ((weight[target][i] != 0) && (d[i] > weight[target][i])){
43.             d[i] = weight[target][i];
44.             whoTo[i] = target;
45.         }
46. }
47.
48. int main(int argc, char *argv[]){
49.     FILE *f = fopen("dist.txt", "r");
50.     fscanf(f, "%d", &n);
51.     int i, j;
52.     for(i = 0; i < n; ++i)
53.         for (j = 0; j < n; ++j)
54.             fscanf(f, "%d", &weight[i][j]);
55.     fclose(f);
56.
57.     /* Initialise d with infinity */
58.     for(i = 0; i < n; ++i)
59.         d[i] = 100000;
60.
61.     /* Mark all nodes as NOT beeing in the minimum spanning tree */
62.     for (i = 0; i < n; ++i)
63.         inTree[i] = 0;
64.
65.     /* Add the first node to the tree */
66.     printf("Adding node %c\n", 0 + 'A');
67.     inTree = 1;
68.     updateDistances(0);
69.
70.     int total = 0;
71.     int treeSize;
72.     for (treeSize = 1; treeSize < n; ++treeSize) {
73.         /* Find the node with the smallest distance to the tree */
74.         int min = -1;
75.         for (i = 0; i < n; ++i)
76.             if (!inTree[i])
77.                 if ((min == -1) || (d[min] > d[i]))
78.                     min = i;
79.
80.         /* And add it */
81.         printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
82.         inTree[min] = 1;
83.         total += d[min];
84.
85.         updateDistances(min);
86.     }
87.   printf("Total distance: %d\n", total);
88.
89.     return 0;
90. } 4. C Code:
1. #include<stdio.h>
2. #include<conio.h>
3. #include<dos.h>
4. #define max 50
5. typedef struct Canh{
6.   int d,c,ts;
7. };
8. void nhap(Canh A[max],int *m,int *n){
9.   int mx=0;
10.   printf("\n Nhap so canh: ");
11.   scanf("%d",m);
12.   for(int i=1;i<=*m;i++){
13.     printf("\n Nhap canh(%d)(dau,cuoi,t_so):",i);
14.     scanf("%d%d%d",&A[i].d,&A[i].c,&A[i].ts);
15.     if(A[i].d>mx) mx=A[i].d;
16.     if(A[i].c>mx) mx=A[i].c;
17.   }
18.   *n=mx;
19. }
20. void sx(Canh A[max],int m){
21. Canh tg;
22.   for(int i=1;i<m;i++)
23.     for(int j=i+1;j<=m;j++)
24.       if(A[j].ts<A[i].ts){
25.     tg=A[i];
26.     A[i]=A[j];
27.     A[j]=tg;
28.       }
29. }
30. void hienc(Canh A[max],int m){
31.   for(int i=1;i<=m;i++)
32.     printf("\n(%d)(%d,%d,%d)",i,A[i].d,A[i].c,A[i].ts);
33. }
34. int KT(Canh A,int D[max],int n){
35.   int a=0,b=0;
36.   for(int i=1;i<=n;i++){
37.     if(D[A.d]==1){a=1;}
38.     if(D[A.c]==1){b=1;}
39.   }
40.   return (a+b);
41. }
42. void Prim(Canh A[max],int m,int n){
43.   int D[max],cx[max],d=1,TS,kt;
44.   for(int i=1;i<=n;i++){
45.     if(i==A.d||i==A.c)
46.       D[i]=1;
47.     else
48.       D[i]=0;
49.   }
50.   for(i=2;i<=m;i++)
51.     cx[i]=0;
52.     cx=1;
53.     printf("\n Chon duoc.");
54.     printf("(%d)(%d%d%d)",d,A.d,A.c,A.ts);
55.     TS=A.ts;
56.     nh:
57.   do{
58.     for(i=2;i<=m;i++){
59.       kt=KT(A[i],D,n);
60.       if(cx[i]==0&&kt==1){
61.     d++;
62.     printf("\n Chon duoc.");
63.     printf("(%d)(%d%d%d)",i,A[i].d,A[i].c,A[i].ts);
64.     TS+=A[i].ts;
65.     cx[i]=1;
66.     for(int j=1;j<=n;j++){
67.         D[A[i].d]=1;
68.         D[A[i].c]=1;
69.       }
70.     delay(500);
71.     goto nh;
72.       }
73.     }
74.   }while(d!=n-1);
75.   printf("\n Tong trong so : %d",TS);
76. }
77. void main(){
78.   Canh A[max];
79.   int m,n;
80.   char lc;
81.   clrscr();
82.   nhap(A,&m,&n);
83.   printf("\n so canh: %d , so dinh : %d",m,n);
84.   sx(A,m);
85.   hienc(A,m);
86.   do{
87.     printf("\n Tim cay khung nho nhat:");
88.     printf("\n 1.Prim...");
89.     printf("\n 2. Thoat..");
90.     lc=getch();
91.     switch(lc){
92.       case '1':
93.     printf("\n Tim theo Prim.\n ");
94.     Prim(A,m,n);
95.     getch();
96.     break;
97.       }
98.   }while(lc!='2');
99. }

Code Prim = C đó , bạn hiểu thì chia sẻ cho mình với nhá ^^ #### Quyền hạn của bạn

• Bạn không thể gửi đề tài mới
• Bạn không thể gửi bài trả lời
• Bạn không thể gửi các đính kèm
• Bạn không thể chỉnh sửa bài viết của bạn