首页 > 代码库 > 如何实现广度优先遍历(BFS)

如何实现广度优先遍历(BFS)

BFS过程:

一:访问顶点V,并标记V为已经访问

二:顶点V入队列

三:如果队列非空,进行执行,否则算法结束

四:出队列取得对头顶点u,如果顶点未被访问,就访问该顶点,并标记该顶点为已经访问

五:查找u的第一个邻接节点w

六:如果w不存在,则转到步骤三,否则循环执行

a. 如果w没有被访问过,则先把w入队列

b.查找顶点u的下一个邻接节点,记为w,并转到步骤六


上图使用BFS访问顺序为:

A BEDC


队列的变化过程如下:

A

B

BE

ED

D

C

代码如下:

#include<iostream>
using namespace std;
#define VertexSize 10
int visit[VertexSize];

//===================================
#define QueueSize 30
typedef struct 
{
	int Seq[QueueSize];
	int front;
	int rear;
	int count;
}RQueue;

RQueue Q;

void Initiate_Queue(RQueue *Q)
{
	Q->front=0;
	Q->rear=0;
	Q->count=0;
}

void AppendQueue(RQueue *Q,int data)
{
	if(Q->count>=QueueSize)
	{
		cout<<"overflow"<<endl;
		return ;
	}
	Q->Seq[Q->rear]=data;
	Q->rear=(Q->rear+1)%QueueSize;
	Q->count++;
}

int QueueNotEmpty(RQueue *Q)
{
	if(Q->count!=0)
		return 1;
	else 
		return 0;
}

int DeleteQueue(RQueue *Q)
{
	if(Q->count<=0)
	{
		cout<<"empty"<<endl;
		return NULL;
	}
	int d;
	d=Q->Seq[Q->front];
	Q->front=(Q->front+1)%QueueSize;
	Q->count--;
	return  d;
}



//===================================


typedef struct
{
	int weight[VertexSize][VertexSize];
}Graph;


void Initiate_Graph(Graph *g,int n)
{
	int i,j;
	for(i=0;i<n;i++)
		visit[i]=0;
		for(j=0;j<n;j++)
		{
			if(i==j) g->weight[i][j]=0;
			else g->weight[i][j]=0x7fff;
		}
}

void InsertEdge(Graph *g,int v,int w,int weight,int n)
{
	if(v<0 || v>=n||w<0||w>=n)
	{
		cout<<"overflow!========="<<endl;
	}
	g->weight[v][w]=weight;
}


void dfs(Graph *g,int u,int n)
{
	cout<<u<<" ";
	visit[u]=1;
	int i;
	for(i=0;i<n;i++)
	{
		if(g->weight[u][i]>0 && g->weight[u][i]<0x7fff && !visit[i])
		{
			visit[i]=1;
			dfs(g,i,n);
		}
	}
}

void bfs(Graph *g,int u,int n)
{
	Initiate_Queue(&Q);
	int j;
	cout<<u<<" ";
	visit[u]=1;
	AppendQueue(&Q,u);
	while(QueueNotEmpty(&Q))
	{
		int x=DeleteQueue(&Q);
		for(j=0;j<n;j++)
		{
			if(g->weight[x][j]>0 &&g->weight[x][j]<0x7fff && !visit[j])
			{
				cout<<j<<" ";
				visit[j]=1;
				AppendQueue(&Q,j);
			}
		}
	}
}




void main()
{
	Graph g;
	int n,edge;
	cout<<"请输入图的顶点个数:"<<endl;
	cin>>n;
	cout<<"请输入图的边个数"<<endl;
	cin>>edge;
	Initiate_Graph(&g,n);
	int i,p1,p2,weight;
	cout<<"请输入顶点-顶点-权值:"<<endl;
	for(i=0;i<edge;i++)
	{
		cin>>p1>>p2>>weight;
		InsertEdge(&g,p1,p2,weight,n);
	}
	cout<<"深度优先遍历为:"<<endl;
	dfs(&g,0,n);
	cout<<endl;
	for(i=0;i<n;i++)
		visit[i]=0;
	cout<<"广度优先遍历为:"<<endl;
	bfs(&g,0,n);
	cout<<endl;
	system("pause");
}


如何实现广度优先遍历(BFS)