引例

接上文,小葵提出了一个“深度优先搜索”的办法,那么这一篇我们一起来看看小葵的方法吧!

思想

小葵提出,还是让妈妈拿着游乐园发的游玩手册中的景点目录,刚上来所有的景点都没有游玩过,所以都用铅笔写上×号,然后每游玩过一个景点,就把×号变更为✔️号。爸爸就不用记备忘录了。剩下的事情例如游玩过一个景点之后该如何挑选接下来该去的景点等全听小葵的指挥,这个策略就是DFS算法!(剧透一下:小葵的景点挑选策略就是先玩尽一条道路上的景点,一条路走到黑先!)

代码实现

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
	//老规矩,初始化一下
	for(v=0;v<G.vexnum;++v)
		visited[v]=FALSE;
	//老规矩,到了每一个还未游览的景点时都执行小葵的策略
	for(v=0;v<G.vexnum;++v)
		if(!visited[v])
		DFS(G,v);
}

void DFS(Graph G,int v){
	visit(v);
	visited[v]=TRUE;
	//对于刚刚玩完的这个景点的邻接景点都使用DFS策略,递归!
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		if(!visited[w])
			DFS(G,w)
}