bfs.cpp

数据结构里的bfs算法

#include <iostream.h>

const int nmax=100;

typedef struct
{
	int data[nmax+1];    
    int adjmat[nmax+1][nmax+1];   
    int n,e;             
}mat_graph;

typedef struct 
{
	int data[nmax];
	int front,rear;
}sqqueue;

void bfs(mat_graph ga, int v); 
void init_sqqueue(sqqueue Q);
int empty_sqqueue(sqqueue Q);
int en_sqqueue(sqqueue Q,int);
int de_sqqueue(sqqueue Q,int); 
void main()
{
	mat_graph ga;
	int i,j;
    ga.n=4;
	ga.e=4;
	ga.adjmat[1][2]=1;
	ga.adjmat[2][3]=1;
	ga.adjmat[3][1]=1;
	ga.adjmat[1][4]=1;
	bfs(ga,1);
}
 
void  bfs(mat_graph ga,int v)
{
	int j,n;
	sqqueue Q;
	n=ga.n;
	init_sqqueue (Q);
	cout<<v<<" "; 
	int visited[100];
	visited[v]=1;         
	en_sqqueue(Q, v);
	while(!empty_sqqueue (Q))   
	{
		de_sqqueue (Q,v);
		for(j=1;j<=n;j++)
			if(ga.adjmat[v][j]==1&&!visited[j]) 
			{
				cout<<j<<" "; visited[j]=1;
				en_sqqueue(Q,j);
			}
	}
	cout<<"bfs completed"<<endl;
}
void init_sqqueue(sqqueue Q)
{
	Q.front=Q.rear=0;
}
int empty_sqqueue(sqqueue Q)
{
	if(Q.rear==Q.front) return 1;
	else return 0;
}
int en_sqqueue(sqqueue Q,int j)
{
	if((Q.rear+1)%nmax==Q.front)
	{
		cout<<"队满，不能入队"<<endl;return 0;
	}
	else {
		Q.rear=(Q.rear+1)%nmax;
		Q.data[Q.rear]=j;
		return 1;
	}
}
int de_sqqueue(sqqueue Q,int v)
{
	if(Q.rear==Q.front)
	{
		cout<<"队空，不能出队！"<<endl; return 0;
	}
	else {
		Q.front=(Q.front+1)%nmax;
		v=Q.data[Q.front];
		return 1;
	}
}