引例

周日广志,美伢带着小新和小葵去游乐园游玩。
我们都知道游乐园里面有很多景点,景点和景点与景点之间的道路就构成了一个“图”。我们去游玩的时候,希望所有的景点都逛一遍,那么游乐园里面的路错综复杂,我们如何制定一个计划使得我们能够将游乐园里的所有景点都游玩一遍呢?
小新提出了一个“广度优先搜索”的办法,小葵提出了一个“深度优先搜索”的办法,那么这一篇我们一起来看看小新的方法吧!

思想

小新提出,先让妈妈拿着游乐园发的游玩手册中的景点目录,刚上来所有的景点都没有游玩过,所以都用铅笔写上×号,然后每游玩过一个景点,就把×号变更为✔️号。然后爸爸拿出手机打开备忘录新建一个待玩清单,从上往下依次记下来接下来该要游览的景点,然后从爸爸的备忘录里面从上往下依次去游玩并且在每次游玩过后删除本次游玩的景点(队列,先进先出)。剩下的事情例如游玩过一个景点之后该如何挑选接下来该去的景点等全听小新的指挥,这个策略就是BFS算法!(剧透一下:小新的景点挑选策略就是刚玩过的景点中临近的还没有游玩过的景点。)

代码实现

bool visited[MAX_VERTEX_NUM];
//你让我游玩所有景点,你游乐场得给我吧
void BFSTraverse(Graph G){  
	//到达一个还未游玩过的景点时都实行小新的策略(BFS)!
	for(i=0;i<G.vexnum;++i){
		if(!visited[i])
			BFS(G,i);
	}
}

void BFS(Graph G, int v){
	visited(v);	//到达一个新景点,先玩再说
	visited[v] = TRUE;	//玩完了,先让妈妈更改×号为✔️号
	Enqueue(Q,v)	//再让爸爸把这个景点记录到队列中
	//只要爸爸的待玩清单里有景点,就去玩
	while(!isEmpty(Q)){
		DeQueue(Q,v);	//把队列中的第一个景点去除
		//小新检查地图上该景点的所有邻接着的景点
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		//所有邻接着的景点,若没有玩过,就去玩
			if(!visited[w]){	
				visited(w);
				visited[w]=TRUE;
				EnQueue(Q,w);
			}
		}
	}	
}