《2022年2022年广度优先搜索算法 .pdf》由会员分享,可在线阅读,更多相关《2022年2022年广度优先搜索算法 .pdf(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、/*广度优先搜索算法,从第start 节点开始进行搜索;*算法中利用到队列数据结构。*param G 待搜索的图*param start 搜索的起点*/static void BFS(GraphLnk G,int start)int n=G.get_nv();if(start=n)return;color=new COLORn;/节点的父节点,非负整数parent=new intn;/深度 depth d=new intn;/初始化for(int i=0;i n;i+)/将所有顶点的颜色着色为白色colori=COLOR.WHITE;/所有顶点的父母初始化为-1 parenti=-1;/所有顶
2、点的深度初始化为无穷大di=Integer.MAX_VALUE;/起点着色为灰色colorstart=COLOR.GRAY;/起点无父节点,记为-1 parentstart=-1;/起点的深度为0 dstart=0;/创建队列LinkQueue Q=new LinkQueue();/将起点添加到队列中Q.enqueue(new ElemItem(start);/迭代第对队列首顶点的相邻边重新着色while(Q.currSize()0)/队列首顶点u int u=(Integer)(Q.dequeue().elem).intValue();for(Edge w=G.firstEdge(u);G.
3、isEdge(w);w=G.nextEdge(w)/*如果 u 的相邻顶点第一次被发现了,则将其颜色改变为灰色,*其深度增加1,其父顶点为u,并将该顶点添加到队列*/if(colorw.get_v2()=COLOR.WHITE)colorw.get_v2()=COLOR.GRAY;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页,共 6 页 -dw.get_v2()=du+1;parentw.get_v2()=u;Q.enqueue(new ElemItem(w.get_v2();/搜索了顶点u 的所有相邻顶点后,将其颜色改变为黑色coloru=COLOR.BLACK;/打印此时各个顶
4、点的颜色for(int i=0;i n;i+)System.out.print(i+)+colori+t);System.out.println();/打印所有顶点的搜索深度System.out.println(各顶点的深度为:);for(int i=0;i n;i+)System.out.print(di+t);/打印所有顶点的父顶点System.out.println(n 各顶点的父母为:);for(int i=0;i n;i+)System.out.print(parenti+t);System.out.println();/广度优先搜索算法_基于邻接表/procedure BFS(G:
5、带顶点v1,.vn 的连通图)/T:=只包含顶点v1 的树/L:=空表/把 v1 放入尚未处理顶点的表L 中/-/while L 非空/begin/删除 L 中第一个顶点v/for v 的每个邻居w/if w 既不在 L 中也不在T 中 then/begin/加入 w 到表 L 的末尾/加入 w 和边 v,w到 T/end/end 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页,共 6 页 -#include /012345 分别表示v0 v1.int v;/点数目int edge;/边数目int j=0;int Lleft=0,Lright=0;/队列头和尾typedef clas
6、s ING*pING;class ING private:int var;pING link;ING()public:ING(int a)var=a;link=NULL;pING backlink()return link;int backvar()return var;friend void add(pING,pING);friend void show(pING);void add(pING head,pING temp)while(head-link)head=head-link;head-link=temp;void show(pING out)while(out)coutvarlin
7、k;pING*draw();/绘图void BFS(pING*a,int head,int*T,int*L);/深度优先搜索int no_T(int num,int*T);/判断是否访问过了int no_L(int num,int*L);/判断是否在队列中名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 6 页 -int main(int argc,char const*argv)pING*a=draw();/指针变量的引用int*T=new intv;/访问 ok int*L=new intv;/队列/-/for(int i=0;i v;+i)/v个访问始点 j=0;Lleft=
8、0;/记得重新设置Lright=0;/队列头和尾BFS(a,i,T,L);coutvedge;/输入点数目和边数目pING*a=new pINGv;for(i=0;i v;+i)ai=NULL;int spot1,spot2;for(i=0;i spot1spot2;pING temp=new ING(spot2);if(aspot1=NULL)aspot1=temp;else add(aspot1,temp);pING temp2=new ING(spot1);if(aspot2=NULL)aspot2=temp2;else add(aspot2,temp2);名师资料总结-精品资料欢迎下载
9、-名师精心整理-第 4 页,共 6 页 -/-/for(i=0;i v;+i)show(ai);coutn;return a;void BFS(pING*a,int head,int*T,int*L)coutheadbackvar();if(no_T(i,T)&no_L(i,L)/w既不在 L 中也不在 T 中 coutibacklink();int no_T(int num,int*T)for(int i=0;i j;+i)if(num=Ti)return 0;return 1;int no_L(int num,int*L)for(int i=Lleft;i Lright;+i)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页,共 6 页 -if(num=Li)return 0;return 1;/*5 7 0 1 0 2 0 3 1 4 1 3 2 3 3 4 图1 2 3 0 4 3 0 3 0 1 2 4 1 3 路线0 1 2 3 4 1 0 3 4 2 2 0 3 1 4 3 0 1 2 4 4 1 3 0 2 Press any key to continue*/名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页,共 6 页 -
限制150内