TopSort(拓扑排序)中DFS和BFS的应用

图的搜索：

深度优先搜索：
下面图中的数字显示了深度优先搜索顶点被访问的顺序。

为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则：
(1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。
(2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。
(3) 如果不能执行规则1和规则2，就完成了整个搜索过程。

广度优先搜索：
在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中，算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。

实现广度优先搜索，也要遵守三个规则：
(1) 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。
(2) 如果因为已经没有未访问顶点而不能执行规则1时，那么从队列头取一个顶点，并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2，则搜索结束。

1.深度优先搜索DFS（递归调用栈实现）

void DFS(graph *G, int v){
	G->setMark(v,VISITED);
	for(int w=G->first(v);w<G->n();w=G->next(v,w))
		if(G->getMark(w)==UNVISITED)
			DFS(G,w);
}

2.广度优先搜索BFS（优先队列实现）

void BFS(graph *G, int  start, Queue<int> *Q)
{
	int v,w;
	Q->enqueue(start);
	G->setMark(start,VISITED);
	while(Q->lenght!=0)
	{
		Q->dequeue(v);
		for(w->G->first(v);w<G->n();w=G->next(v,w))
			if(G->getMark(w)==UNVISITED){
				G->setMark(w)= VISITED;
				Q->enqueue(w);
			}
	}
}

3.拓扑排序

假如我们需要为一组任务安排执行顺序，但是这些任务存在先决条件，只有一项或几项任务完成后才能进行另一项任务。

拓扑排序是对有向无环图的一种排序。表示了顶点按边的方向出现的先后顺序。如果有环，则无法表示两个顶点的先后顺序。在现实生活中，也会有不少应用例子，比如学校课程布置图，要先修完一些基础课，才可以继续修专业课。

　对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。

   　通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。
注意：
   　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
   　②若图中存在有向环，则不可能使顶点满足拓扑次序。
   　③一个DAG的拓扑序列通常表示某种方案切实可行。
   　【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。
   　④一个DAG可能有多个拓扑序列。
   　【例】对图G₉进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C₀，C₁，C₂，C₄，C₃，C₅，C₇，C₈，C₆和C₀，C₇，C₉，C₁，C₄，C₂，C₃，C₆，C₅。
　　　　　　 TopSort(拓扑排序)中DFS和BFS的应用　　
　　⑤当有向图中存在有向环时，拓扑序列不存在
【例】下面(a)图中的有向环重排后如(b)所示，有向边<v₃，v_l>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。
　　　　　　 TopSort(拓扑排序)中DFS和BFS的应用　

3.1利用DFS实现拓扑排序

void topSort(Graph *G){
	int i;
	for(i=0;i<G->n();i++)
		G->setMark(i,UNVISTED);
	for(i=0;i<G->n();i++)
		if(G->getmMark(i)==UNVISITED)
			tophelp(G,i);
}

void tophelp(Graph *G, int v)
{
	G->setMark(v,VISITED);
	for(int w=G->first(v);w<G->n();w=G->next(v,w)
	{
		if(G->getMark(w)==UNVISTED)
			tophelp(G,w);
	}
	printout(v);
}

3.2利用BFS实现拓扑排序

void topSort(Graph *G,Queue<int> *Q)
{
	int count[G->n()];
	int v,w;
	for(v=0;v<G->n();v++)
		count[v]=0;
	for(v=0;v<G->n();v++)
		for(w=G->fisrt(v);w<G->n();w=G->next(v,w))
			count[w]++;
	for(v=0;v<G->n();v++)
		if(count[v]==0)
			Q->enqueue(v);
	while(Q->length()!=0)
	{
		Q->dequeue(v);
		for(w=G->first(v);w<G->n();w=G->next(v,w))
		{
			count[w]--;
			if(count[w]==0)
				Q->enqueue(w);
		}
	}
}

秒客网

TopSort(拓扑排序)中DFS和BFS的应用

相关文章