dây là thuật toán tìm kiếm BFS
em làm hoài mà nó cai g.previous cu sai hoai a
cái hàng đợi nó bị cái gi ý
de bai:
n=7
start=0 end=5
0 1 0 0 0 0 1
1 0 1 0 0 0 0
0 1 0 1 1 0 1
0 0 1 0 1 0 1
0 0 1 1 0 1 0
0 0 0 0 1 0 1
1 0 1 1 0 1 0
Mã:
// BFS.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#define max 100
struct MYGRAPH
{
int n;
int start,end;
int A[max][max];
int previous[max];
int nhan[max];
};
struct QUEUE
{
int *Qarray;
int QnumiTems;
int QFront;
int QRear;
int Qmax;
};
void InputGraph(MYGRAPH &g)
{
FILE *f;
f = fopen ("E:\input.txt","rt");
if(f==NULL)
{
printf("Khong mo duoc File!
");
return;
}
fscanf(f,"%d",&g.n);
fscanf(f,"%d %d",&g.start,&g.end);
for(int i=0;i<g.n;i++)
{
for(int j=0;j<g.n;j++)
{
fscanf(f,"%d",&g.A[i][j]);
}
}
fclose(f);
printf("Lay thong tin Ma Tran thanh cong!
");
}
void outputGraph(MYGRAPH g)
{
printf("So dinh: %d
",g.n);
printf("diem dau: %d
",g.start);
printf("diem cuoi: %d
",g.end);
for(int i=0;i<g.n;i++)
{
for(int j=0;j<g.n;j++)
{
printf("%d ",g.A[i][j]);
}
printf("
");
}
}
int InitQUEUE(QUEUE &Q,int maxitems)//khoi tao Q
{
Q.Qarray = new int [maxitems];
if(Q.Qarray == NULL)
return 0;
Q.Qmax=maxitems;
Q.QnumiTems=0;
Q.QFront =Q.QRear =-1;
return 1;
}
int IsQueueEmpty(const QUEUE &Q)//kt Q rong
{
if(Q.QnumiTems==0)
return 1;
return 0;
}
int IsQueueFull(const QUEUE &Q)//kt Q day
{
if(Q.QnumiTems==Q.Qmax)
return 1;
return 0;
}
int EnQueue(QUEUE &Q,int newitems)//them phan tu vao cuoi
{
if(IsQueueFull(Q)==1)
return 0;
Q.QRear++;
if(Q.QRear ==Q.Qmax)
Q.QRear =0;
Q.Qarray[Q.QRear]=newitems;
if(IsQueueEmpty(Q)==1)
Q.QFront=0;
Q.QnumiTems++;
return 1;
}
int DeQueue(QUEUE &Q,int outitems)//lay phan tu o dau
{
if(IsQueueEmpty(Q)==1)
return 0;
outitems=Q.Qarray[Q.QFront];
Q.QFront ++;
Q.QnumiTems--;
if(Q.QFront==Q.Qmax)
Q.QFront =0;
if(IsQueueEmpty(Q)==1)
Q.QFront=Q.QRear=-1;
return outitems;
}
int QueueFront(const QUEUE &Q,int &outitme)//kt phan tu o dau Q
{
if(IsQueueEmpty(Q)==1)
return 0;
if(outitme==Q.Qarray[Q.QFront])
return 1;
return 0;
}
int QueueRear(const QUEUE &Q,int &outitme)//kt phan tu o cuoi Q
{
if(IsQueueEmpty(Q)==1)
return 0;
if(outitme==Q.Qarray[Q.QRear])
return 1;
return 0;
}
int BFS(MYGRAPH &g)
{
int flag = 0;
int v;
int outitems=0;
QUEUE Q;
int MAX=10;
for(int i=0;i<=6;i++)
{
g.previous[i]=-1;
g.nhan[i]=0;
}
InitQUEUE(Q,MAX);
EnQueue(Q,g.start);
while(IsQueueEmpty(Q)!=1 && flag==0)
{
v=DeQueue(Q,outitems);
for(int j=0;j<=6;j++)
{
if(g.A[v][j]==1 && g.nhan[j]==0)
{
g.previous[j]=v;
g.nhan[j]=1;
EnQueue(Q,j);
}
if(QueueFront(Q,g.end)==1 )
{
flag=1;
}
}
}
return flag;
}
void PrintPath(MYGRAPH g)
{
printf("
%d",g.end);
int i=g.end ;
do{
i=g.previous[i];
printf("<- %d",i);
}while(i>-1);
}
void main()
{
MYGRAPH g;
InputGraph(g);
outputGraph(g);
printf("----------------------------------
");
int kq=BFS(g);
printf("kq %d
",kq);
for(int j=0;j<=g.end;j++)
{
printf("%d<>",g.previous[j]);
}
// PrintPath(g);
}
View more random threads:
Thông qua phân tích dữ liệu Google từ 86 quốc gia, mới đây, một công ty tại Anh đã công bố bảng xếp hạng kích tấc "cậu nhỏ" của các nước trên thế giới. Kết quả, hầu hết các nước xếp ở nhóm đầu của...
"Chim" của chàng trai Việt thuộc...