综合技术

广度优先搜索算法(Breath-first Search)是如何搜索一张图的?

微信扫一扫,分享到朋友圈

广度优先搜索算法(Breath-first Search)是如何搜索一张图的?
0

搜索可以理解为探索,给定一个图上的点S和A,需要找到从S到A的一个路径

图的基础概念

一个图用 G=(V,E) 表示,V是顶点的集合,E是边的集合。如下所示有两种图

  1. 无向图,V={a,b,c},E={{a,b},{b,c},{a,c}}

2. 有向图,V={a,b,c},E={(a,b),(b,a),(c,a),(b,c)}


实际应用有哪些?

网络爬虫、社交网络、网络包传播、垃圾回收算法等

如何用算法表示图?

使用邻接表。它是一个数组(Adj表示)大小是 |V|,每个元素是指向一个链表的指针,遍历的方法如下

for each vertex u in V
    Adj[u] stores u's neighbors 

比如,上所述的有向图来说 Adj[a]={b},Adj[b]={a,c} ,对无向图来讲 Adj[a]={(a,c),(a,b)}

这种表现形式所需要的空间大小为 (V+E),|V|个顶点和|E|条边

广度优先算法是如何搜索一张图的?

目标:对于一个给定的节点S

V,通过它来遍历它所能到达的所有节点

时间要求:O(V+E)

思路:查看给定节点,通过0步移动,能够到达的节点,这个节点就是s本身,然后从s移动一步,也就是s的邻接表,找到他能到达的节点,依次类推,需要避免重复

BFS(s,Adj):
    level={s:0} //第0步能到达的节点
    parent={s:None}
    i=1 //第0步就是s,已经到达,从第一步开始
    frontier=[s] //前一层已经经过的节点 level=i-1
    while frontier: //在已经经过的节点找它的相邻节点
        next=[] //当前层找到的节点
        for u in frontier:
            for v in Adj[u]:
                if  v not in level: //当前节点没有在其它层出现过,从而避免重复
                    level[v]=i 
                    parent[v]=u
                    next.append(v)
        frontier=next 
        i+=1 //走下一层

以无向图为例

  1. 初始状态,处于第0层,i=0,s没有父节点,已经经过的节点只有s

2. 从s移动0步,s的相邻节点是a和x,他们没有在之前的level存在,所以需要添加到level中。执行完后

level={s:0,a:1,x:1}  
parent={s:None,a:s,x:s}  
frontier={a,s}  
i=2

3. 以新的frontier为基础,再往前一步,发现a有z和s,但是s已经经历过了,不再添加,依次类推x。执行完之后

level={s:0,a:1,x:1,z:2,x:2}  
parent={s:None,a:s,x:s,z:a,d:x,c:x}  
frontier={z,d,c}  
i=3

  1. 以新的frontier为基础,再往前一步,发现z的唯一邻接节点只有a,但是a已经在level 1中,不再添加。执行完之后
level={s:0,a:1,x:1,z:2,x:2,f:3,v:3}  
parent={s:None,a:s,x:s,z:a,d:x,c:x,f:d,v:c} frontier优先存的是d  
frontier={f,v}  
i=4

5. 以新的frontier为基础,再往前一步,发现f,v的邻接节点都已经计算过,不再计入,因此最后

frointer={}  
i=5

至此结束

阅读原文...


稀土掘金

如何用蓝湖做自动标注 ?

上一篇

要问火山口中强旗舰 坚果R1才是真蓝火

下一篇

您也可能喜欢

评论已经被关闭。

插入图片
广度优先搜索算法(Breath-first Search)是如何搜索一张图的?

长按储存图像,分享给朋友