[ Solved ]Giải thuật Prim !

[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.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 !

[Ada]

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.

[rox_rook]

There

#include <cstdio> /*The input file :        4        0 0 0 21        0 0 8 17        0 8 0 16        21 17 16 0     The first line contains n, the number of nodes.    Next is an nxn matrix containg the distances between the nodes    NOTE: The distance between a node and itself should be 0*/ int n; /* The number of nodes in the graph */ int weight[100][100]; /* weight[i][j] is the distance between node i and node j;            if there is no path between i and j, weight[i][j] should            be 0 */ char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum            spanning tree; 0 otherwise*/ int d[100]; /* d[i] is the distance between node i and the minimum spanning        tree; this is initially infinity (100000); if i is already in        the tree, then d[i] is undefined;        this is just a temporary variable. It's not necessary but speeds        up execution considerably (by a factor of n) */ int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be            linked to in order to get a distance of d[i] */ /* updateDistances(int target)    should be called immediately after target is added to the tree;    updates d so that the values are correct (goes through target's    neighbours making sure that the distances between them and the tree    are indeed minimum)*/void updateDistances(int target){    int i;    for (i = 0; i < n; ++i)        if ((weight[target][i] != 0) && (d[i] > weight[target][i])){            d[i] = weight[target][i];            whoTo[i] = target;        }} int main(int argc, char *argv[]){    FILE *f = fopen("dist.txt", "r");    fscanf(f, "%d", &n);    int i, j;    for(i = 0; i < n; ++i)        for (j = 0; j < n; ++j)            fscanf(f, "%d", &weight[i][j]);    fclose(f);     /* Initialise d with infinity */    for(i = 0; i < n; ++i)        d[i] = 100000;     /* Mark all nodes as NOT beeing in the minimum spanning tree */    for (i = 0; i < n; ++i)        inTree[i] = 0;     /* Add the first node to the tree */    printf("Adding node %c\n", 0 + 'A');    inTree[0] = 1;    updateDistances(0);     int total = 0;    int treeSize;    for (treeSize = 1; treeSize < n; ++treeSize) {        /* Find the node with the smallest distance to the tree */        int min = -1;        for (i = 0; i < n; ++i)            if (!inTree[i])                if ((min == -1) || (d[min] > d[i]))                    min = i;         /* And add it */        printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');        inTree[min] = 1;        total += d[min];         updateDistances(min);    }  printf("Total distance: %d\n", total);     return 0;}

[sieuphuong]

#include<stdio.h>#include<conio.h>#include<dos.h>#define max 50typedef struct Canh{  int d,c,ts;};void nhap(Canh A[max],int *m,int *n){  int mx=0;  printf("\n Nhap so canh: ");  scanf("%d",m);  for(int i=1;i<=*m;i++){    printf("\n Nhap canh(%d)(dau,cuoi,t_so):",i);    scanf("%d%d%d",&A[i].d,&A[i].c,&A[i].ts);    if(A[i].d>mx) mx=A[i].d;    if(A[i].c>mx) mx=A[i].c;  }  *n=mx;}void sx(Canh A[max],int m){Canh tg;  for(int i=1;i<m;i++)    for(int j=i+1;j<=m;j++)      if(A[j].ts<A[i].ts){    tg=A[i];    A[i]=A[j];    A[j]=tg;      }}void hienc(Canh A[max],int m){  for(int i=1;i<=m;i++)    printf("\n(%d)(%d,%d,%d)",i,A[i].d,A[i].c,A[i].ts);}int KT(Canh A,int D[max],int n){  int a=0,b=0;  for(int i=1;i<=n;i++){    if(D[A.d]==1){a=1;}    if(D[A.c]==1){b=1;}  }  return (a+b);}void Prim(Canh A[max],int m,int n){  int D[max],cx[max],d=1,TS,kt;  for(int i=1;i<=n;i++){    if(i==A[1].d||i==A[1].c)      D[i]=1;    else      D[i]=0;  }  for(i=2;i<=m;i++)    cx[i]=0;    cx[1]=1;    printf("\n Chon duoc.");    printf("(%d)(%d%d%d)",d,A[1].d,A[1].c,A[1].ts);    TS=A[1].ts;    nh:  do{    for(i=2;i<=m;i++){      kt=KT(A[i],D,n);      if(cx[i]==0&&kt==1){    d++;    printf("\n Chon duoc.");    printf("(%d)(%d%d%d)",i,A[i].d,A[i].c,A[i].ts);    TS+=A[i].ts;    cx[i]=1;    for(int j=1;j<=n;j++){        D[A[i].d]=1;        D[A[i].c]=1;      }    delay(500);    goto nh;      }    }  }while(d!=n-1);  printf("\n Tong trong so : %d",TS);}void main(){  Canh A[max];  int m,n;  char lc;  clrscr();  nhap(A,&m,&n);  printf("\n so canh: %d , so dinh : %d",m,n);  sx(A,m);  hienc(A,m);  do{    printf("\n Tim cay khung nho nhat:");    printf("\n 1.Prim...");    printf("\n 2. Thoat..");    lc=getch();    switch(lc){      case '1':    printf("\n Tim theo Prim.\n ");    Prim(A,m,n);    getch();    break;      }  }while(lc!='2');}

Code Prim = C đó , bạn hiểu thì chia sẻ cho mình với nhá ^^