bfsearch.cpp

实现图的广度优先遍历:数据结构课程设计

#include"ALGraph.h"
#include"LinkQueue.h"
using namespace std;
void BFSTraverse(ALGraph G,int v)
{
	bool visited[MAX_VERTEX_NUM ];	//标志数组，若第i个顶点被访问了，则visited[i-1]==true;否则visited[i-1]==false
	for(int i=0;i<G.vexnum;i++) visited[i]=false;
	LinkQueue Q;
	initQueue(Q);
	//从第v个顶点开始遍历
	cout<<"开始遍历该图。从第"<<v<<"个顶点开始!"<<endl;
	cout<<endl<<"遍历的顶点顺序为: "<<endl;
	int time=0;		// while 循环的次数
	int fenZhi=0;	//判断无向图中的连通分支数
	while(time<=MAX_VERTEX_NUM)
	{
		time++;
		if(!visited[v-1])
		{
			fenZhi++;
			visited[v-1]=true;
			Visit(v);
			EnQueue(Q,v);
			int u;
			while(!queueEmpty(Q))
			{
				DeQueue(Q,u);		//取对头元素，并置为u
				for(int w=firstAdjVex(G,u)	; w	;	w=nextAdjVex(G,u,w)	) //遍历第u个顶点的所有邻接顶点
				{
					if(!visited[w-1])	//第w个顶点没被访问过
					{
						visited[w-1]=true;
						Visit(w);
						EnQueue(Q,w);
					}
				}
			}
			cout<<endl;
		}
		if(time==1)		//从第v个顶点遍历完毕后，遍历其他没被遍历的顶点，这个是针对无向非连通图和有向图的
			v=1;
		else
			v++;
	}
	cout<<endl<<"遍历结束！  ";
	if(G.kind ==0&&fenZhi==1)
		cout<<"该图为连通图!"<<endl;
	else if(G.kind ==0&&fenZhi!=1)
		cout<<"该无向图的连通分量为： "<<fenZhi<<endl;
	else if(G.kind ==1&&fenZhi!=1)
		cout<<"并不能从指定的顶点开始依次遍历其它顶点!\n分"<<fenZhi<<"次才遍历完该图!"<<endl;	
	system("pause");
}