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

    千次阅读 2013-04-12 21:58:56
    在http://www.cnblogs.com/yanlingyin/archive/2011/12/26/Depth-firstsearch.html 介绍了递归的深度搜索,写的比较好,最后我补充他的非递归方法。 图是一种常见的数据结构,深度优先和广度优先搜索都是常用...

    http://www.cnblogs.com/yanlingyin/archive/2011/12/26/Depth-firstsearch.html 介绍了递归的深度搜索,写的比较好,最后我补充他的非递归方法。

    图是一种常见的数据结构,深度优先和广度优先搜索都是常用的算法,这篇博文先介绍深度优先搜索。

    和往常一样的,我会用朴实的语言来介绍它,所以只要认真看一定能理解。开始会先介绍下图的表示方法,如果已经掌握了大可跳过。

    图的表示

    要表示一个图G(V,E)有两种常见的表示方法,邻接矩阵和邻接表。这两种方法可用于有向图和无向图。对于稀疏图,常用邻接表表示,

    它占用的空间|E|要小于|V|*|V|。

    邻接表:

    图G(V,E)的邻接表表示由一个包含V列表的数组Adj组成,其中的每个列表对应于V中的一个顶点,对于v中的任意一个点u,灵界表Adj[u]

    包含所有满足条件(u,v)属于E的点v,也就是Adj[u]中包含所有和u相邻的点。

    邻接矩阵:

    用一个矩阵表示,矩阵的横向和纵向分别为图中的点的有序排列,如果两个点之间有边相连对应的矩阵中的元素就是1,反之就是0.

    看下图实例就能很好的理解~

    对于一个无向图,所有邻接表的长度之和是2|E|,如果是有向图为|E|(无向图的每一条边都被表示了两遍)

    它有潜在的不足之处,如果要判断边(u,v)是否存在,只能在表Adj[u]中搜索v。如果有则存在,没有则不存在。

    在图G(V,E)的邻接矩阵表示法中,假定个顶点按照某种任意的方式编号1,2,3、、|V|,那么G的邻接矩阵就是一个

    |V|*|V|的举证A=(aij),它满足:

    它要占用|V|*|V|的空间,和边的数量无关。

    深度优先搜索:

    深度优先搜索是尽可能深的搜索一个图,对于一个新发现的节点,如果还有以此为起点还未探测到的边,就沿此边探测下去。

    当顶点v的所有边都被探寻过后,搜索将回溯到发现顶点v的起始点的那些边。这一过程一直进行到一发现从原点可达的所有点为止。

    如果还存在未发现的顶点,则选择其中一个座位源顶点,重复上过程。

    补充:

    1、在这个过程中可以记录每个点访问的时间。

    在访问点的时候记录下一个时间 t_start,当这个点所有邻居都被访问的时候记录时间 t_end.那么访问的时间 t =t_end-t_start.

    在算法中开始和结束的时间描述为d[u]和f[u].

    2、在每一次深度优先遍历的时候都记录下访问节点的前驱节点,可以用一个数组 f[i] 来存放,当完成遍历的是,就可以利用 f[i] 里面的数据来得到深度遍历的顺序。它的逆序就是

    这个图的一个拓扑排序。

    搜索过程中,可以通过对顶点着色来表示顶点的状态,开始时每个顶点都是白色,搜索过程中被发先置为灰色,

    结束时变为黑色,也就是每个有其他邻居可方位的时候。并且用d[u]和f[u]来记录点开始方问和结束访问的时间。

    Vertices initially colored white

    Then colored gray when discovered

    Then black when finished

    d[u]: discovery time, a counter indicating when vertex u is discovered.

    f[u]: finishing time, a counter indicating when the processing of vertex u (and the processing of all its descendants ) is finished.

    算法描述:

    1-3行把所有点置为白的,第三行把每个节点的父节点设置为空。第四行让时间计数为0。 5-7行一次检索v中的顶点,如果是白色,

    就调用DFS-VISIT访问该节点。每次调用DFS-VISIT(u)时,u就成为深度优先遍历中的一颗树根。

    调用DFS-VISIT(u)是,开始u置为灰色,第二行让time增值,第三行记录u的访问开始时间d[u],4-7行检查u的邻居,如果存在没有被

    访问的点,则深度优先遍历该点。第8行,因为访问了u 的所有邻居,u成了死节点,把u的颜色置为黑色,第9行记录u的访问结束时间。

    深度优先遍历的过程可以用下图表示:

     

    深度优先搜索的结果可能依赖于第DFS中5行中各个节点的访问顺序,也可能依赖于DFS-VISIT中的第4行中u的邻居的访问顺序。

    下面是c++实现:

    View Code
    复制代码
    /*
    图的深度优先遍历
    出处:一条鱼@博客园
    http://www.cnblogs.com/yanlingyin/
    2011-12-26

    */
    #include <stdlib.h>
    #include <stdio.h>

    struct node /* 图顶点结构定义 */
    {
    int vertex; /* 顶点数据信息 */
    struct node *nextnode; /* 指下一顶点的指标 */
    };
    typedef struct node *graph; /* 图形的结构新型态 */
    struct node head[9]; /* 图形顶点数组 */
    int visited[9]; /* 遍历标记数组 */

    /********************根据已有的信息建立邻接表********************/
    void creategraph(int node[20][2],int num)/*num指的是图的边数*/
    {
    graph newnode; /*指向新节点的指针定义*/
    graph ptr;
    int from; /* 边的起点 */
    int to; /* 边的终点 */
    int i;
    for ( i = 0; i < num; i++ ) /* 读取边线信息,插入邻接表*/
    {
    from = node[i][0]; /* 边线的起点 */
    to = node[i][1]; /* 边线的终点 */

    /* 建立新顶点 */
    newnode = ( graph ) malloc(sizeof(struct node));
    newnode->vertex = to; /* 建立顶点内容 */
    newnode->nextnode = NULL; /* 设定指标初值 */
    ptr = &(head[from]); /* 顶点位置 */
    while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
    ptr = ptr->nextnode; /* 下一个顶点 */
    ptr->nextnode = newnode; /* 插入节点 */
    }
    }

    /********************** 图的深度优先搜寻法********************/
    void dfs(int current)
    {
    graph ptr;
    visited[current] = 1; /* 记录已遍历过 */
    printf("vertex[%d]\n",current); /* 输出遍历顶点值 */
    ptr = head[current].nextnode; /* 顶点位置 */
    while ( ptr != NULL ) /* 遍历至链表尾 */
    {
    if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
    dfs(ptr->vertex); /* 递回遍历呼叫 */
    ptr = ptr->nextnode; /* 下一个顶点 */
    }
    }

    /****************************** 主程序******************************/
    int main()
    {
    graph ptr;
    int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
    {1, 3}, {3, 1},
    {1, 4}, {4, 1},
    {2, 5}, {5, 2},
    {2, 6}, {6, 2},
    {3, 7}, {7, 3},
    {4, 7}, {4, 4},
    {5, 8}, {8, 5},
    {6, 7}, {7, 6},
    {7, 8}, {8, 7} };
    int i;
    //clrscr();
    for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
    {
    head[i].vertex = i; /* 设定顶点值 */
    head[i].nextnode = NULL; /* 指针为空 */
    visited[i] = 0; /* 设定遍历初始标志 */
    }
    creategraph(node,20); /* 建立邻接表 */
    printf("Content of the gragh's ADlist is:\n");
    for ( i = 1; i <= 8; i++ )
    {
    printf("vertex%d ->",head[i].vertex); /* 顶点值 */
    ptr = head[i].nextnode; /* 顶点位置 */
    while ( ptr != NULL ) /* 遍历至链表尾 */
    {
    printf(" %d ",ptr->vertex); /* 印出顶点内容 */
    ptr = ptr->nextnode; /* 下一个顶点 */
    }
    printf("\n"); /* 换行 */
    }
    printf("\nThe end of the dfs are:\n");
    dfs(1); /* 打印输出遍历过程 */
    printf("\n"); /* 换行 */
    puts(" Press any key to quit...");
    // getch();
    }
    复制代码

    以上代码cfree5上编译通过。

     

     

     

     

    图的深度优先搜索可以用栈来实现,对某一层的点比如有A,B,C都把他们入栈,每次都把栈顶元素的孩子入栈,当某个点没有孩子的时候,

    就回退到有孩子的节点,把它的孩子入栈,重复上过程,直到根节点的每一个孩子都入栈,最后的出栈顺序就是深度优先遍历的顺序。

    相应的,广度优先搜索利用队列来实现,对于某一层的点A,B,C,把他们入队列,然后队列头出队列,对头的孩子入队列,如果A有孩子M,N

    ,那么A出队列后队列为:BCMN,下一步就是B出队列,B的孩子入队列、、、、最后出队列的顺序就是广度优先遍历的顺序。

     下一篇将会介绍广度优先搜索算法~

    非递归程序:

    /*
    图的深度优先遍历
    出处:一条鱼@博客园 http://www.cnblogs.com/yanlingyin/
    2011-12-26 
    
    */
    #include <stdlib.h>
    #include <stdio.h>
    
    struct node                       /* 图顶点结构定义     */
    {
       int vertex;                    /* 顶点数据信息       */
       struct node *nextnode;         /* 指下一顶点的指标   */
    };
    typedef struct node *graph;       /* 图形的结构新型态   */
    struct node head[9];              /* 图形顶点数组       */
    int visited[9];                   /* 遍历标记数组       */
    
    /********************根据已有的信息建立邻接表********************/
    void creategraph(int node[20][2],int num)/*num指的是图的边数*/
    {
       graph newnode;                 /*指向新节点的指针定义*/
       graph ptr;
       int from;                      /* 边的起点          */
       int to;                        /* 边的终点          */
       int i;
       for ( i = 0; i < num; i++ )    /* 读取边线信息,插入邻接表*/
       {
          from = node[i][0];         /*    边线的起点            */
          to = node[i][1];           /*   边线的终点             */
          
       /* 建立新顶点 */
          newnode = ( graph ) malloc(sizeof(struct node));
          newnode->vertex = to;        /* 建立顶点内容       */
          newnode->nextnode = NULL;    /* 设定指标初值       */
          ptr = &(head[from]);         /* 顶点位置           */
          while ( ptr->nextnode != NULL ) /* 遍历至链表尾   */
             ptr = ptr->nextnode;     /* 下一个顶点         */
          ptr->nextnode = newnode;    /* 插入节点        */
       }
    }
    
    /**********************  图的深度优先搜寻法********************/
    void dfs(node head[9],int current){/*非递归深度优先遍历算法*/
    	node* p;
    	node* stack[9];
    	int top=-1,vertex;
    	printf("%d\n",current);
    	visited[current] = 1;
    	stack[++top] = head[current].nextnode;
    	while(top > -1){
    		p = stack[top];
    		while(p != NULL){
    			vertex = p->vertex;
    			if(visited[vertex] == 0){
    				printf("%d\n",vertex);
    				visited[vertex] = 1;
    				stack[++top] = head[vertex].nextnode;
    				//printf("%dss\n",stack[top]->vertex);
    				break;
    			}
    			p = p->nextnode;
    		}
    		if(p == NULL){
    			top--;
    		}
    	}
    }
    /****************************** 主程序******************************/
    int main()
    {
       graph ptr;
       int node[20][2] = { {1, 2}, {2, 1},  /* 边线数组     */
                           {1, 3}, {3, 1},
                           {1, 4}, {4, 1},
                           {2, 5}, {5, 2},
                           {2, 6}, {6, 2},
                           {3, 7}, {7, 3},
                           {4, 7}, {4, 4},
                           {5, 8}, {8, 5},
                           {6, 7}, {7, 6},
                           {7, 8}, {8, 7} };
       int i;
       //clrscr();
       for ( i = 1; i <= 8; i++ )      /*   顶点数组初始化  */
       {
          head[i].vertex = i;         /*    设定顶点值      */
          head[i].nextnode = NULL;    /*       指针为空     */
          visited[i] = 0;             /* 设定遍历初始标志   */
       }
       creategraph(node,20);          /*    建立邻接表      */
       printf("Content of the gragh's ADlist is:\n");
       for ( i = 1; i <= 8; i++ )
       {
          printf("vertex%d ->",head[i].vertex); /* 顶点值    */
          ptr = head[i].nextnode;             /* 顶点位置   */
          while ( ptr != NULL )       /* 遍历至链表尾       */
          {
             printf(" %d ",ptr->vertex);  /* 印出顶点内容   */
             ptr = ptr->nextnode;         /* 下一个顶点     */
          }
          printf("\n");               /*   换行             */
       }
       printf("\nThe end of the dfs are:\n");
       dfs(head,1);                        /* 打印输出遍历过程   */
       printf("\n");    
       printf("\nThe end of the dfs are:\n");              /* 换行               */
      // getch();
    }


    展开全文
  • 1.深度优先搜索中的关键 2.深度优先搜索小结 ...对于深度优先搜索,最重要的参数有两个,第一是 深度搜索的次数 step,可以看做需要将待搜索的结果放入到 step 个盒子中,直到放满为止。 第二个是每一...

     

     

    1.深度优先搜索中的关键

    2.深度优先搜索小结

    3.深度优先搜索和回溯法的区别

    4.深度优先搜索与递归的区别


    1.深度优先搜索中的关键

    深度搜索算法通常用来 解决 全排列不重复组合分组问题多条路径路径的条数等等

    对于深度优先搜索,最重要的参数有两个,第一是 深度搜索的次数 step,可以看做需要将待搜索的结果放入到 step 个盒子中,直到放满为止。

    第二个是每一次 深度搜索的开始位置start, 主要控制的是每次深度搜索的范围

    比如:

    对于全排列问题,求[1,2,3]的全排列问题,此时我们可以将问题转化为 将 1,2,3按不同的次序放入到三个盒子中,我们需要的是控制深度搜索的次数step,这个次数就是我们深度搜索的结束条件(收敛条件)

    对于求子集问题,求[1,2,3]的全部子集(不能重复),与全排列不同,为了求出不重复的子集,我们需要使在1右边的元素永远在1的右边,也就是说,在第二次深度搜索时我们的搜索范围应该是[2,3],此时我们并不控制深度搜索的次数,而是控制的是深度搜索开始的位置。

    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) 
        {
            vector<bool> book(nums.size(),false);
            vector<int> tmp;
            vector<vector<int>> res;
            dfs(nums,0,book,tmp,res);
            return res;
        }
        
    private:
        void dfs(vector<int>& nums,int step,vector<bool>&book,vector<int>& tmp,vector<vector<int>>& res)
        {
            if(step == nums.size())
            {
                res.push_back(tmp);
                return;
            }
            for(int i = 0; i < nums.size();i++)
            {
                if(!book[i])
                {
                    tmp.push_back(nums[i]);
                    book[i] = true;
                    dfs(nums,step+1,book,tmp,res);
                    tmp.pop_back();
                    book[i] = false;
                }
            }
        }
    };

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) 
        {
            vector<vector<int>> res;
            vector<int> path;
            dfs(nums, 0, path, res);
            return res;
        }
    private:
        void dfs(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res)
        {
            res.push_back(path);
            
            for(int i = start; i < nums.size(); i++)//这里用的是start,控制每一次深搜的范围
            {
                path.push_back(nums[i]);
                dfs(nums,i+1,path,res);
                path.pop_back();
            }
        }
        
    };

    当然,有些情况下,我们即需要控制 深搜的次数 又需要控制每一次深搜的范围,这种问题典型特征是 分配出了要求的盒子数,

    而且是组合问题

    较简单的:

    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) 
        {
            vector<vector<int>> res;
            vector<int> path;
            dfs(n, k,1, 0, path, res);
            return res;
        }
        
    private:
        void dfs(int n, int k,int start, int step, vector<int>& path, vector<vector<int>>& res)
        {
            if(step == k)
            {
                res.push_back(path);
                return;
            }
            for(int i = start; i <= n; i++)
            {
                path.push_back(i);
                dfs(n,k,i+1,step+1,path,res);
                path.pop_back();
            }
        }
    };

    较难的:

    这一题目中,虽然没有明确说拆分为的盒子数,但是根据IP的特征,应该拆分为4个盒子

    同时,这也是一个组合问题(只不过是字符串写在了一起而已),需要控制每次深度搜索的初始位置

    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) 
        {
            vector<string> res;
            string path;
            if(s.size() > 12)
            {
                return res;
            }
            dfs(s, 0,0,path,res);
            return res;
        }
    private:
        void dfs(string s, int start,int step,string path, vector<string>& res)
        {
            if(start == s.size() && step == 4)
            {
                res.push_back(path);
                return;
            }
            for(int i = 1; i <= s.size();i++)
            {
                if(start + i > s.size())
                {
                    return;
                }
                string section = s.substr(start,i);
                if(section.size() > 1 && section[0] == '0' || convert(section) > 255)
                {
                    return;
                }
    
                //同时这里用了一个小技巧,因为是字符串,所以不能pop掉后面过来的字符串,所以选择下面这一种方式,来进行回溯
                dfs(s,start+i,step+1,step == 0 ? section : path + "." + section,res);
            }
        }
        int convert(string section)
        {
            int sum = 0;
            for(int i = 0; i < section.size(); i++)
            {
                sum = sum*10 + section[i] - '0';
            }
            return sum;
        }
        
    };

    对于二维空间的深度搜索,如果起点已经定下,则由此点开始向上下左右扩展即可,如果起点没有定下来,则在主调函数中进行遍历起点,并对每一个起点进行深度优先搜素,同时,如果深度搜索函数有返回值,则对其进行组合处理即可

    起点确定下的二维深度搜索:

    class Solution {
    public:
        int uniquePaths(int m, int n) 
        {
            vector<vector<int>> book(m+1,vector<int>(n+1,0));
            return dfs(m,n,0,0,book);   
        }
        
    private:
        int dfs(int m, int n,int i,int j,vector<vector<int>>& book)
        {
            if( i == m-1 && j == n-1)//收敛条件
            {
                return 1;
            }
            if(i >= m || j >= n)
            {
                return 0;
            }
            return getbook(m,n,i+1,j,book) + getbook(m,n,i,j+1,book);        
        }
        
        int getbook(int m,int n,int i,int j,vector<vector<int>>& book)
        {
            if(book[i][j] > 0)
            {
                return book[i][j];
            }
            else
            {
                return book[i][j] = dfs(m,n,i,j,book);
            }
        }
        
    };

    起点不确定条件下的二维深度搜索:

    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) 
        {
            int m = board.size();
            int n = board[0].size();
            vector<vector<bool>> book(m,vector<bool>(n,false));
            
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n;j++)
                {
                    if(exist(board,i,j,0,word,book))
                    {
                        return true;
                    }
    
                }
            }
            return false;
            
        }
    private:
        bool exist(vector<vector<char>>& board,int i,int j,int step,string word,vector<vector<bool>>& book)
        {
            if(step == word.size() )//注意:这个step必须为连续不断的step,不能断
            {
                return true;
            }
            if(i < 0 || j < 0 || i >= board.size() || j >= board[0].size())
            {
                return false;
            }
            if(book[i][j])
            {
                return false;
            }
            if(board[i][j] != word[step])
            {
                return false;
            }
    
            book[i][j] = true;
            bool res = exist(board,i+1,j,step+1,word,book) || exist(board,i,j+1,step+1,word,book) ||exist(board,i-1,j,step+1,word,book) || exist(board,i,j-1,step+1,word,book);
            book[i][j] = false;
            return res;
        }
    };

    2.深度优先搜索小结

    深度优先搜索适用:

                             如果是递归数据结构,比如单链表,二叉树,集合,则一定可以用深度搜索,如果是非递归数据结构,如一维数组,二维数组,字符串,图等则概率小一些

                             明确深搜是求路径本身还是路径条数,前者则用一个数组 path来进行记录存储,后者不用存储路径

                            终止条件是什么?终止条件只的是不能扩展的末端节点,对于树,则是叶子节点

                            收敛条件是什么?收敛条件是指找到了一个合法解,很多时候终止条件和收敛条件是合二为一的,但两者代表的含义是不同的

                           剪枝加速,深度搜索的优点 是能在答案生成一半时就进行判断,舍弃不满足要求的答案,减少冗余搜索;利于题设中的各种信息,一旦判断此时的答案不会满足要求,则提前返回,避免冗余搜索

                         深度搜索代码模板:

    void dfs(type *input,type* path,int step(int start),type *result)
    {
        if(数据非法) return;
        if(step == input.size() (or start == input.size()))//收敛条件
        {
            将path放入 res中
            return;
        }
        if(可以剪枝) return;
        for(...) //执行所有可能的扩展操作
        {
            执行动作,修改path
            dfs(input,path,step+1(or start+1),res);
            恢复path;        
        }
    }

    3.深度优先搜索和回溯法的区别

    回溯法= 深度搜索  + 剪枝

    深度搜索 准确的来讲,在搜索过程中会保留下来完整的树结构,即使遍历结果不满足答案,也会继续搜素下去,

    而回溯法 是在深度搜索的过程中进行判断中间结果,如果中间结果不满足条件要求,则进行返回,不再搜索下去,

    但是由于现在我们在深度搜索的过程中,或多或少会进行剪枝,所以这样来看两者并没有什么区别

     

    4.深度优先搜索与递归的区别

    深搜常常用递归来实现,二者常常同时出现,但是两者并不是同一个东西。

    深搜,是一种算法,而递归是一种物理意义上的实现,递归和迭代是对应的。深搜可以用递归来实现,也可以用栈来实现,而递归,一般总用来实现深搜。

    可以说,递归一定是深搜,深搜不一定用递归

    递归有两种加速策略:一种是剪枝,对中间结果进行判断,提前返回(回溯),一种是加缓存,缓存中间结果,防止重复计算(动态规划),当然动态规划也可以用迭代来实现

    还有一个问题:既然递归一定是深搜,那为什么要有两种术语呢?一般而言,在递归味道更浓的地方,一般用递归,比如在单链表,二叉树等递归数据结构上,而在图,数组等数据结构上,递归的比重不大,深搜的味道更浓,所以用深搜,但两者大部分情况下指同一回事。

    展开全文
  • 深度搜索和广度搜索 - 图的遍历

    千次阅读 2015-03-07 11:39:27
    图的连接表示 深度搜索 广度搜索 DFS BFS

    一. 图的连接表示

    一种表示图的直接方法是使用二维数组,也称为邻接矩阵。通过邻接矩阵表示顶点 i 和 j 之间是否存在一条边(检查邻接矩阵中行 i 和 j 处是否为非零值)。定义数组visited[N] 标记节点是否被访问过。
    以下程序:如果在图中顶点 i 和顶点 j 或者顶点 j 和顶点 i 之间存在一条边,就把关联矩阵 G->edges[i][j] 和 G->edges[j][i] 设置为 1 ;如果不存在这样的边,则设置为 0 。
    图的结构图的关联矩阵
    创建图的程序如下:

    typedef struct Graph
    {
        int edges[MAX][MAX]; //连接矩阵
        int e;  //边数
        int n;  //顶点数
    }Graph;
    void CreatGraph(Graph* G)
    {
        for(int i = 0; i < G->n; i++)
        {
            for(int j = 0; j < G->n; j++)
            {
                G->edges[i][j] = 0; //初始化连接矩阵
            }
            visited[i] = 0; //初始化访问标记
        }
        //输入相连的顶点
        for(int k = 0; k < G->e; k++)
        {
            int s, t, v;
            v = 1;//权重,非0即连接
            printf("Please enter two connected vertices\n");
            scanf("%d%d", &s, &t);
            G->edges[s][t] = v;
        }
    }

    二. 图的遍历

    沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
    这里写图片描述
    如上图所示的无向图,从0 节点开始遍历的顺序:0 -> 1 -> 3 -> 5 -> 4 -> 2
    DFS的实现方式一般有两种:递归实现和非递归实现:

    递归实现

    实现程序简单,比较常用

    void DFS(Graph* G, int i)
    {
        printf("Visiting %d\n", i);
        visited[i] = 1;
        for(int j = 0; j < G->n; j++)
        {
            if(G->edges[i][j] != 0 && visited[j] == 0)
                DFS(G, j);
        }
    }

    非递归实现:

    使用栈压入每一个没有被访问过的节点,由于栈的后进先出的原理,我们总是以最后访问的那一节点(栈顶节点)为起始节点,访问下一个未被访问过的节点,当当前栈顶节点没有后续连接节点要访问时,从栈中弹出。
    这里写图片描述
    例如上图从节点 0 开始访问的过程为:
    访问 0,压入 0 ,访问 1 压入 1,访问 3 压入 3,访问 5 压入 5, 弹出 5(无与 5 相连且未访问的节点),弹出 3 ,访问 4 (此时栈顶为 1),压入 4,弹出 4,访问 2,弹出 2,弹出 0, 栈空。
    遍历的顺序:0 -> 1 -> 3 -> 5 -> 4 -> 2

    void DFS1(Graph* G, int i)
    {
        printf("Visiting %d\n", i);
        visited[i] = 1;
        Stack s = NULL;
        s = StackInit(s);
        StackPush(s, i);
        while (!StackIsEmpty(s))
        {
            i = StackTop(s);
            int j;
            for (j = 0; j < G->n; j++)
            {
                if (G->edges[i][j] != 0 && visited[j] == 0)
                {
                    printf("Visiting %d\n", j);
                    visited[j] = 1;
                    StackPush(s, j);
                    break;
                }
            }
            if (j == G->n) //已无与i相连且未访问的节点
            {
                StackPop(s);
            }
        }
    }

    又译作宽度优先搜索,或横向优先搜索,简称BFS,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。
    使用FIFO队列压入每一个没有被访问过的节点, 由于队列的先进先出的原理,我们总是以最开始访问的那一节点(队列顶节点)为起始节点,访问所有与之相连且未被访问过的节点,当当前队列顶节点没有后续连接节点要访问时,从队列中弹出。
    这里写图片描述
    访问顺序为:0 -> 1 -> 2 -> 3 -> 4 -> 5
    遍历过程为: 访问 0 ,压入 0, (队列顶一直为 0 )<访问 1 压入 1,访问 2 压入 2 >,弹出 0 ,(队列顶一直为 1 )<访问 3 压入 3,访问 4 压入 4>,弹出 1,(队顶为2),弹出 2,(队顶为3)访问 5 ,弹出 3,(队顶为4)弹出 4,访问压入5,弹出 5.

    void BFS(Graph *G, int i)
    {
        printf("Visiting %d\n", i);
        visited[i] = 1;
        Queue q = NULL;
        q = (Queue)malloc(sizeof(q));
        QueueInit(q); //上一句分配内存后,应该初始化后才能正常使用
    
        QueuePut(q, i);
        while(!QueueIsEmpty(q))
        {
            i = QueueGet(q);
            for(int j = 0; j < G->n; j++)
            {
                if(G->edges[i][j] != 0 && visited[j] == 0)
                {
                    printf("Visiting %d\n", j);
                    visited[j] = 1;
                    QueuePut(q, j);
                }   
            }   
        }
    }

    三.测试主程序

    #include<stdio.h>
    #include "stack.h"
    #include "queue.h"
    #define MAX 100
    typedef struct Graph Graph;
    int visited[MAX];
    struct Graph
    {
        int edges[MAX][MAX]; //连接矩阵
        int e;  //边数
        int n;  //顶点数
    };
    
    //将visited[]全部设为0
    void visitedInit(Graph* G, int visited[])
    {
        for (int i = 0; i < G->n; i++)
        {
            visited[i] = 0;
        }
    }
    //创建图(矩阵连接)
    void CreatGraph(Graph* G)
    {
        for(int i = 0; i < G->n; i++)
        {
            for(int j = 0; j < G->n; j++)
            {
                G->edges[i][j] = 0; //初始化连接矩阵
            }
    
            visited[i] = 0; //初始化访问标记
        }
        //输入相连的顶点
        for(int k = 0; k < G->e; k++)
        {
            int s, t, v;
            v = 1;//权重,非0即连接
            printf("Please enter the two connected vertices\n");
            scanf("%d%d", &s, &t);
            G->edges[s][t] = v;
        }
    }
    
    //递归深度优先搜索
    void DFS(Graph* G, int i)
    {
        printf("Visiting %d\n", i);
        visited[i] = 1;
        for(int j = 0; j < G->n; j++)
        {
            if(G->edges[i][j] != 0 && visited[j] == 0)
                DFS(G, j);
        }
    
    }
    //非递归深度优先搜索,栈
    void DFS1(Graph* G, int i)
    {
        printf("Visiting %d\n", i);
        visited[i] = 1;
        Stack s = NULL;
        s = StackInit(s);
        StackPush(s, i);
        while (!StackIsEmpty(s))
        {
            i = StackTop(s);
            int j;
            for (j = 0; j < G->n; j++)
            {
                if (G->edges[i][j] != 0 && visited[j] == 0)
                {
                    printf("Visiting %d\n", j);
                    visited[j] = 1;
                    StackPush(s, j);
                    break;
                }
            }
            if (j == G->n)
            {
                StackPop(s);
            }
        }
    
    }
    //广度优先搜索
    void BFS(Graph *G, int i)
    {
        printf("Visiting %d\n", i);
        visited[i] = 1;
        Queue q = NULL;
        q = (Queue)malloc(sizeof(q));
        QueueInit(q); //上一句分配内存后,应该初始化后才能正常使用
    
        QueuePut(q, i);
        while(!QueueIsEmpty(q))
        {
            i = QueueGet(q);
            for(int j = 0; j < G->n; j++)
            {
                if(G->edges[i][j] != 0 && visited[j] == 0)
                {
                    printf("Visiting %d\n", j);
                    visited[j] = 1;
                    QueuePut(q, j);
                }   
    
            }   
        }
    }
    
    int main()
    {
        int n, e;
        Graph* G = (Graph*)malloc(sizeof(*G));
        printf("Please enter the number of vertices and edges\n");
        scanf("%d %d", &n, &e); //输入图的顶点数和边数
        G->n = n;
        G->e = e;
        CreatGraph(G);
    
        printf("\nDepth-First-Search-1:\n");
        DFS(G, 0);
    
        visitedInit(G, visited); //将visited[]全部设为0
        printf("\nDepth-First-Search-2:\n");
        DFS1(G, 0);
    
        visitedInit(G, visited); //将visited[]全部设为0
        printf("\nBreadth-First-Search:\n");
        BFS(G, 0);
    
        system("pause");
        return 0;
    }

    结果如下:
    这里写图片描述

    四. 源代码下载

    http://pan.baidu.com/s/1DAD6u

    展开全文
  • 深度搜索算法查找最短路径

    千次阅读 2019-02-27 11:05:04
    从图中可以得到一个5*5的二维矩阵,利用深度搜索算法,求出最短路径。从最后的运行结果,可以直观的看出搜索的过程 代码实现如下: #include "pch.h" #include &lt;stdio.h&gt; #include &...

    如图,百度地图上有5个地点,各个地点间是单向的路径,试求出从1到5的最短路径。

    从图中可以得到一个5*5的二维矩阵,利用深度搜索算法,求出最短路径。从最后的运行结果,可以直观的看出搜索的过程

    代码实现如下:

    
    #include "pch.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <vector>
    using namespace std;
    
    #define M 99999999
    
    const int CityNum = 5;
    const int cityMap[CityNum][CityNum] =
    {
    	0,2,M,M,10,
    	M,0,3,M,7,
    	4,M,0,4,M,
    	M,M,M,0,5,
    	M,M,3,M,0
    };
    bool book[CityNum] = { false };
    int iMin = M;
    vector<int> vecPath;
    void ShowPath()
    {
    	for (size_t i=0; i<vecPath.size(); i++)
    	{
    		printf("->%d", vecPath[i]+1);
    	}
    }
    void dfs(int iCur, int iDes, int iDis)
    {
    	vecPath.push_back(iCur);
    	if (iDis > iMin)
    	{
    		ShowPath();
    		printf("->More than Min:%d>%d\r\n", iDis, iMin);
    		return;
    	}
    	if (iDes == iCur)
    	{
    		if (iDis < iMin)
    		{
    			iMin = iDis;
    		}
    		ShowPath();
    		printf("->MinPath:%d\r\n", iMin);
    		return;
    	}
    
    	for (int i=0; i<CityNum; i++)
    	{
    		if (cityMap[iCur][i] != M && !book[i])
    		{
    			book[i] = true;
    			dfs(i, iDes, iDis + cityMap[iCur][i]);
    			vecPath.pop_back();
    			book[i] = false;
    		}
    		else
    		{
    			ShowPath();
    			printf("->%dX\r\n", i + 1);
    		}
    
    	}
    
    }
    
    int main()
    {
    	book[0] = true;
    	dfs(0, 4, 0);
    	printf("Shortest path is %d", iMin);
    	
    	return 0;
    }

    运行结果:打印出路径

    展开全文
  • 创建二叉树 树的深度搜索 广度搜索

    千次阅读 2014-05-14 11:19:33
    树的创建 深度搜索 广度搜索
  • C++ - 深度搜索遍历文件夹

    千次阅读 2013-11-26 21:12:18
    深度搜索遍历文件夹   深度优先搜索遍历文件夹所有文件, 由于使用windows的函数, 必须要使用C语言; 注意字符集的问题,使用"#undef UNICODE", 屏蔽因字符集所产生的问题; 代码如下: #undef UNICODE #include #...
  • 深度搜索(DFS)和广度搜索(BFS)

    千次阅读 2019-07-18 10:52:34
    深度搜索(DFS) 一、搜索方法:  沿出发顶点的第一条路径尽量深入,遍历路径上所有顶点;然后退回到该顶点,搜索其它路径,直到以该顶点为始点的所有路径的顶点都被访问,深度搜索算法是递归算法,因为对于没一个...
  • 深度搜索和广度搜索

    千次阅读 2016-12-12 15:18:59
    深度优先搜索和广度优先搜索的深入讨论(一)深度优先搜索的特点是:(1)从上面几个实例看出,可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的,如例题2-4,2-5,2-6;有的是未知的,...
  • 以用户指定的结点分别进行广度搜索和深度搜索 相应的生成树的边集 运行截图 源代码 public class AdjacencyList { public static void main(String[] args) { CreateGraph createGraph=new CreateGraph(); ...
  • java结课以后,就想写一个文件搜索的程序,本以为会很难的,原来用深度优先搜索算法代码这么短,写出来分享一下。。。 import java.io.*; public class seek{ /*深度优先搜索算法*/ private static void...
  • 深度搜索算法C语言实现,以走迷宫为例子
  • DFS,深度搜索,回溯法,递归,迷宫问题
  • 深度搜索、深搜。简单地说深搜就是一种**【不撞南墙不回头】** 的 **暴力算法**,基本上该算法常用递归作为设计基础,当然也有使用for循环嵌套的,本文是以递归为讲解方向的。 至于更深一层的理论在这里就不详细说明...
  • ——————dfs深度搜索用于遍历寻找解;2;实现原理;——bfs;利用队列;层次来搜索的; 模板;//结合上图理解代码;Q={起点s}; 标记s为己访问; while (Q非空) { 取Q队首元素u; u出队; 所有与u相邻且未被...
  • 深度搜索(dfs)题 1011,含各种剪枝,比较经典
  • 深度优先搜索是按照树的深度进行搜索的,所以又叫纵向搜索,在每一层只扩展一个节点,直到为树的规定深度或叶子节点为止。这个便称为深度优先搜索。 我先来说说两种算法的不同点。广度优先搜索,适用于所有情况下的...
  • 分支定界之深度搜索定界

    千次阅读 2006-06-05 09:18:00
    深度搜索定界原文 http://it.pjschool.com.cn/Article/ArticleShow.asp?ArticleID=231原文题为分支定界, 深度搜索定界是其中例2, 例1代码已重写为 http://blog.csdn.net/jq0123/archive/2006/05/30/762957.aspx此为...
  • 作业调度问题深度搜索定界算法

    千次阅读 2006-06-12 12:50:00
    作业调度问题深度搜索定界算法深度搜索定界设有n台处理机p1,p2,......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断,作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短?...
  • 深度优先搜索 分析过程 实现代码 进出栈过程示意图 DFS算法应用-Leetcode相关题目 Leetcode 78 Subsets Leetcode 90 Subsets II Leetcode 47 Permutations II Leetcode 131 Palindrome Partitioning 答案 搜索...
  • 深度搜索破密码

    千次阅读 2013-04-16 15:35:51
    百度一面的一道题目,今天才想起来实现以下,给面试官说的时候没表达清楚,现在想想原因还是对递归掌握的深度不够,逻辑没有表达好. 下面是代码,其中characters里存放的是密码可能出现的字符,我这里只存了几个,比较方便...
  • 旅行售货员问题-回溯法-深度搜索

    万次阅读 2018-05-06 16:33:40
    若当前搜索的层次i = n 时,处在排列树的叶节点的父节点上,此时算法检查图G是否存在一条从顶点x[n-1] 到顶点x[n] 有一条边,和从顶点x[n] 到顶点x[1] 也有一条边。若这两条边都存在,则发现了一个旅行售货员的回路...
  • 深度搜索迷宫问题(C语言实现)

    千次阅读 2020-05-14 13:18:30
    算法步骤: 使用一个栈来保存符合要求的点,每次根据栈顶的点的k值(1表示上,2表示右,3表示下,4表示左)依次取下一个点,满足条件则不断循环;若某一个点的四面都不行,则进行出栈回溯。当找到这样一条路径,也要进行...
  •  深度优先搜索(缩写DFS)有点类似广度优先搜索,也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,然后从另一条路开始走到底...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 271,854
精华内容 108,741
关键字:

深度搜索