Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Thu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin

Shopmotion


Affiliates
free forum


Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)

View previous topic View next topic Go down

Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM)

Post  Admin on Wed Jun 15, 2011 10:41 pm

Code:

Code:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <values.h>
#define fi "D:\\PRIM.INP"
#define fo "D:\\PRIM.OUT"

int    error=0,
  V, dd[100],
  G[100][100];
  KQ[100][100];

void input(){
  FILE *f;
  int s;
  f = fopen(fi,"r");

  if (f!=NULL){
      if (fscanf(f,"%d\n",&s))
        V=s;
      else {error=1; exit;}
      for (int i=0; i<V; i++){
        for (int j=0; j<V; j++)
            if (fscanf(f,"%d",&s))
              G[i][j]=s;
            else {error=1; exit;}
        fscanf(f,"\n");
      }
  }
  else error=1;
  fclose(f);
}
void init(){
  for (int i=0; i<100; i++){
      dd[i]=0;
      for (int j=0; j<100; j++)
        KQ[i][j]=0;
  }
}
void xuly(){
  int min = MAXINT, x, y;
  for (int i=0; i<V; i++)
  for (int j=0; j<V; j++)
      if ((G[i][j]>0)&&(G[i][j]<min)){
        x=i;
        y=j;
        min=G[x][y];
      }

  KQ[x][y]=G[x][y];
  KQ[y][x]=G[y][x];
  dd[x]=1;
  dd[y]=1;
  for (int s=2; s<V; s++){
      min = MAXINT;
      for (i=0; i<V; i++)
      for (j=0; j<V; j++)
        if ((G[i][j])&&(G[i][j]<min)&&(dd[i])&&(!dd[j])){
        x=i;
        y=j;
        min=G[x][y];
      }
      KQ[x][y]=G[x][y];
      KQ[y][x]=G[y][x];
      dd[x]=1;
      dd[y]=1;
  }
}
void output(){
  FILE *f;
  f = fopen(fo,"w");
  fprintf(f,"%d\n",V);
  for (int i=0; i<V; i++){
      for (int j=0; j<V; j++)
        fprintf(f,"%3d",KQ[i][j]);
      fprintf(f,"\n");
  }
  fclose(f);
}
void BFS(){
  int stack[100], dinh, spt;
  dd[0]=1;
  stack[0]=0;
  spt=1;
  while (spt>0){
      spt--;
      dinh=stack[spt];
      for (int i=0; i<V; i++)
        if (G[dinh][i] &&  !dd[i]){
            dd[i]=1;
            stack[spt]=i;
            spt++;
        }
  }
}
int LienThong(){
  for (int i=0; i<V; i++)
      dd[i]=0;
  BFS();
  for (i=0; i<V; i++)
      if (!dd[i])
        return 0;
  return 1;
}

void main(){
  input();
  clrscr();
  if (!error){
      if (LienThong()){
        init();
        xuly();
        output();
      }
      else{
        printf("\n\nDo thi khong LIEN THONG lam sao co cay phu toi tieu?");
        getch();
      }
  }
  else{
      printf("\n\nLoi khong tim thay file input hoac noi dung file input sai cu phap");
      getch();
  }
}

File input mẫu:

Code:
6
 0 10  0  0  0 30
10  0 50 20  0 50
 0 50  0 30  0  0
 0 20 30  0 40 70
 0  0  0 40  0 60
30 50  0 70 60  0

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum