数据结构13--BFS

广度优先搜索BFS广度优先搜索类似于树的按层次遍历的过程，其搜索过程如下：假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。若此时图中尚有结点未被访问，则任选其中的一个作起始点，重复上述过程，直至图中所有结点都被访问到为止。换句话说，按广度优先顺序搜索遍历图的过程是以v0为起始点，由近及远，依次访问和v0有路径相连且路径长度为1，2，3……的结点。从v3出发按广度优先搜索的顺序遍历，得到的结点序列是v3→v2→v4→v1→v5由于队列“先进先出”的存取规则与广度优先搜索的遍历顺序相吻合，因此使用了一个工作队列q，按访问的先后顺序存储被访问过的结点序号。fillchar(f,sizeof(f),0);/*访问标志初始化*/f[S]←true;q[1]←S;/*访问源点，源点入队*/open←1;closed←1;/*队列的首尾指针初始化*/whileopen=closeddo/*若队列非空，则访问与队首元素相连的未访问点，计算其路径长度，并将它们送入队列*/{fori←1toNdoif(f[i]=false)and(a[q[open],i]0)or(q[open]i)then{访问顶点I;f[i]←true;inc(closed);q[closed]←i};/*then*/inc(open);/*出队*/};/*while*/调用一次bfs(i)可按广度优先搜索的顺序访问处理结点i所在的连通分支。整个图按广度优先搜索顺序遍历的过程如下：proctraver;/*对每个连通块进行BFS*/{fillchar(f,sizeof(f),false);foreachi∈G(V)doiff[i]=falsethenbfs(i);};/*traver*/宽度优先搜索的应用•1、计算连通子图•2、计算无权图的单源最短路•3、计算无权图的多源最短路•4、计算有权图的单源最短路1、计算连通子图从源点v0出发进行宽度优先搜索访问到的顶点：v0所在连通分支的顶点；未访问顶点：v0所在连通分支外的顶点；用于计算顶点对之间路径的必经顶点和连通子图间的连通关系街道赛跑下图给出了一个沿街道赛跑的路线。图中有许多点，给以标号0，1，．．．N(此图中N=9)，点之间可以用含箭头的线相连。标号为0的点是起点；标号为N的点为终点。含箭头的线表示单向通行的街道。运动员沿箭头所指方向从一个点跑向另一个点；在每一个点上，运动员可以选择任何一个箭头(向外的)继续向前跑。一个完整路线具有如下特点：1．路线中每一点都可从出发点到达；2．路线中每一点都可到达终点；3．终点处没有向外的箭头。运动员要到达终点，但不要求路线(图)中的每一点都经过。但是路线(图)中的某些点是必经之点。上图的例子中，必经之点是：0，3，6，9。②采用广度优先搜索的方法从点0开始，按逐层搜索的方法对删除当前判别点后的路线重复进行访问，直至找不到可访问的点为止。广度搜索的结果，将路线上的所有点(除当前判别点外)分为两个集合：⑴广度优先搜索中访问到的点，即从出发点0可达的点集合，设这些点到达标志；⑵广度优先搜索中未访问过的点，即不可从出发点0到达的点集合。这些点设未到达标志；若终点N在第二个集合中，则当前判别点是必经点，然后再判别两个集合是否互为独立。若与必经点相连的所有点都在第二个集合中，且两个集合中的点之间无任何箭头相连，则这个必经点亦是分裂点。Fori←1ton-1do/*顺序设点1、点2，．．．点N－1为当前判别点*/{删除顶点i，构建新图的相邻矩阵a；BFS(0)；/*宽度优先搜索出发点0可达的点集*/iff[n]=false/*若出发点0不可达终点n，则顶点i为必经点*/Then{输出顶点i为必经点；Fund←true；/*初始时假设顶点i为分裂点*/Fork←0ton-1do/*搜索出发点0可达的点集合*/Forp←0tondo/*搜索出发点0不可达的点集合*/if(f[k]=true)and(f[p]=false)and((a[k,p]0)or(a[p,k]0))/*若两个点集间有边相连，则退出for循环*/Then{Fund←false;break};/*then*/ifFundthen输出顶点i为分裂点；}；/*then*/}；/*for*/2、计算无权图的单源最短路无权图可以看作是边长为1的有权图；由于宽度优先搜索是按层次递增的顺序搜索，即第i层顶点为v0出发的所有长度为i-1的路径的尾顶点，因此第1次搜索到顶点v，即可确定v0至v的最短路。子图划分给定一个无向图，图中有一个起点S和一个终点T。要求选K个集合S1，S2，…，SK，每个集合都含有图中的一些边，任意两个不同的集合的交集为空。并且从图中任意去掉一个集合，S到T都没有通路。要求K尽量大。无解条件如果S到T在图中有一条长为L的最短路，那么显然答案不会超过L：如果答案大于L，那么根据抽屉原理，必定至少有一个集合中没有这条路上的任意一条边。那么显然删去这个集合，S到T仍然连通：至少这条最短路没有被破坏。所以与题目要求不符，导致矛盾。构造K=L的方案如果S到T的最短路是L，则构造方法如下：首先求出S到任意一点u的最短路D(u)。这样对图上的任意一条边e=uv，如果D(v)-D(u)=1，且D(v)≤L，就将这条边加入集合SD(v)中。这样就构造出来一种分组方案。为什么？证明[引理]如果图上的任意一条边e=uv，D(v)–D(u)=1且D(v)=ie∈Si。那么从图上将Si中的所有边删去，对原图上任意D(p)≥i的点p，在新图上S到p均无通路。[证明]如果D(p)≥i，就说明任意一条从S到p的路径中至少包括[D(p)+1]个点：S,p1,p2,…,p，顺序写出S到每一个点最短路的长度：D(S),D(p1),D(p2),…,D(p)(1)这个数列(1)一定以0开头，最后结尾是D(p)≥i，而根据最短路的性质，数列(1)中相邻两项差的绝对值一定不超过1，所以在这个数列中一定会出现相邻的两个数i-1，i。而显然对应的边在新图中被删去了，因此在新图中无法找到这条路径。于是，从图中删去Si的所有边，就可以保证S到p没有路径。因此，引理成立。[定理]上文描述的构造集合的方案是正确的[证明]上文所说的任意Si（i≤L）满足引理中的条件，因此删去任意Si（i≤L）后S到T：D(T)=L≥i，一定没有通路。所以这个构造集合的方案符合题意，是正确的。这样，编程实现就很简单了：图中每条边的长度都为1，求最短路数组的功能可以有宽度优先搜索实现。所以算法的时间、空间复杂度都是O(E)。数据结构ConstLimit=400;/*顶点数的上限*/Maximum=10000;TypeTdata=array[1..Limit,1..Limit]oflongint;Tvisited=array[1..Limit]oflongint;Tqueue=array[1..Limit]oflongint;Vardata:Tdata;/*data[i，j]为边(I,j)的边序号*/visited:Tvisited;/*visited[i]为顶点i与s的最短路径长度，-1表示未访问*/queue:Tqueue;/*队列*/N,S,T:longint;/*顶点数、源点、终点*/通过宽度优先搜索计算边集fillchar(visited,sizeof(visited),$FF);/*访问标志初始化*/visited[S]←0;queue[1]←S;/*访问源点，源点入队*/open←1;closed←1;/*队列的首尾指针初始化*/whileopen=closeddo/*若队列非空，则访问与队首元素相连的未访问点，计算其路径长度，并将它们送入队列*/{fori←1toNdoif(visited[i]=-1)and(data[queue[open],i]0)then{visited[i]←visited[queue[open]]+1;inc(closed);queue[closed]←i};/*then*/inc(open);/*出队*/};/*while*/输出集合个数和每个集合中的边信息writeln(visited[T]);/*输出集合个数，即s到t的最短路径长度*/fori←0tovisited[T]-1do/*依次输出边集*/{tot←0;/*计算由S出发的所有最短路径上的第i条边的条数tot，这些边组成了集合si*/forj←1toNdoifvisited[j]=ithenfork←1toNdoif(visited[k]=i+1)and(data[j,k]0)theninc(tot);write(tot);/*输出si集合中的边数*/forj←1toNdo/*输出si集合中的所有边*/ifvisited[j]=ithenfork←1toNdoif(visited[k]=i+1)and(data[j,k]0)thenwrite('',data[j,k]);writeln;};/*for*/k源最短路问题如果是k源无权图1、使用k次单源最短路算法（Dijkstra），时间复杂度为O(k*n2)；2、初始时所有源点入队列。然后进行宽度优先搜索。时间复杂度为O(n2)；如果是k源有权图：将所有源点压缩成一个源点，保持源点与非源点之间的连接关系，采用Dijkstra算法计算时间复杂度为O(k*n2)。位图给定一个n*m的矩形位图，位图中的每个像素不是白色就是黑色，但至少有一个是白色的。第i行、第j列的像素被称作像素(i，j)。两个像素p1=(i1，j1)，p2=(i2，j2)之间的距离定义为：d(p1，p2)=|i1-i2|+|j1-j2|。现在请你计算图中每个像素与离其最近的“白像素”的距离。【输入】输入文件BIT.IN的第一行包含两个整数n，m（1≤n≤150，1≤m≤150），用一个空格隔开。接下来n行，每一行都包含一个长度为m的01串；第i+1行，第j列的字符若为1，则像素(i，j)是白色的；否则是黑色的。【输出】文件BIT.OUT包含n行，每行有m个用空格隔开的整数。第i行、第j列的整数表示(i，j)与离它最近的白像素之间的距离。算法分析1、由于是求所有黑像素的点到白像素的最短距离，所以采用适合于整体计算floyd算法比较好，但floyd算法的时间复杂度为O（n3m3），不能满足时间要求。2、考虑用求单源最短路径的算法：对于每一点进行一次宽度优先搜索，求该点到其他各点的最短距离。但这一算法的时间复杂度也达到了O（n2m2），3、在前面的方法里，我们是将每个黑像素到白像素的距离作为单独的问题来考虑的。这里忽略了一个重要的信息：相邻的黑像素之间有着很强的联系。定义：f（x，y）表示像素（x，y）到最近的白像素的距离。f(x,y)=min{f(x-1,y),f(x+1,y),f(x,y-1),f(x,y+1)}+1看到了这个式子，眼前顿时豁然开朗：前面所用的宽度优先搜索是以黑像素作为源点，得到的是单源最短路；而现在以白像素作为源点，求的是多源最短路。采用多源最短路径的算法求解本题，时间复杂度仅为O（n*m），时效大为改善。设constmaxn=150；/*位图的规模*/move：array[1..4，1..2]ofinteger=((1，0)，(0，1)，(-1，0)，(0，-1))；/*四个方向所对应的水平竖直增量*/varused:array[1..maxn,1..maxn]ofboolean；/*像素已访问标志*/list:array[1..maxn*maxn,1..2]ofinteger；/*list[i]为第i个源点(白像素)的坐标*/map：array[1..maxn，1..maxn]ofinteger；/*map[i，j]为（i，j）的像素离最近白像素的距离*/i，j，n，p，q，x，y，t1，t2，m：int