精华内容
下载资源
问答
  • 广度优先搜索算法

    万次阅读 多人点赞 2019-04-25 13:26:58
    广度优先搜索算法(Breadth-First Search,BFS)是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验...

    一、简介

    广度优先搜索算法(Breadth-First Search,BFS)是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。

    广度优先搜索让你能够找出两样东西之间的最短距离,不过最短距离的含义有很多!使用广度优先搜索可以:

    1. 编写国际跳棋AI,计算最少走多少步就可获胜;
    2. 编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方;
    3. 根据你的人际关系网络找到关系最近的医生。

    二、例子

    假设你居住在旧金山,要从双子峰前往金门大桥。你想乘公交车前往,并希望换乘最少。可乘坐的公交车如下。

    为找出换乘最少的乘车路线,你将使用什么样的算法?
    一步就能到达金门大桥吗?下面突出了所有一步就能到达的地方。

    金门大桥未突出,因此一步无法到达那里。两步能吗?

    金门大桥也未突出,因此两步也到不了。三步呢?

    金门大桥突出了!因此从双子峰出发,可沿下面的路线三步到达金门大桥。

     还有其他前往金门大桥的路线,但它们更远(需要四步)。这个算法发现,前往金门大桥的最短路径需要三步。这种问题被称为最短路径问题(shorterst-path problem)。你经常要找出最短路径,这可能是前往朋友家的最短路径,也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索。要确定如何从双子峰前往金门大桥,需要两个步骤。
    (1) 使用图来建立问题模型。
    (2) 使用广度优先搜索解决问题。
    下面介绍什么是图,然后再详细探讨广度优先搜索。

    三、图

    图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图,V是图G中顶点的集合,E是图G中边的集合。

    无边图:若顶点Vi到Vj之间的边没有方向,则称这条边为无项边(Edge),用序偶对(Vi,Vj)标示。

    对于下图无向图G1来说,G1=(V1, {E1}),其中顶点集合V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}:

    有向图:若从顶点Vi到Vj的边是有方向的,则成这条边为有向边,也称为弧(Arc)。用有序对(Vi,Vj)标示,Vi称为弧尾,Vj称为弧头。如果任意两条边之间都是有向的,则称该图为有向图。

    有向图G2中,G2=(V2,{E2}),顶点集合(A,B,C,D),弧集合E2={<A,D>,{B,A},<C,A>,<B,C>}.

    权:有些图的边和弧有相关的数,这个数叫做权。这些带权的图通常称为网。

    四、广度优先搜索算法

    假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。

    这种查找很简单。首先,创建一个朋友名单。

     然后,依次检查名单中的每个人,看看他是否是芒果销售商。

     假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。

     检查名单中的每个人时,你都将其朋友加入名单。

     这样一来,你不仅在朋友中查找,还在朋友的朋友中查找。别忘了,你的目标是在你的人际关系网中找到一位芒果销售商。因此,如果Alice不是芒果销售商,就将其朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网,直到找到芒果销售商。这就是广度优先搜索算法。

    五、查找最短路径

    再说一次,广度优先搜索可回答两类问题。
    第一类问题:从节点A出发,有前往节点B的路径吗?(在你的人际关系网中,有芒果销售商吗?)
    第二类问题:从节点A出发,前往节点B的哪条路径最短?(哪个芒果销售商与你的关系最近?)
    刚才你看到了如何回答第一类问题,下面来尝试回答第二类问题——谁是关系最近的芒果销售商。例如,朋友是一度关系,朋友的朋友是二度关系。

     在你看来,一度关系胜过二度关系,二度关系胜过三度关系,以此类推。因此,你应先在一度关系中搜索,确定其中没有芒果销售商后,才在二度关系中搜索。广度优先搜索就是这样做的!在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系。顺便问一句:将先检查Claire还是Anuj呢?Claire是一度关系,而Anuj是二度关系,因
    此将先检查Claire,后检查Anuj。

    你也可以这样看,一度关系在二度关系之前加入查找名单。

    你按顺序依次检查名单中的每个人,看看他是否是芒果销售商。这将先在一度关系中查找,再在二度关系中查找,因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从A到B的路径,而且找到的是最短的路径。

     注意,只有按添加顺序查找时,才能实现这样的目的。换句话说,如果Claire先于Anuj加入名单,就需要先检查Claire,再检查Anuj。如果Claire和Anuj都是芒果销售商,而你先检查Anuj再检查Claire,结果将如何呢?找到的芒果销售商并非是与你关系最近的,因为Anuj是你朋友的朋友,而Claire是你的朋友。因此,你需要按添加顺序进行检查。有一个可实现这种目的的数据
    结构,那就是队列(queue)。

    六、队列

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

    队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

    顺序队列

    建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置,如图所示

    每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列元素的个数不断变化,队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时,队列中没有任何元素,称为空队列。当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。

    顺序队列中的溢出现象:

    (1) "下溢"现象:当队列为空时,做出队运算产生的溢出现象。“下溢”是正常现象,常用作程序控制转移的条件。

    (2)"真上溢"现象:当队列满时,做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态,应设法避免。

    (3)"假上溢"现象:由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

    循环队列

    在实际使用队列时,为了使队列空间能重复使用,往往对队列的使用方法稍加改进:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0,可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间,环形空间中的存储单元循环使用,用这种方法管理的队列也就称为循环队列。除了一些简单应用之外,真正实用的队列是循环队列。 [2] 

    在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个队列元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件时front=rear,而队列判满的条件时front=(rear+1)%MaxSize。队空和队满的情况如图:

    七、广度优先搜索算法实现

    我们要从“你”出发找到“ANUJ”,关系表示为下图,使用广度优先搜索算法

     先概述一下这种算法的工作原理。

    但这样可能会出现一些问题,Peggy既是Alice的朋友又是Bob的朋友,因此她将被加入队列两次:一次是在添加Alice的朋友时,另一次是在添加Bob的朋友时。因此,搜索队列将包含两个Peggy。

    但你只需检查Peggy一次,看她是不是芒果销售商。如果你检查两次,就做了无用功。因此,检查完一个人后,应将其标记为已检查,且不再检查他。
    如果不这样做,就可能会导致无限循环。假设你的人际关系网类似于下面这样。

    一开始,搜索队列包含你的所有邻居。

    现在你检查Peggy。她不是芒果销售商,因此你将其所有邻居都加入搜索队列。

    接下来,你检查自己。你不是芒果销售商,因此你将你的所有邻居都加入搜索队列。

    以此类推。这将形成无限循环,因为搜索队列将在包含你和包含Peggy之间反复切换。

    检查一个人之前,要确认之前没检查过他,这很重要。为此,你可使用一个列表来记录检查过的人。

    首先,需要使用代码来实现图。图由多个节点组成。
    每个节点都与邻近节点相连,如果表示类似于“你→Bob”这样的关系呢?好在你知道的一种结构让你能够表示这种关系,它就是散列表!
    记住,散列表让你能够将键映射到值。在这里,你要将节点映射到其所有邻居。

    图不过是一系列的节点和边,因此在JAVA中,你可以使用HashMap来表示一个图。

    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.concurrent.LinkedBlockingQueue;
    
    public class BFS {
    
    
        public static void main(String[] args) {
            HashMap<String,String[]> hashMap=new HashMap<>();
            hashMap.put("YOU",new String[]{"CLAIRE","ALICE","BOB"});
            hashMap.put("CLAIRE",new String[]{"YOU","JONNY","THON"});
            hashMap.put("JONNY",new String[]{"CLAIRE"});
            hashMap.put("THOH",new String[]{"CLAIRE"});
            hashMap.put("ALICE",new String[]{"YOU","PEGGY"});
            hashMap.put("BOB",new String[]{"YOU","PEGGY","ANUJ"});
            hashMap.put("PEGGY",new String[]{"BOB","ALICE"});
            hashMap.put("ANUJ",new String[]{"BOB"});
            Node target = findTarget("YOU","ANUJ",hashMap);
            //打印出最短路径的各个节点信息
            printSearPath(target);
        }
    
        /**
         * 打印出到达节点target所经过的各个节点信息
         * @param target
         */
        static void printSearPath(Node target) {
            if (target != null) {
                System.out.print("找到了目标节点:" + target.id + "\n");
    
                List<Node> searchPath = new ArrayList<Node>();
                searchPath.add(target);
                Node node = target.parent;
                while(node!=null) {
                    searchPath.add(node);
                    node = node.parent;
                }
                String path = "";
                for(int i=searchPath.size()-1;i>=0;i--) {
                    path += searchPath.get(i).id;
                    if(i!=0) {
                        path += "-->";
                    }
                }
                System.out.print("步数最短:"+path);
            } else {
                System.out.print("未找到了目标节点");
            }
        }
    
        static Node findTarget(String startId,String targetId,HashMap<String,String[]> map) {
            List<String> hasSearchList = new ArrayList<String>();
            LinkedBlockingQueue<Node> queue=new LinkedBlockingQueue<>();
            queue.offer(new Node(startId,null));
            while(!queue.isEmpty()) {
                Node node = queue.poll();
                if(hasSearchList.contains(node.id)) {
                    continue;
                }
                System.out.print("判断节点:" + node.id +"\n");
                if (targetId.equals(node.id)) {
                    return node;
                }
                hasSearchList.add(node.id);
                if (map.get(node.id) != null && map.get(node.id).length > 0) {
                    for (String childId : map.get(node.id)) {
                        queue.offer(new Node(childId,node));
                    }
                }
            }
            return null;
        }
    
        static class Node{
            public String id;
            public Node parent;
            public Node(String id,Node parent) {
                this.id = id;
                this.parent = parent;
            }
        }
    }

    运行时间

    如果你在你的整个人际关系网中搜索芒果销售商,就意味着你将沿每条边前行(记住,边是从一个人到另一个人的箭头或连接),因此运行时间至少为O(边数)。
    你还使用了一个队列,其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的,即为O(1),因此对每个人都这样做需要的总时间为O(人数)。所以,广度优先搜索的运行时间为O(人数 + 边数),这通常写作O(V + E),其中V为顶点(vertice)数,E为边数。

    展开全文
  • 数据结构当中深度优先搜索算法和广度优先搜索算法的c语言算法
  • 广度优先搜索算法BFS

    2017-04-24 18:56:18
    广度优先搜索算法—BFS的相关代码,包括循环队列的代码
  • 主要介绍了python 递归深度优先搜索与广度优先搜索算法模拟实现 ,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
  • 广度优先搜索算法BFS(Breadth First Search) 对于广度优先搜索的原理,在CSDN上有很多博主已经介绍过了,可以参考下边的几篇博客。简单来讲的话广度优先搜索算法(Breadth First Search)就是优先搜索完距离自己最近的...

    广度优先搜索算法BFS(Breadth First Search)

    对于广度优先搜索的原理,在CSDN上有很多博主已经介绍过了,可以参考下边的几篇博客。简单来讲的话广度优先搜索算法(Breadth First Search)就是优先搜索完距离自己最近的节点,然后一层一层像是摊饼一样进行搜索,是一种面积最大化的搜索方式。
    广度优先搜索 - 一只程序猿 - CSDN博客 https://blog.csdn.net/hihozoo/article/details/51173175
    算法(三):图解广度优先搜索算法 - 风无言 - CSDN博客 https://blog.csdn.net/a8082649/article/details/81395359

    相信大家已经对广度优先搜索算法BFS有了一个最初步的概念,下面来讲一下他的python算法实现。
    对于python实现部分主要是参考GitHub上几个印度小哥做的python算法新手入门大全,github链接如下: https://github.com/TheAlgorithms/Python ,整个项目包含很多基础的算法,包括排序算法、搜索算法、插值算法、跳跃搜索算法、快速选择算法、禁忌搜索算法、加密算法等。在这里就不一一介绍了,这篇文章相关的主要是图形搜索算法,对应的模块是 https://github.com/TheAlgorithms/Python/tree/master/graphs

    以这样一个图的搜索作为例子,目标是从A点出发遍历所有节点。
    在这里插入图片描述

    广度优先度算法BFS的python代码实现

    # encoding=utf8  
    """pseudo-code"""
    
    """
    BFS(graph G, start vertex s):
    // all nodes initially unexplored
    mark s as explored
    let Q = queue data structure, initialized with s
    while Q is non-empty:
        remove the first node of Q, call it v
        for each edge(v, w):  // for w in graph[v]
            if w unexplored:
                mark w as explored
                add w to Q (at the end)
    
    """
    # collections 是 python 内建的一个集合模块,里面封装了许多集合类,其中队列相关的集合只有一个:deque。
    # deque 是双边队列(double-ended queue),具有队列和栈的性质,在 list 的基础上增加了移动、旋转和增删等。
    import collections
    
    
    def bfs(graph, start):
        explored = set()       # 已经访问过的节点集合
        queue = collections.deque([start])  # 初始化队列
        explored.add(start)
    
        print("========explored sort=========")
        while queue:   # 只要队列queue不是空的,就一直循环(隐含的意思就是只要这个点还有新的相邻点,那么就一直往下面进行搜索)
            # print(queue)
            v = queue.popleft()  # queue.popleft() #popleft,左边弹出元素,弹出的元素作为起始点,去查找相邻的点
            print(explored)
    
            for w in graph[v]:   # 遍历当前起始点的相邻点
                if w not in explored:   
                    explored.add(w) # 如果这个相邻点没有在已经探索过的集合里,那么就把这个相邻点加到探索过的集合里
                    queue.append(w) # 如果这个相邻点没有在已经探索过的集合里,那么就把这个相邻点压到队列里,在队列尾添加元素
        print("============All explored result==========")
        return explored
    
    
    G = {'A': ['B','C','D'],          # 无向图,表示A和B\C\D直接连接
         'B': ['A','E'],
         'C': ['A','F'],
         'D': ['A','K'],
         'E': ['B','I'],
         'F': ['C','H'],
         'H':['F'],
         'I':['E','J'],
         'J':['I'],
         'K':['D']}
    
    
    print(bfs(G, 'A'))
    

    BFS执行结果,可以看出广度优先搜索先把A相邻的节点BCD全都搜索完了,然后搜索“第三层”EFK,然后搜索“第四层”HI,最后才是第五层 J,也就是面积优先的一层一层往外搜索。queue遵循先进先出的选择

    python BFS.py 
    ========explored sort=========
    set(['A'])
    set(['A', 'C', 'B', 'D'])
    set(['A', 'C', 'B', 'E', 'D'])
    set(['A', 'C', 'B', 'E', 'D', 'F'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'K'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'K'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K', 'J'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K', 'J'])
    ============All explored result==========
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K', 'J'])
    
    

    深度优先算法 DFS

    # encoding=utf8  
    """pseudo-code"""
    
    """
    DFS(graph G, start vertex s):
    // all nodes initially unexplored
    mark s as explored
    for every edge (s, v):
        if v unexplored:
            DFS(G, v)
    """
    
    
    def dfs(graph, start):
        """The DFS function simply calls itself recursively for every unvisited child of its argument. We can emulate that
         behaviour precisely using a stack of iterators. Instead of recursively calling with a node, we'll push an iterator
          to the node's children onto the iterator stack. When the iterator at the top of the stack terminates, we'll pop
           it off the stack."""
        # explored, stack = set(), [start]
        explored = set()
        stack = [start]     # 相当于list类型变量实现stack
        explored.add(start)
        print("========explored sort=========")
        while stack:
            v = stack.pop()  # the only difference from BFS is to pop last element here instead of first one
            print(explored)
            for w in graph[v]:
                if w not in explored:
                    explored.add(w)
                    stack.append(w)
        print("============All explored result==========")
        return explored
    
    
    G = {'A': ['B','C','D'],          # 无向图,表示A和B\C\D直接连接
         'B': ['A','E'],
         'C': ['A','F'],
         'D': ['A','K'],
         'E': ['B','I'],
         'F': ['C','H'],
         'H':['F'],
         'I':['E','J'],
         'J':['I'],
         'K':['D']}
    
    
    print(dfs(G, 'A'))
    

    深度优先算法DFS在终端的执行结果,可以看出来优先一条一条的进行搜索, ADK ACFH ABEIJ 除了一开始搜了三个分支 BCD后面就开始对每个分支进行搜索下去了。stack遵循后进先出的原则。

    python DFS.py 
    ========explored sort=========
    set(['A'])
    set(['A', 'C', 'B', 'D'])
    set(['A', 'C', 'B', 'D', 'K'])
    set(['A', 'C', 'B', 'D', 'K'])
    set(['A', 'C', 'B', 'D', 'F', 'K'])
    set(['A', 'C', 'B', 'D', 'F', 'H', 'K'])
    set(['A', 'C', 'B', 'D', 'F', 'H', 'K'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'H', 'K'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K'])
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K', 'J'])
    ============All explored result==========
    set(['A', 'C', 'B', 'E', 'D', 'F', 'I', 'H', 'K', 'J'])
    
    
    展开全文
  • bfs广度优先搜索算法 1)广度优先搜索(BFS) (1) Breadth first search (BFS)) Breadth first search explores the space level by level only when there are no more states to be explored at a given level does ...

    bfs广度优先搜索算法

    1)广度优先搜索(BFS) (1) Breadth first search (BFS))

    Breadth first search explores the space level by level only when there are no more states to be explored at a given level does the algorithm move on to the next level.

    广度优先搜索仅当在给定级别上没有更多状态要探索时,算法才继续进行下一个级别。

    We implement BFS using lists open and closed to keep track of progress through the state space. In the order list, the elements will be those who have been generated but whose children have not been examined. The closed list records the states that have been examined and whose children have been generated. The order of removing the states from the open list will be the order of searching. The open is maintained as a queue on the first in first out data structure. States are added to the right of the list and removed from the left.

    我们使用打开和关闭列表来实现BFS ,以跟踪整个状态空间的进度。 在订单列表中,元素将是已生成但未检查其子元素的元素。 封闭列表记录了已检查的状态及其子代。 从打开列表中删除状态的顺序将是搜索的顺序。 开放保持为先进先出数据结构上的队列。 状态将添加到列表的右侧,然后从左侧删除。

    After initialization, each vertex is enqueued at most once and hence dequeued at most once. The operations of enqueuing and dequeuing take O (1) time, so the total time devoted to queue operations is O (v). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, the adjacency list of each vertex is scanned at most once. Since the sum of the lengths of all the adjacency lists is the ta(E), at most O(E) time is spent in total scanning adjacency lists. The overhead for the initialization is O(v), and thus the total running time of BFS is O(v+E). Thus, breadth first search runs in time linear in the size of the adjacency list representation.

    初始化后,每个顶点最多入队一次,因此最多出队一次。 入队和出队操作花费O(1)时间,因此用于排队操作的总时间为O(v) 。 因为仅在顶点出列时才扫描每个顶点的邻接表,所以每个顶点的邻接表最多被扫描一次。 由于所有邻接表的长度之和为ta(E),因此在总扫描邻接表中最多花费O(E)时间。 初始化的开销为O(v) ,因此BFS的总运行时间为O(v + E) 。 因此, 广度优先搜索在时间上与邻接列表表示的大小成线性关系。

    算法-广度优先搜索(BFS) (Algorithm - Breadth First Search (BFS))

        1.	Begin
        2.	Open = [start];
        3.	Closed =[];
        4.	While open != [] do
        5.	Begin
        6.	Remove leftmost state from open call it x;
        7.	If x is a goal then return success
        8.	Else
        9.	Begin
        10.	Generate children of x;
        11.	Put x on closed;
        12.	Put children on right end of open;
        13.	End
        14.	End
        15.	Return(failure)
        16.	End
    
    

    2)深度优先搜索(DFS) (2) Depth First Search (DFS))

    In depth first search, when a state is examined all of its children and their descendants are examined before any of its siblings. Depth first search goes deeper into the search space whenever this is possible, only when no further descendants of a state can be found, are its siblings considered.

    深度优先搜索 ,当检查一个状态时,将在其任何同级之前检查其所有子级及其子孙。 只要有可能, 深度优先搜索就会深入搜索空间,只有在找不到状态的其他后代时,才考虑其同级。

    A depth first traversal takes O(N*E) time for adjacency list representation and O(N2) for matrix representation.

    深度优先遍历的O(N * E)时间用于邻接表表示, O(N2)用于矩阵表示。

    算法-深度优先搜索(DFS) (Algorithm - Depth First Search (DFS))

        1.	Begin
        2.	Open = [start];
        3.	Closed = [];
        4.	While open != [] do
        5.	Begin
        6.	Remove left most state from open call it x;
        7.	If x is a goal then return success
        8.	Else
        9.	Begin
        10.	Generate children of x;
        11.	Put x on closed;
        12.	Put children on left end of open;
        13.	End
        14.	End
        15.	Return (failure)
        16.	End
    
    

    References:

    参考文献:

    翻译自: https://www.includehelp.com/algorithms/breadth-first-search-bfs-and-depth-first-search-dfs.aspx

    bfs广度优先搜索算法

    展开全文
  • 首先,我们先应该先了解一下什么是图,其次学习第一种图的算法,这种图的算法被称作是广度优先搜索算法(breadth-first search ,BFS)。 广度优先搜索算法其实就是帮助你找出两样东西之间的最短距离,掌握了这种算法...

    1、  序言

    又很久没有学习了,上次学到哈希表又称散列表的相关知识,这次我们学习一种新的数据结构来建立网络模型。这种数据结构被称作图。首先,我们先应该先了解一下什么是图,其次学习第一种图的算法,这种图的算法被称作是广度优先搜索算法(breadth-first search ,BFS)。

             广度优先搜索算法其实就是帮助你找出两样东西之间的最短距离,掌握了这种算法之后,我们可以完成以下几项内容:

    • 编写国际跳棋AI,计算出最少走多少步可以获胜

    • 编写拼写检查器,计算最少编辑多少个地方就可以将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方

    • 根据你的人际关系网络找到关系最近的医生

    --------此示例来源于《算法图解》

    2、  图简介

    听说户县到咸阳的大巴已经停运了,那么我们去咸阳的话就需要重新计算路线,(我们暂时排除自驾到咸阳的路线)假设我们乘坐公共交通工具前往,并且希望中间的换乘最少,可以到达的部分交通线路如下:

    a02ce28074651ff0cc3f4ddc4c334adc.png

      我们从图中可以发现想从石油大学直接到达咸阳湖景区,除了自驾其它并不能一步到达景区,接着我们使用两步、三步、四步发现都不能直接到达景区,最少也得需要五步,路线为:从石油大学东门(周南站)乘坐101路到鄠邑站,然后乘坐动车到达阿房宫站,然后乘坐1061路到达沣东第一学校站,接着换成咸阳郭杜线到达统一广场站,最终不步行到达咸阳湖景区。当然还有其他到达景区的路线,但它们执行起来路程会更远。这个算法发现,前往咸阳湖景区需要五步,这种问题在专业上称为“最短路径问题(shorterest-path problem)”。解决最短路径的问题的算法被称为广度优先搜索。

    就像上图一样,我们将路线用图解的形式展现出来,这就是图!其实非常简单,图由节点和边组成。一个节点可能与众多节点直接相连,这些众多节点都被称为这个节点的邻节点,在上图,大十字站和亚迪路站都被称为郭寨桥站的邻节点。

      一句话概括起来:图用于模拟不同的东西是如何相连的。

    3、  广度优先搜索

      广度优先搜索算法是一种可用于图的查找算法,可以帮助回答两类问题:

              从节点A出发,有前往节点B的路径吗?

      从节点A出发,前往节点B的哪条路径最短?

    举个例子,假设你经营着一个果园,每年秋天果子成熟了你需要将苹果卖给他。在微信上,你在好友列表中去找这么一个人。这种查找很简单,只需每看到一个人,然后想想他是不是收苹果的。

    假设你没有朋友是收苹果的,那么就必须在朋友的朋友中进行查找。然后问到信息之后立马把他记在小本本上,这样一来,不仅需要在朋友中进行查找,还需要在朋友的朋友中查找。如果你当前看到的朋友并不是收苹果的,就将其加入小本本里,这就意味着你将在他的人际关系中进行查找。这种算法最终会将你整个人际关系网进行搜索,直到找到苹果经销商,这就是广度优先搜索算法。

    • 广度优先搜索算法过程

      在刚才的例子中,我们先从自己的朋友开始找起,后来从朋友的朋友继续查找,自己朋友称为一度关系,朋友的朋友称为二度关系,显然,一度关系优于二度关系。

         搜索时,肯定是先自己的朋友,其次是朋友的朋友。当然只有按添加顺序查找时,才能达到搜索的目的。举个例子,张三是自己的朋友,李四是张三的朋友,但是李四先添加到名单中时,假设张三和李四都是收苹果的,但是由于添加顺序不对,必定会先搜索李四,然后再搜索张三,这样的话只是搜索到了苹果经销商,但没搜索到最近的朋友。

    7241f56f07d42f51d3749fa59b23bb92.png

      别忘了广度优先搜索需要解决两个问题:第一个是存在吗?第二个是最短吗?

        但是这种按照顺序存储的数据结构竟然存在,它的专业术语叫做“队列”。

    • 队列

      数据结构的队列就如同我们吃饭排队,秉承先来后到的原则,先到的先吃饭。队列类似于栈,你不能随机地访问队列中的元素,队列只支持两种操作:入队和出队。

    0938462f7c2f0695447ddb32a9336ade.png

      队列是一种先进先出的数据结构(First in First OutFIFO)

    3、  代码实现

    package cn.yanhao.breadthfirstsearch;/**
      *
    定义图类*/public class Graph
     {
    private final int  Max_VERTS = 6;   //图中顶点的个数private Vertex vertexList[];        //用来存储顶点的数组//用邻接矩阵来存储边,数组元素表示没有边界,1表示有边界private  int adjMat[][];private int nVerts;         //顶点个数private QueueX queue;       //用队列实现广度优先搜索/*顶点类
          */
    class Vertex{public char label;public boolean wasVisited;public Vertex(char label){this.label  = label;wasVisited = false;
             }
         }
         Graph(){
    //顶点数组长度初始化为20vertexList = new Vertex[Max_VERTS];//初始化20x20矩阵adjMat  = new int[Max_VERTS][Max_VERTS];nVerts = 0; //初始化顶点个数为0
             //
    初始化邻接矩阵所有元素都为0,即所有顶点没有边for (int i = 0; i  < Max_VERTS; i++) {for (int j = 0; j  < Max_VERTS; j++) {adjMat[i][j]  = 0;
                 }
             }
    queue = new QueueX();
         }
    //将顶点添加到数组中,是否访问位置置为wasVisited  = false(未访问)public  void addVertex(char lab){//先添加在加1vertexList[nVerts++] = new Vertex(lab);
         }
    //用邻接矩阵表示边,是对称的,两部分都要赋值public  void addEdge(int start,int end){adjMat[start][end]  = 1;adjMat[end][start]  = 1;
         }
    //打印某个顶点表示的值public  void displayVertex(int v){
             System.
    out.print(vertexList[v].label+"");
         }
    //找到与某一顶点邻接且未被访问的顶点public  int getAdjUnvisitedVertex(int v){for (int i = 0; i  < nVerts; i++) {//v顶点与i顶点相邻且未被访问if(adjMat[v][i]  == 1 && vertexList[i].wasVisited  == false){return i;
                 }
             }
    return -1;
         }
    /**
          *
    广度优先搜索* 1、用remove方法检查栈顶* 2、试图找到这个顶点还未被访问的邻接点* 3、如果没有找到,该顶点出列* 4、如果找到这样的顶点,访问这个顶点,并把它放入队列中*/public void breadthFirstSearch()
         {
    //第一个顶点可访问vertexList[0].wasVisited  = true;//打印第一个顶点的值displayVertex(0);//队列插入第一个元素queue.insert(0);int v2;//如果队列不为空while(!queue.isEmpty()){int v1 = queue.remove();while ((v2 =  getAdjUnvisitedVertex(v1)) != -1){vertexList[v2].wasVisited  = true;
                     displayVertex(v2);
    queue.insert(v2);
                 }
             }
    //搜索完毕,初始化,便于下次搜索for (int i = 0; i  < nVerts; i++) {vertexList[i].wasVisited  = false;
             }
         }
    public static  void main(String[] args) {
             Graph graph =
    new Graph();
             graph.addVertex(
    'A');
             graph.addVertex(
    'B');
             graph.addVertex(
    'C');
             graph.addVertex(
    'D');
             graph.addVertex(
    'E');
             graph.addEdge(
    0,1);     //ABgraph.addEdge(1,2);     //BCgraph.addEdge(0,3);     //ADgraph.addEdge(3,4);     //DESystem.out.println("广度优先搜索算法:");
             graph.breadthFirstSearch();
         }
     }

    展开全文
  • 广度优先搜索算法 问题:许多GPS导航系统使用BFS(宽度优先搜索)从地图上的一个点到另一个点,以最短路径算法。 在该项目中,将设计一种在图形上执行此操作的算法。 处理步骤: 阅读带有N个节点,M个链接和​​...
  • 主要介绍了PHP实现广度优先搜索算法(BFS,Broad First Search),简单描述了广度优先搜索算法的原理并结合具体实例分析了php实现广度优先搜索算法的步骤与相关操作技巧,需要的朋友可以参考下
  • 深度优先和广度优先搜索算法 文章目录深度优先和广度优先搜索算法1、先构建子节点以及子节点构成的二叉树2、广度优先:3、深度优先:4、代码结果 1、先构建子节点以及子节点构成的二叉树 //定义一个节点,节点连接有...
  • 主要介绍了C语言使用广度优先搜索算法解决迷宫问题,结合迷宫问题分析了C语言队列广度优先搜索算法的相关使用技巧,需要的朋友可以参考下
  • 今天终于把这个拿下来了广度优先搜索算法广度优先搜索算法是先访问图中的一个节点,然后再访问所有和它相邻的符合条件的节点依次往后直到访问完图中所有的节点。这些理论知识网上一搜都是一大把,就不详细赘述了。/*...
  • 图的广度优先搜索算法(BFS)Java版
  • MATLAB源码集锦-基于BFS广度优先搜索算法代码
  • 更高效率的广度优先搜索算法 学校课程和教科书中展示的经典广度优先搜索算法有时候效率非常的低下,因为即便所需的计算已经完成,经典的广度优先算法仍不会停止。下面的这篇被一位以图算法而著名的图灵奖获得者审查...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,173
精华内容 2,469
关键字:

广度优先搜索算法