📄 bfs.bak
字号:
outtextxy(120,55,"NHAP DO THI TU BAN PHIM");
forprintf(150,75,"Nhap sai - xin moi nhap lai so dinh : ",LIGHTRED);
forscanf(450,75,dinh);
n=atoi(dinh);
}
forprintf(120,95,"Nhap do thi co huong(1) hay vo huong(0) : ",LIGHTRED);
forscanf(450,95,h1);
h=atoi(h1);
while((h!=1)&&(h!=0))
{
delay(200);
gd();
setcolor(LIGHTRED);
outtextxy(120,55,"NHAP DO THI TU BAN PHIM");
outtextxy(150,75,"So dinh cua do thi la : ");
forprintf(380,75,dinh,LIGHTRED);
outtextxy(130,95,"Nhap sai - Nhap lai ");
forprintf(120,115,"Nhap do thi co huong(1) hay vo huong(0) : ",LIGHTRED);
forscanf(450,115,h1);
h=atoi(h1);
}
outtextxy(150,150,"NHAP MA TRAN KE");
b=b1=170;
for(i=1;i<=n;i++)
{
c=a1=140;
itoa(i,s1,10);
setcolor(GREEN);
outtextxy(c,b1+15,s1);
for(j=1;j<=n;j++)
{
itoa(j,s2,10);
setcolor(GREEN);
outtextxy(a1+30,b,s2);
setcolor(WHITE);
forscanf(a1+22,b1+14,tam);
tam1=atoi(tam);
a[i][j]=tam1;
setcolor(WHITE);
outtextxy(a1+30,b,s2);
a1+=30;
}
setcolor(WHITE);
outtextxy(c,b1+15,s1);
b1+=15;
}
if(h==1)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
while(i==j&&a[i][j]!=0)
{
gd();
setcolor(LIGHTRED);
outtextxy(130,60,"Nhap sai, canh nay phai bang 0");
outtextxy(125,80,"Nhap lai canh ");
itoa(i,temp,10);
itoa(j,temp1,10);
forprintf(240,80,temp,LIGHTRED);
forprintf(249,80,temp1,LIGHTRED);
outtextxy(265,80,"la: ");
forscanf(310,80,temp2);
a[i][j]=atoi(temp2);
if(a[i][j]!=0);
}
}
if(h==0) kiemtrafile1(n,a);
setcolor(GREEN);
outtextxy(125,350,"Ban muon luu tap tin voi ten ( co duong dan ) ");
outtextxy(140,370,"VD: c:\\tentaptin.txt ");
forscanf(200,390,s);
taofile(n,h,a,s);
}
void taofile(int &n,int &h,int a[][max1],char link1[])
{
char tam[25];
FILE *f;
strcpy(tam,link1);
f=fopen(tam,"w+");
while(f==NULL)
{
gd();
setcolor(WHITE);
outtextxy(125,65," Khong tao duoc file co duong dan nhu tren");
outtextxy(125,85,"Nhap lai duong dan luu file");
outtextxy(130,105,"VD c:\\tenfile.txt");
forprintf(125,65,"",LIGHTBLUE);
forscanf(270,125,tam);
f=fopen(tam,"w+");
}
fprintf(f,"%3d\n",n);
if(h==1) fprintf(f,"%3d\n",1);
else fprintf(f,"%3d\n",0);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
fprintf(f,"%4d",a[i][j]);
fprintf(f,"\n");
}
}
void nhaptufile()
{
char link[20];
gd();
setcolor(LIGHTRED);
outtextxy(145,55," NHAP TU FILE");
forprintf(125,75,"Nhap vao duong dan cua file (VD: c:\\thumuc\\file.txt)",LIGHTRED);
forscanf(130,95,link);
f=fopen(link,"r+");
while(f==NULL)
{
gd();
setcolor(LIGHTMAGENTA);
outtextxy(145,55,"NHAP TU FILE");
outtextxy(135,75,"Nhap sai duong dan - Nhap lai");
forprintf(125,95,"Nhap vao duong dan cua file (VD: c:\\tenfile.txt)",LIGHTRED);
forscanf(130,115,link);
f=fopen(link,"rb");
}
doctufile(f);
}
void doctufile(FILE *f)
{
fscanf(f,"%d",&sodinh);
while(((sodinh<0)||(sodinh>16))||(isalpha(sodinh))) nhapsodinh(sodinh);
fscanf(f,"%d",&cohuong);
while(((cohuong!=0)&&(cohuong!=1))&&(isalpha(cohuong))) nhaphuong(cohuong);
for(i=1;i<=sodinh;i++)
for(j=1;j<=sodinh;j++)
fscanf(f,"%d",&canh[i][j]);
if(cohuong==0) kiemtrafile1(sodinh,canh);
}
void kiemtrafile1(int n,int a[][max1])
{
char tam1[1],tam2[2];
char tam3[2];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
while(a[i][j]!=a[j][i])
{
gd();
setcolor(LIGHTRED);
outtextxy(130,60,"Nhap sai, xin moi nhap lai");
outtextxy(125,80,"Nhap lai canh ");
itoa(i,tam1,10);
itoa(j,tam2,10);
forprintf(240,80,tam1,LIGHTRED);
forprintf(249,80,tam2,LIGHTRED);
outtextxy(265,80,"la: ");
forscanf(310,80,tam3);
a[i][j]=atoi(tam3);
a[j][i]=a[i][j];
}
}
}
}
void kiemtra(int n,int a[][max1])
{
int k=0;
int t=400;
int khuyen[10];
char s[2];
khuyen[1]=0;
for(i=1;i<=n;i++)
for(j=1;j<=sodinh;j++)
if((i==j)&&(a[i][i]!=0))
{
itoa(i,s,10);
outtextxy(t,110,s);
t=t+15;
k++;
}
if(k==0) outtextxy(125,110,"Do thi khong co khuyen ");
else outtextxy(125,110,"Do thi co khuyen tai cac dinh la : ");
}
/////////////////// / loadinh chuong trinh//////////////////
void set()
{
int i;
setbkcolor(LIGHTBLUE);
outtextxy(240,441,"Loading.........");
for(i=0;i<64;i++)
{
bar(4+i*10,getmaxy()-24,9+i*10,getmaxy()-5);
}
for(i=0;i<636;i++)
{
line(4+i,getmaxy()-24,4+i,getmaxy()-5);
delay(5);
}
setcolor(BLACK);
outtextxy(240,441,"Loading.........");
for(i=0;i<636;i++)
{
line(4+i,getmaxy()-24,i+4,getmaxy()-5);
setcolor(BLACK);
}
}
////////////// to mau cho dinh////////////////////
void painttop(int x, int y,int mau)
{
delay(500);
setcolor(mau);
circle(x,y,10);
setfillstyle(1,mau);
floodfill(x,y,mau);
}
void drawline()
{
int i;
for(i=0;i<2;i++)
{
setcolor(LIGHTBLUE);
rectangle(2*i,2*i,getmaxx()-2*i,getmaxy()-21-2*i+20);
}
}
/////////// ve mot dinh bat ky //////////////////////
void top(int x, int y, char *s, int mau)
{
int dai;
dai=strlen(s);
circle(x,y,15);
setcolor(mau);
if(dai<=1) outtextxy(x-2,y-2,s);
else outtextxy(x-6,y-4,s);
}
///////////// ve tu dong do thi /////////////////////
void vedinh(int sodinh)
{
int i;
char dinh[2];
setcolor(RED);
for(i=1;i<=sodinh;i++)
{
delay(1000);
itoa(i,dinh,10);
top(v[2*i-2],v[2*i-1]+2,dinh,RED);
}
}
double goc(int x1, int y1, int x2, int y2)
{
double a,b,g;//goc
a=x1-x2;
b=y1-y2;
g=acosl((a)/sqrt(sqm(a)+sqm(b)));
if (y1-y2<0) return 2*pi-g;
else return g;
}
void chi_huong(int x1, int y1, int x2, int y2, int x3, int y3)
{
double anpha;
int xt1,xt2,yt1,yt2,i,j;
anpha=goc(x2,y2,x1,y1);
setcolor(15);
xt1=x3-10*cos(anpha+pi/7);
yt1=y3-10*sin(anpha+pi/7);
xt2=x3-10*cos(anpha-pi/7);
yt2=y3-10*sin(anpha-pi/7);
line(x3,y3,xt1,yt1);
line(x3,y3,xt2,yt2);
line(xt1,yt1,xt2,yt2);
setfillstyle(1,11);
floodfill(((4*xt1+xt2+x3)/6),((4*yt1+yt2+y3)/6),getpixel(x3,y3));
floodfill(((4*xt2+xt1+x3)/6),((4*yt2+yt1+y3)/6),getpixel(x3,y3));
}
void TrongSo(int x1, int y1, int x2, int y2,int so)
{
char *s="";
itoa(so,s,10);
setcolor(15);
outtextxy((x2+x1)/2,(y1+y2)/2,s);
setcolor(4);
}
void vedt(int n,int a[15][15])
{
int i,j,z,x9,y9;
setcolor(RED);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if((a[i][j]>0)&&(a[j][i]<16))
{
line(v[2*(i-1)],v[2*(i-1)+1],v[2*(j-1)],v[2*(j-1)+1]);
TrongSo(v[2*(i-1)],v[2*(i-1)+1],v[2*(j-1)],v[2*(j-1)+1],a[i][j]);
}
}
for(z=0;z<n;z++)
{
x9=2*z;
y9=2*z+1;
setcolor(14);
setfillstyle(1,12);
fillellipse(v[x9],v[y9],10,10);
if(z<9) outtextxy(v[x9]-2,v[y9]-5,D[z]);
else if(z>=9 && z<15) outtextxy(v[x9]-7,v[y9]-4,D[z]);
}
}
void vedtcohuong(int n ,int a[15][15])
{
int i,j,z,x9,y9;
setcolor(RED);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]>0)
{
setcolor(13);
line(v[2*(i-1)],v[2*(i-1)+1],v[(j-1)*2],v[2*(j-1)+1]);
chi_huong(v[2*(i-1)],v[2*(i-1)+1],v[(j-1)*2],v[2*(j-1)+1],((v[2*(i-1)]+v[2*(j-1)])/2+v[2*(j-1)])/2,((v[2*(i-1)+1]+v[2*(j-1)+1])/2+v[2*(j-1)+1])/2);
TrongSo(v[2*(i-1)],v[2*(i-1)+1],v[(j-1)*2],v[2*(j-1)+1],a[i][j]);
}
for(z=0;z<n;z++)
{
x9=2*z;
y9=2*z+1;
setcolor(8);
setfillstyle(1,14);
fillellipse(v[x9],v[y9],10,10);
if(z<9) outtextxy(v[x9]-2,v[y9]-5,D[z]);
else if(z>=9 && z<15) outtextxy(v[x9]-7,v[y9]-4,D[z]);
}
}
void vedtlenmanhinh(int h)
{
// opengraph();
// cleardevice();
// setfillstyle(1,BLACK);
// bar(0,0,getmaxx(),getmaxy());
if(h==0) vedt(sodinh,canh);
else vedtcohuong(sodinh,canh);
}
void Draw_circle(int x, int y, int num, int mauvien,int maunen, int mauso)
{
int dai;
char s[3];
itoa(num,s,10);
dai=strlen(s);
setcolor(mauvien);
setfillstyle(SOLID_FILL,maunen);
fillellipse(x,y,10,10);
setcolor(mauso);
if(dai<=1) outtextxy(x-2,y-2,s);
else outtextxy(x-8,y-2,s);
}
////////////DFS///////////////////////////////////////
void mtketodske(int a[][15])
{
int i,j;
for(i=1;i<=sodinh;i++)
{
ke[i]=NULL;
chuaxet[i]=1;
index[i]=1;
}
for(i=1;i<=sodinh;i++)
for(j=1;j<=sodinh;j++)
{
struct node *p;
if(a[i][j])
{
p=(node*)malloc(sizeof(node));
if(p==NULL) return;
p->data=j;
p->next=NULL;
if(ke[i]==NULL)
ke[i]=p;
else
{
node *temp;
temp=ke[i];
while(temp->next!=NULL)
temp=temp->next;
temp->next=p;
}
}
}
}
void DFS(int s)
{
struct node *p;
chuaxet[s]=0;
int tam[15];
int k=0;
char h[3];
// outtextxy(50,405,"Ket qua duyet: ");
for(p=ke[s];p!=NULL;p=p->next)
{
if(chuaxet[p->data]==1)
{
tam[k]=p->data;
Draw_circle(v[tam[k]*2-2],v[tam[k]*2-1],tam[k],1,1,13);
setcolor(WHITE);
itoa(tam[k],h,10);
tDFS=tDFS+30;
vitriDFS[p->data]=tDFS;
outtextxy(tDFS,405,h);
sleep(2);
k++;
DFS(p->data);
}
}
}
/////////////////////////ket thuc DFS///////////////////////////
/////////////////////BFS khong de quy///////////////////////////////////////
void BFS(int s, int y)
{
int u,dauq=1,cuoiq=1,p;
int tam[15];
int k=0;
int j=1;
int t=200;
char h[3];
queue[dauq]=s;
chuaxet[s]=0 ;
tam[k]=s;
k++;
truoc[1]=s;
while(dauq<=cuoiq)
{
u=queue[dauq];
dauq=dauq+1;
for(p=1; p<=sodinh; p++)
if(canh[u][p]==1 && chuaxet[p]==1)
{
truoc[p]=u;
cuoiq=cuoiq+1;
queue[cuoiq]=p;
chuaxet[p]=0;
tam[k]=p;
k++;
if(p==y)
break;
}
}
outtextxy(50,405,"Ket qua duyet: ");
for(j=1;j<k;j++)
{
Draw_circle(v[tam[j]*2-2],v[tam[j]*2-1],tam[j],1,1,13);
setcolor(WHITE);
itoa(tam[j],h,10);
outtextxy(t,405,h);
t=t+30;
sleep(2);
}
}
//////////////////////////BFS de quy/////////////////////////////////////
void BFSDQ(int s)
{
int j;
int tem[15];
int tam[15];
char h[3];
int k=0;
// int t=200;
for(j=1;j<=sodinh;j++)
tem[j]=1;
chuaxet[s]=0;
for(j=1;j<=sodinh;j++)
{
if(canh[s][j]==1 && chuaxet[j]==1)
{
chuaxet[j]=0;
tem[j]=0;
tam[k]=j;
k++;
}
}
outtextxy(50,405,"Ket qua duyet: ");
for(j=0;j<k;j++)
{
Draw_circle(v[tam[j]*2-2],v[tam[j]*2-1],tam[j],1,1,13);
setcolor(WHITE);
itoa(tam[j],h,10);
outtextxy(tBFSDQ,405,h);
tBFSDQ=tBFSDQ+30;
sleep(2);
}
for(j=0;j<k;j++)
BFSDQ(tam[j]);
tBFSDQ=200;
}
void BFSaction(int m)
{
char *tam;
char dinh[2],dinhcuoi[2];
char so[2];
int begin,goal,star1,star2,k;
for(i=1;i<=sodinh;i++)
chuaxet[i]=1;
itoa(sodinh,so,10);
outtextxy(150,50,"QUA TRINH DUYET BFS ");
forprintf(120,70,"Nhap vao dinh dau : ",YELLOW);
forscanf(370,70,dinh);
// forprintf(120,80,"Nhap vao dinh cuoi : ",YELLOW);
//forscanf(370,80,dinhcuoi);
star1=atoi(dinh);
// star2=atoi(dinhcuoi);
while((star1<1)||(star1>sodinh))
{
clrscr();
// gd_dothi();
// vedtlenmanhinh(cohuong);
setcolor(LIGHTRED);
outtextxy(150,25,"QUA TRINH DUYET BFS");
outtextxy(140,50,"Nhap sai - Nhap lai");
gd_dothi();
// vedtlenmanhinh(cohuong);
forprintf(120,75,"Nhap vao dinh dau : ",YELLOW);
forscanf(400,75,dinh);
// forprintf(120,75,"Nhap vao dinh cuoi : ",YELLOW);
// forscanf(700,75,dinhcuoi);
star1=atoi(dinh);
// s1=star1;
// star2=atoi(dinhcuoi);
}
if(m==1)
BFS(star1,star2);
if(m==0)
BFSDQ(star1);
char h[3];
if(m==2)
{
mtketodske(canh);
itoa(star1,h,10);
outtextxy(tDFS,350,h);
DFS(star1);
}
outtextxy(50,430,"Qua trinh duyet hoan tat");
}
///////////////// thoat khoi chuong trinh ///////////
void thoat()
{
int ch;
int ESC=27;
outtextxy(240,441,"Nhan ESC de thoat khoi chuong trinh");
if(kbhit())
{
ch=getch();
if(ch==ESC)
{
delay(1000);
shutdow();
}
}
}
void opengraph()
{
int mh=0,mode=0;
initgraph(&mh,&mode,"C:\\TC\\BGI");
}
/////////////////////////// Phan chuong trinh chinh //////////////////////////////////////
void main()
{
start_graphics();
spacemouse();
control_program();
getch();
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -