队列应用——广度优先搜索.doc

《队列应用——广度优先搜索.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、队列应用——广度优先搜索如图：求出从节点1到节点8的最短路径的长度（1到8最少的边数）。使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导找出答案的。就像这一题，需穷举从节点1到节点8的所有路径才能找到答案。穷举是最朴素的搜索。穷举所有路径，面对大规模数据将是很可怕的，采用广度优先搜索法(BFS)，就不必穷举所有路径，大大提高效率。用广度优先搜索法解答此题的过程：1.先搜索所有节点中距节点1最近的点——节点1（距离为0）；2.再搜索与节点1距离为1的节点——2，3，5；3.然后搜索与节点

2、1距离为2的节点——与节点2，3，5中某点距离为1且尚未搜索过的节点——6，7，4，9；4.再搜索距节点1距离为3的节点——与节点6，7，4，9中的某点距离为1且尚未搜索过的节点——8；由以上过程可以确定1到8的最短距离为3（可以用反证法证明此结论的正确性）。整个过程如下图：可以看出搜索的过程是“一层一层”的，从第一层开始，每层的节点都会被“用”来产生下一层的节点，当这一层的节点被“用完”后，才用它们所产生的下一层节点来产生新的节点层，而同一层的节点可以按任意顺序“使用”，一般采用的原则是先生成的结

3、点先“使用”。对“使用”一词，更恰当的说法是“扩展”。广度优先搜索算法中，为了便于进行搜索，要设置一个表存储所有的节点，为了满足先生成的节点层（节点）先扩展的原则，存储节点的表一般设计成队列的数据结构。搜索过程中不断地从队列头取出节点进行扩展。对生成的新节点，要检查它是否已在队列中存在，还要检查它是否目标节点。如果新节点是目标节点，则搜索成功，程序结束；若新节点不是目标节点，并且未曾在队列中出现过，则将它加入到队列尾，否则将它丢弃，再从队列头取出节点进行扩展......。最终可能产生两种结果：找到目

4、标节点，或扩展完所有节点有找到目标节点。题一：求两点间的最短路径长度在一由n（1<=n<=100）个节点，m(1<=m<=n*(n-1)/2)条边构成的图中，求出节点s到t的最短路径长度。输入（input.txt）：第一行n,m,s,t;接下来m行，每行两个整数i，j（1<=i,j<=n)，表示i，j间有一条边。输出(output.txt)：S到t的最短路径的长度（从s到t经过的最少边数），若从s无法到达t，输出-1.分析：布尔数组bVisited[i]非零表示节点i已在队列中，为零表示尚未入队；布

5、尔数组bAdj[i][j]非零表示节点i与节点j之间有一条边，否则无边；队列q[],队首iH,队尾iT;step[i]表示起点到节点i的最短距离。（数据见习题）源代码：#includeusingnamespacestd;ifstreamfin("input.txt");ofstreamfout("output.txt");constintLQ=110,N=110;intbNoAns,bVisited[N]={0},bAdj[N][N]={0};intn,m,s,t,iH,iT,q[

6、LQ],step[N]={0};intInputDataAndInitialize(void);intBFS(void);intOutputAnswer(void);intmain(intargc,char*argv[]){InputDataAndInitialize();BFS();OutputAnswer();return0;}intInputDataAndInitialize(void){fin>>n>>m>>s>>t;inti,j;for(;m--;){fin>>i>>j;bAdj[i][j

7、]=bAdj[j][i]=1;}for(i=1;i<=n;++i)bAdj[i][i]=0;iH=0;iT=1;q[0]=s;bVisited[s]=1;bNoAns=1;return1;}intBFS(void){if(q[0]==t){bNoAns=0;return1;}inti,j;while(iH

8、ted[j]=1;if(j==t){bNoAns=0;return1;}}}}return1;}intOutputAnswer(void){if(bNoAns){fout<<"-1";return1;}fout<