HACKIS - Hacking Internet Security
Would you like to react to this message? Create an account in a few clicks or log in to continue.
Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyThu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyThu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyMon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyTue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyTue Apr 17, 2012 10:03 pm by Admin

» Giá của món quà
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyFri Apr 13, 2012 6:01 am by Admin

» Sẽ chỉ yêu ai?
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyFri Apr 13, 2012 6:01 am by Admin

» Cách đọc bảng chữ cái!
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyThu Apr 12, 2012 10:37 pm by Admin

» Gắn trojan, keylog, virus vào website, forum
Tìm Cây Phụ Tối Tiểu (Thuật Toán PRIM) EmptyTue Apr 10, 2012 1:14 am by Admin

Affiliates
free forum


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

Go down

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

Post  Admin 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
Admin

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

https://hackis.forumvi.com

Back to top Go down

Back to top

- Similar topics

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