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);
    
}