张金磊的个人必威体育手机版本

当前位置:首页 > 必威体育手机版本优化
服务热线
18695836489
联系邮箱
1020280500@qq.com

SEO技术关于广度优先搜索和深度优先搜索

时间:2016-03-05 00:00:00 浏览:

 广度优先搜索(BFS),可以被形象的描述为“浅尝辄止”,具体一点就是每个顶点只访问它的邻接节点(如果它的邻接节点没有被访问)并且记录这个邻接节点,当访问完它的邻接节点之后就结束这个顶点的访问。周口必威体育手机版本建设

广度优先用到了“先进先出”队列,通过这个队列来存储第一次发现的节点,以便下一次的处理;而对于再次发现的节点,我们不予理会——不放入队列,因为再次发现的节点:周口必威体育手机版本建设

无非是已经处理完的了;周口必威体育手机版本建设

或者是存储在队列中尚未处理的。周口必威体育手机版本建设

周口必威体育手机版本建设

《算法导轮》对两种搜索都采用了很聪明的做法,用白色WHITE来标志未发现的节点,用灰色GRAY来标志第一次被发现的节点,用黑色BLACK来标志第二次被发现的节点。周口必威体育手机版本建设

于是有了:周口必威体育手机版本建设

seo.com/static/image/common/codebg.gif); background-color: rgb(247, 247, 247); font-family: 'Microsoft YaHei', ΢���ź�, 'Microsoft JhengHei', Verdana, Helvetica, sans-serif, ����; line-height: 25px; word-wrap: break-word; overflow: hidden; color: rgb(102, 102, 102); zoom: 1; background-position: 0px 0px; background-repeat: no-repeat repeat;">
word-wrap: break-word;">
    word-wrap: break-word; margin: 0px 0px 0px 10px !important; padding: 0px !important;">
  1. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">BFS(G,s)
  2. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    for each vertex v in V[G]
  3. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        status[v] = WHITE
  4. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        /******其他初始化******/
  5. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    status[s] = GRAY    //s是原点
  6. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    queue q
  7. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    入队(q,s);
  8. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    while q非空
  9. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        t = 出队(q);
  10. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        for each vertex v in Adj[t] //与t邻接的点
  11. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">            if status[v] = WHITE    //只对未访问的操作
  12. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">                status[v] = GRAY    //标记为第一次访问
  13. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">                /******其他操作******/
  14. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">                入队(q,v)
  15. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        status[t] = BLACK   //此点已经处理完了
word-wrap: break-word; cursor: pointer; color: rgb(51, 102, 153) !important; background-position: initial initial; background-repeat: initial initial;">复制代码

word-wrap: break-word;">word-wrap: break-word;">周口必威体育手机版本建设

word-wrap: break-word; margin-bottom: 5px !important;">

导论还在上面伪代码的“其他”中加入了访问长度和父节点的操作。此举可以算出,从源点到其他顶点路径的最少步数和它的具体路径。周口必威体育手机版本建设

关于广度优先搜索的一个简单应用:周口必威体育手机版本建设

假如有问题,每个村庄之间都通过桥来联通,先给出村庄的图,问村庄A到村庄B最少要通过多少座桥?这个问题可以很容易的转化为上面的BFS问题。周口必威体育手机版本建设

深度优先搜索深度优先搜索(DFS),可以被形象的描述为“打破沙锅问到底”,具体一点就是访问一个顶点之后,我继而访问它的下一个邻接的顶点,如此往复,直到当前顶点一被访问或者它不存在邻接的顶点。周口必威体育手机版本建设

同样,算法导论采用了“聪明的做法”,用三种颜色来标记三种状态。但这三种状态不同于广度优先搜索:周口必威体育手机版本建设

WHITE 未访问顶点周口必威体育手机版本建设

GRAY 一条深度搜索路径上的顶点,即被发现时周口必威体育手机版本建设

BLACK 此顶点的邻接顶点被全部访问完之后——结束访问次顶点周口必威体育手机版本建设

seo.com/static/image/common/codebg.gif); background-color: rgb(247, 247, 247); word-wrap: break-word; overflow: hidden; color: rgb(102, 102, 102); zoom: 1; background-position: 0px 0px; background-repeat: no-repeat repeat;">
word-wrap: break-word;">
    word-wrap: break-word; margin: 0px 0px 0px 10px !important; padding: 0px !important;">
  1. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">DFS(G,s)
  2. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    for each vertex v in V(G)
  3. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        status[v] = WHITE
  4. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        /******其他初始化******/
  5. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    for each vertex v in V(G)
  6. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        if(status[v]==WHITE)
  7. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">            DFS-VISIT(v)
  8. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;"> 
  9. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">DFS-VISIT(v)
  10. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    status[v] = GRAY
  11. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    for each vertex t in Adj(v)
  12. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">        if status[t] = WHITE
  13. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">            DFS-VISIT(t)
  14. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">            /******其他操作******/
  15. word-wrap: break-word; list-style-type: decimal-leading-zero; font-family: Monaco, Consolas, 'Lucida Console', 'Courier New', serif; line-height: 1.8em; background-position: initial initial; background-repeat: initial initial;">    status[v] = BLACK
word-wrap: break-word; cursor: pointer; color: rgb(51, 102, 153) !important; background-position: initial initial; background-repeat: initial initial;">复制代码

通过给DFS搜索过程中给每一个顶点加时间戳,就可以实现拓扑排序了。实现拓扑排序需要:周口必威体育手机版本建设

对于每一个顶点,都有两个时间戳,分别这样来定义:周口必威体育手机版本建设

在一顶点刚被发现的时候,标记此顶点的第一个时间戳;周口必威体育手机版本建设

在结束此顶点的访问的时候,标记此顶点的第二个时间戳。时间戳可以用简单的123456来标记,只要能区分大小就行。周口必威体育手机版本建设

因此,你会发现,越早发现的点,他的第一个时间戳会越小,但是他的第二个时间戳会越大。周口必威体育手机版本建设

总结两个算法都是O(V+E),在用到的时候适当选取。在使用白灰黑标志的时候,突然明白了如何用深度优先搜索来判断有向图中是否存在环。周口必威体育手机版本建设

深度优先和广度优先各有各的优缺点:周口必威体育手机版本建设

广优的话,占内存多,能找到最优解,必须遍历所有分枝. 广优的一个应用就是迪科斯彻单元最短路径算法。周口必威体育手机版本建设

深优的话,占内存少,能找到最优解(一定条件下),但能很快找到接近解(优点),可能不必遍历所有分枝(也就是速度快), 深优的一个应用就是连连看游戏。周口必威体育手机版本建设

在更多的情况下,深优是比较好的方案。周口必威体育手机版本建设

上一篇:SEO技术避免必威体育手机版本流量大损失的seo策略
下一篇:seo技术关于鼠标键盘模拟与数据提交
分享到:

联系我们

三石必威体育手机版本,设计开发安全无漏洞必威体育手机版本。

  • 全国统一服务热线

    18695836489

  • 咨询QQ

    1020280500

  • 扫描微信二维码

    微信联系更方便

  • 办公邮箱:1020280500@qq.com公司地址:河南省周口市太康县

    选择三石,选择快捷!三石网络,让您不同!