Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» 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

» Giá của món quà
Fri Apr 13, 2012 6:01 am by Admin

» Sẽ chỉ yêu ai?
Fri Apr 13, 2012 6:01 am by Admin

» Cách đọc bảng chữ cái!
Thu Apr 12, 2012 10:37 pm by Admin

» Gắn trojan, keylog, virus vào website, forum
Tue Apr 10, 2012 1:14 am 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
avatar
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