5. Ïpèëîæåíèå:

Òåêñòû ïpîãpàìì íà ÿçûêå Ñ

/* File prim.c   Òåîpèÿ ãpàôîâ                                ÐÊ6 Ðåäíèêèí À.H.  1996ã.           */

/* Àëãîpèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà âî âçâåøåííîì ãpàôå         */

/* Ð.Ïpèì, 1957 ã.                                                                                                                           */

#include <stdio.h>

#include <stdlib.h>

#include <float.h>

int load_matrix(int n, double* weigh);          /* Ââîä ìàòpèöû âåñîâ      */

int prim(int n, double* weigh);                             /* Àëãîpèòì ïîèñêà                   */

void print(int n, double* weigh);                         /* Âûâîä påçóëüòàòà                   */

void main(void){

      int n=0,ret=0;

      double *weigh;

      printf("\nÀëãîpèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà âî âçâåøåííîì ãpàôå.\n");

      printf("Ð.Ïpèì, 1957 ã.\n");

      printf("\nÂâåäèòå êîëè÷åñòâî âåpøèí..");

      scanf("%d",&n);

      if (n <= 1){

             printf("\nÊîëè÷åñòâî âåpøèí äîëæíî áûòü áîëüøå åäèíèöû!\n");

             exit(1);

      }

      weigh=malloc(sizeof(double)*n*n);

      if (weigh == NULL){

             printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ çàãpóçêè ìàññèâà!\n");

             exit(2);

      }

      ret=load_matrix(n,weigh);

      if (ret != 0){

             printf("\nÎøèáêà ââîäà äàííûõ!\n");

             exit(5);

      }

      ret=prim(n,weigh);

      if (ret != 0){

             switch (ret){

                   case 1 :

                         printf("\nÃpàô íå ÿâëÿåòñÿ ñâÿçàííûì!\n");

                         exit(3);

                   case 2 :

                         printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ pàáîòû!\n");

                         exit(4);

             }

      }

      print(n,weigh);

      free(weigh);

}

int load_matrix(int n, double* weigh){

      int i,j,k;

      double tmp;

      for (i=0; i < n; i++){

             for (j=0; j < n; j++){

                   weigh[n*i+j]=(-1);

             }

      }

      printf("\nÂâåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.");

      for (i=0; i < n; i++){

             for (j=i+1; j < n; j++){

                   printf("\nÂåpøèíû %d è %d ",i+1,j+1);

                   k=scanf("%lf",&tmp);

                   if (k != 1){return(1);}

                   weigh[i*n+j]=tmp;

             }

      }

      return(0);

}

int prim(int n, double* weigh){

      int i,j,k,l,m,flag;

      int* index;

      double tmp;

      index=calloc(sizeof(int),n);

      if (index == NULL){return(2);}

      index[0]=1;

      for (k=0; k < (n-1); k++){

             for (i=0,flag=0,tmp=DBL_MAX; i < n; i++){

                   for (j=i+1; j < n; j++){

                         if    ((weigh[i*n+j] < tmp)&&

                                (weigh[i*n+j] >= 0)&&

                                (weigh[j*n+i] == (-1))&&

                                (index[i]*index[j] == 0)&&

                                (index[i]+index[j] == 1)){

                                flag=1;

                                tmp=weigh[i*n+j];

                                l=i;

                                m=j;

                         }

                   }

             }

             if (flag == 1){

                   weigh[m*n+l]=tmp;

                   index[m]=1;

                   index[l]=1;

             }

      }

      for (i=0; i < n; i++){

             if (index[i] == 0)

             return(1);

      }

      free(index);

      return(0);

}

void print(int n, double* weigh){

      int i,j;

      double tmp=0.0;

      printf("\nÎñòîâ ìèíèìàëüíîãî âåñà:");

      for (i=0; i < n; i++){

             printf("\n");

             for (j=(i+1); j < n; j++){

                   if (weigh[j*n+i] != (-1)){

                         printf(" weigh[%d,%d]=%6.2f",i+1,j+1,weigh[j*n+i]);

                          tmp+=weigh[j*n+i];

                   }

             }

      }

      printf("\nÂåñ íàéäåííîãî äåpåâà: %6.2f\n",tmp);

}

Òåñòîâûé ïðèìåð èç ðàáîòû [1] (ðèñ.6 íà ñòð. 9).

Àëãîpèòì ïîèñêà îñòîâà ìèíèìàëüíîãî âåñà âî âçâåøåííîì ãpàôå.

Ð.Ïpèì, 1957 ã.

Ââåäèòå êîëè÷åñòâî âåpøèí.. 6

Ââåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.

Âåpøèíû 1 è 2   3

Âåpøèíû 1 è 3  -1

Âåpøèíû 1 è 4  -1

Âåpøèíû 1 è 5  -1

Âåpøèíû 1 è 6   1

Âåpøèíû 2 è 3   1

Âåpøèíû 2 è 4  -1

Âåpøèíû 2 è 5   1

Âåpøèíû 2 è 6   2

Âåpøèíû 3 è 4   4

Âåpøèíû 3 è 5  -1

Âåpøèíû 3 è 6  -1

Âåpøèíû 4 è 5   6

Âåpøèíû 4 è 6  -1

Âåpøèíû 5 è 6   2

Îñòîâ ìèíèìàëüíîãî âåñà:

 weigh[1,6]=  1.00

 weigh[2,3]=  1.00 weigh[2,5]=  1.00 weigh[2,6]=  2.00

 weigh[3,4]=  4.00

Âåñ íàéäåííîãî äåpåâà:   9.00

/* File deik.c   Òåîpèÿ ãpàôîâ        ÐÊ6 Ðåäíèêèí À.H.  1996ã. */

Страницы: 1, 2, 3, 4, 5, 6, 7