基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)
本文最后更新于1889天前,其中的信息可能已经有所发展或是发生改变。

        深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种,是一个针对图和树的遍历算法,英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。

基本步奏

(1)对于下面的树而言,DFS方法首先从根节点1开始,其搜索节点顺序是1,2,3,4,5,6,7,8(假定左分枝和右分枝中优先选择左分枝)。

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(2)从stack中访问栈顶的点;

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(3)找出与此点邻接的且尚未遍历的点,进行标记,然后放入stack中,依次进行;

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(4)如果此点没有尚未遍历的邻接点,则将此点从stack中弹出,再按照(3)依次进行;

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(5)直到遍历完整个树,stack里的元素都将弹出,最后栈为空,DFS遍历完成。

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

二、广度优先搜索

        广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。基本过程,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。一般用队列数据结构来辅助实现BFS算法。

基本步奏

(1)给出一连通图,如图,初始化全是白色(未访问);

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(2)搜索起点V1(灰色);

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(3)已搜索V1(黑色),即将搜索V2,V3,V4(标灰);

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(4)对V2,V3,V4重复以上操作;

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(5)直到终点V7被染灰,终止;

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

(6)最短路径为V1,V4,V7.

点击数:127

    暂无评论

    发送评论 编辑评论

    
    				
    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇