精华内容
下载资源
问答
  • 广度搜索

    2011-11-29 17:34:30
    ACM入门(3)——图的遍历——广度优先搜索 基本算法:  由Moore和Lee独立提出  给定图G和一个源点s, 广度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离  广度优先的过程对结点着色.  ...
    ACM入门(3)——图的遍历——广度优先搜索
    基本算法: 
    由Moore和Lee独立提出 
    给定图G和一个源点s, 广度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离 
    广度优先的过程对结点着色. 
    白色: 没有考虑过的点 
    黑色: 已经完全考虑过的点 
    灰色: 发现过, 但没有处理过, 是遍历边界 
    依次处理每个灰色结点u, 对于邻接边(u, v), 把v着成灰色并加入树中, 在树中u是v的父亲(parent)或称前驱(predecessor). 距离d[v] = d + 1 
    整棵树的根为s 


    BFS算法: 
    BFS(G,s)//从s点开始对图G广度优先搜索for each vertex u∈V[G]-{s}        do color← white//每个点赋值为未处理          d←∞  //每个点与源点的距离标志为∞∏←NIL       //每个点赋值为没有父亲color[s] ←gray              //s点标为正在处理d[s] ←0                     //s点与源点的距离为0Q ←ф                   //建空队列保存灰色顶点ENQUEUE(Q,s)       //源点入队列While(Q≠ф)    do u ←DEQUEUE(Q);//从队列中拿出一个元素进行处理         for each v ∈Adj //对没有处理过的邻接点进行处理              do  if  color[v]=white                        then color[v] ←gray                                d[v]=d+1∏[v]=u                                ENQUEUE(Q,v)         color=black//标记为处理完毕


    用BFS求最短路: 
    定理: 对于无权图(每条边的长度为1), BFS算法计算出的d是从s到i的最短路 
    满足d=1的点一定是正确的(因为长度至少为1), 并且其他点都满足d>1. 容易证明对于任意距离值x, d=x的点一定是正确的, 而且白色点(没有计算出距离的点)的距离一定至少为x+1 
    更进一步, 根据每个点的parent值, 可以计算出它到s的一条最短路 
    Bfs算法中路径的打印 
    Print-Path(G,s,v) 
    ①   if(v==s) 
    ②        then print s 
    ③        else if ∏[v]=NIL 
    ④                  then print “no path from ”s”to” v”exits” 
    ⑤                  else Print-path(G,s, ∏[v]) 
    ⑥                         print v 
    展开全文
  • 广度搜索和深度搜索

    2019-06-12 10:45:01
    广度搜索和深度搜索 这篇文章从有向图和无向图来说明两种搜索的区别,很详细。

    广度搜索和深度搜索
    这篇文章从有向图和无向图来说明两种搜索的区别,很详细。

    展开全文
  • 双向广度搜索

    2017-05-22 14:43:48
    广度搜索是十分基本的搜索规则,就是从初始节点开始一层层扩展到目标节点,但它只能较好地解决状态不太多的问题,一旦搜索量巨大,往往会出现内存空间不够用的状况。双向广度搜索就是对广度搜索的改进,减少空间和...

    广度搜索是十分基本的搜索规则,就是从初始节点开始一层层扩展到目标节点,但它只能较好地解决状态不太多的问题,一旦搜索量巨大,往往会出现内存空间不够用的状况。双向广度搜索就是对广度搜索的改进,减少空间和时间上的复杂度。

    有些问题按照广度搜索进行节点扩展,即适合逆序,也适合顺序,于是可以将单向搜索变为双向,初始节点向目标节点以及目标节点向初始节点,当两个扩展方向上出现同一个节点,搜索结束。


    例如:移动一个只含字母A和B的字符串中的字母,给定初始状态为(a)表,目标状态为(b)表,给定移动规则为:只能互相对换相邻字母。请找出一条移动最少步数的办法。

    [AABBAA]  [BAAAAB] 
     (a)       (b)
    
    解题分析:从初始状态和目标状态均按照深度优先搜索扩展结点,当达到以下状态时,出现相交点,如图1(a),结点序号表示结点生成顺序。
    双向扩展结点:
                       顺序                           逆序
                        1                              1
                   ___AABBAA___                      BAAAAB
              2   /            /  3                2 /    / 3
          __ABABAA__            AABABA           ABAAAB  BAAABA
       4 /    |5    / 6       7 /    / 8       4 /
    ABBAAA  BAABAA  ABAABA  AAABBA  AABAAB    AABAAB
                     (a)            图1               (b)
    

      顺序扩展的第8个子结点与逆序扩展得到的第4个子结点就是相交点,问题的最佳路径如图2。


        [AABBAA]—[AABABA]—[AABAAB]—[ABAAAB]—[BAAAAB]

                              图2


    对于双向扩展顺序上的选择:由于大部分的解答树不是完全树,在扩展完一层后,下一层则选择节点个数较少的那个方向先扩展。


    下面就以一道经典的Leetcode算法题为例:

    Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWord to endWord, such that:

    1. Only one letter can be changed at a time
    2. Each transformed word must exist in the word list. Note thatbeginWord is not a transformed word.

    For example,

    Given:
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log","cog"]

    Return

      [
        ["hit","hot","dot","dog","cog"],
        ["hit","hot","lot","log","cog"]
      ]
    

    Note:

    • Return an empty list if there is no such transformation sequence.
    • All words have the same length.
    • All words contain only lowercase alphabetic characters.
    • You may assume no duplicates in the word list.
    • You may assume beginWord and endWord are non-empty and are not the same.

    UPDATE (2017/1/20):
    The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.


    该题的解题思路:通过DFS找寻到endWord所在的层,那么该长度就为最短路径长度。DFS期间通过一个map映射来记录每个节点以及其可达的下一节点的逆映射关系。因为如果某一节点先出现,那么该节点后出现并达到endWord的长度必然更大,所以每次出现一个节点需将其从wordList中删除。如果进行优化?那就是使用双向DFS来代替DFS,最终的结果显示效率提升了3倍,基于双向DFS的解法代码如下:

    class Solution {
    public:
        vector<string> tmp_path;
        vector<vector<string>> result_path;
        
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            unordered_set<string> front,back,next;
            unordered_map<string,unordered_set<string>> path;
            unordered_set<string> dict;
            
            for(int i=0;i<wordList.size();i++)
                dict.insert(wordList[i]);
            
           // dict.erase(beginWord);
            //dict.erase(endWord);
            
            front.insert(beginWord);
            if(dict.count(endWord))
                back.insert(endWord);
            bool done = false;
            while(done == false && dict.size() > 0)
            {
                if(front.size() < back.size())
                {
                    for(auto it = front.begin();it!=front.end();it++)
                        dict.erase(*it);
                    for(auto it = front.begin();it!=front.end();it++)
                    {
                        string word = *it;
                        for(int i=0;i<word.size();i++)
                            for(char change='a';change<='z';change++)
                            {
                                string tmp =word;
                                tmp[i] = change;
                                if(back.count(tmp))
                                {
                                    done = true;
                                    path[word].insert(tmp);
                                }
                                else if(done == false && dict.count(tmp))
                                {
                                    next.insert(tmp);
                                    path[word].insert(tmp);
                                }
                            }
                    }
                     front = next;
                }
                else
                {
                    for(auto it = back.begin();it!=back.end();it++)
                        dict.erase(*it);
                    for(auto it = back.begin();it!=back.end();it++)
                    {
                        dict.erase(*it);
                        string word = *it;
                        for(int i=0;i<word.size();i++)
                            for(char change='a';change<='z';change++)
                            {
                                string tmp =word;
                                tmp[i] = change;
                                if(front.count(tmp))
                                {
                                    done = true;
                                    path[tmp].insert(word);
                                }
                                else if(done == false && dict.count(tmp))
                                {
                                    next.insert(tmp);
                                    path[tmp].insert(word);
                                }
                            }
                    }
                     back = next;
                }
                
                if(next.empty())
                    break;
    
                next.clear();           
            }
            
            if(done == true)
                generatePath(path,beginWord,endWord);
            
            return result_path; 
        }
        
        void generatePath(unordered_map<string,unordered_set<string>>& path,string start,string end)
        { 
            tmp_path.push_back(start);
            if(start == end)
            {
                result_path.push_back(tmp_path);
                return;
            }
            
            for(auto it =path[start].begin();it != path[start].end();it++)
            {
                generatePath(path,*it,end);
                tmp_path.pop_back();
            }
        }
    };








    展开全文
  • 适合大学生,学生党学习c++的二叉树的广度搜索遍历的c++程序。
  • 图的广度搜索

    2013-08-30 09:31:38
    利用队列实现图的广度搜索,层次结构清晰,代码质量高,能够加深对图的广度搜索认识
  • C# 广度搜索和深度搜索实现贪吃蛇自动寻路。。。。。。。。。。。。。。。。。。。。。
  • 广度搜索和深度搜索的分析 广度优先搜索和深度优先搜索各有他的优点,也有他们的不足之处。 广度优先搜索在遍历的时候不需要全部遍历,搜索到符合条件的就立即终止,这样就不会浪费太多时间。但是在遍历的过程中,他...

    广度搜索和深度搜索的分析

    广度优先搜索和深度优先搜索各有他的优点,也有他们的不足之处。
    广度优先搜索在遍历的时候不需要全部遍历,搜索到符合条件的就立即终止,这样就不会浪费太多时间。但是在遍历的过程中,他需要创建一个队列来保存遍历的状态(也就是遍历到的每一个结点需要先存入到队列中,然后取出),这样就无非就增加了空间复杂度。
    而深度优先搜索则会遍历所有的结点,不需要保存遍历的状态,虽然时间复杂度高但是空间复杂度低。在使用深度优先搜索的时候非常容易超时,因为每次遍历时间复杂度都是以指数的形式增长的。所以我们在使用深度优先搜索的时候我们一般都会联合奇偶剪枝一起使用,这样就极大的降低了深度优先搜索的时间复杂度。
    奇偶剪枝:奇偶剪枝就是在你遍历的过程中,首先判断你这个结点能不能按要求到达目的地,如果能,则访问他的邻结点,否则,退出这一层遍历。
    部分内容来自:https://blog.csdn.net/chyshnu/article/details/6171758
    把矩阵看成如下形式:
    0 1 0 1 0 1
    1 0 1 0 1 0
    0 1 0 1 0 1
    1 0 1 0 1 0
    0 1 0 1 0 1
    从为 0 的格子走一步,必然走向为 1 的格子 。
    从为 1 的格子走一步,必然走向为 0 的格子 。
    即:
    从 0 走向 1 必然是奇数步,从 0 走向 0 必然是偶数步。

    所以当遇到从 0 走向 0 但是要求时间是奇数的或者 从 1 走向 0 但是要求时间是偶数的,都可以直接判断不可达!
    比如一张地图c
    
     
    S...  
    ....  
    ....  
    ....  
    ...D  
    要求从S点到达D点,此时,从S到D的最短距离为s = abs ( dx - sx ) + abs ( dy - sy )。
    如果地图中出现了不能经过的障碍物:
    S..X  
    XX.X  
    ...X  
    .XXX  
    ...D  
    此时的最短距离s' = s + 4,为了绕开障碍,不管偏移几个点,偏移的距离都是最短距离s加上一个偶数距离。
    不管你怎么绕,最终到达目的地的步数都是一个最短步数加上一个偶数。
    

    一般深度优先搜索用来解那种需要得到全部解的题,而广度优先搜索则是用来求最短路径的,到达的每一个结点都是最短路径。

    展开全文
  • 深度搜索 深度优先搜索(depth-first seach,...广度搜索 广度优先搜索(breadth-first search,BFS)不同与深度优先搜索,它是一层层进行遍历的,因 此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历,
  • 广度搜索是一项重要的软件设计技术,该例采用C编程实现了3个水杯倒水,采用广度搜索的实现算法
  • 基于python的多线程广度搜索 定向图片url爬取处理器
  • 这篇主要是记录一下学习二叉树的深度搜索和广度搜索的学习过程,有问题希望大家多多指正。 首先,下图是一颗二叉树: 深度优先搜索(DFS): 深度优先搜索是从根节点出发,沿左子树方向进行纵向遍历,直到找到叶子...
  • TSP广度搜索算法C++

    2009-12-24 00:51:31
    TSP广度搜索算法C++ TSP广度搜索算法C++
  • 深度搜索和广度搜索 两种C版本的 需要的可以下载 希望对大家有所帮助
  • 图 拓扑排序 深度搜索 广度搜索 最小生成树
  • 迷宫深度搜索和广度搜索 是否可以走出迷宫和最短路径 1234567890
  • 广度搜索/深度搜索

    2020-02-12 16:45:33
    深度搜索 深度搜索(邻接矩阵方式) 深度搜索(邻接表结构) 广度优先遍历 广度优先遍历(邻接矩阵方式) 广度优先遍历(邻接表方式)
  • 广度搜索 c++

    2013-12-30 01:04:11
    用C++写的 BFS (brand first search)广度优先搜索
  • 广度搜索hdu1548

    2016-11-19 20:11:44
    题意:有个电梯在每一层只有固定的...思路:广度搜索按层搜索即可,每次记录步数,一到终点就退出循环。用C++的STL队列要方便些。 代码: #include using namespace std; #include #include #include <string.h>int N,
  • 创建二叉树 树的深度搜索 广度搜索

    千次阅读 2014-05-14 11:19:33
    树的创建 深度搜索 广度搜索
  • 广度搜索hdu1372

    2016-11-19 23:06:31
    题意大概就是在国际象棋上,问马从a点到b... 思路:这种求最少步数或者最小次数的题一般都是用广度搜索来解就行了。#include using namespace std; #include #include int s1, s2, e1, e2; int map[8][8]; int x2x[8]
  • 使用广度搜索的方法实现八数码问题,代码GCC亲自测试无误,有备注,有题目说明
  • 深度搜索和广度搜索 - 图的遍历

    千次阅读 2015-03-07 11:39:27
    图的连接表示 深度搜索 广度搜索 DFS BFS
  • 广度搜索 深度搜索:优先深度扫描,如果当前路径走到了死胡同,那么,又依次访问上次访问过的节点的可走路径。就这样如此往复,最终完成图的遍历。 深度搜索类似于树的前序遍历 广度搜索:优先广度扫描,假设你前面...
  • 广度搜索优先

    2018-10-04 17:01:11
    广度优先搜索的通俗化定义 所谓广度,就是一层一层的,向下遍历,层层堵截,还是这幅图,我们如果要是广度优先遍历的话,我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。 1、访问顶点vi ; 2、访问vi 的所有未被访问的...
  • 盲目搜索(广度搜索)解重排九宫问题,即把数码问题的盲目搜索求解!C++实现的。
  • 前面项目在做一个遍历搜索的时候,有用到深度/广度搜索的相关知识;原理很简单,不再拾人牙慧了哈;这篇文章主要是将我自己简单实现的深广度搜索分享出来并与Python networkx模块中的已有实现做一个简单对比。 1....
  • 我知道这不值钱,但我穷的没点下载东西了。希望需要的兄弟赞助下。 c/c++用递归实现深度搜索和广度搜索解迷宫的源码。 广度搜索可找出迷宫的最优路径。
  • 本人自己总结的acm广度搜索实例代码,经典的几个代码程序 只有代码,没有题目,主要是在POJ的。我是在ubuntu下压缩的。
  • 用C语言编写的深度、广度搜索代码,方便C语言初学者使用!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,703
精华内容 5,881
关键字:

广度搜索