精华内容
下载资源
问答
  • DFS深度优先算法

    2017-10-16 16:54:47
    DFS深度优先算法对图进行遍历(用邻接矩阵的方式表示图) 核心代码部分: #include #include using namespace std; struct Graph1 //使用邻接矩阵来构造图 { int v; //图的顶点数 int e; //图的边数 int **...

    用DFS深度优先算法对图进行遍历(用邻接矩阵的方式表示图)

    核心代码部分:

    #include<iostream>
    #include<string>
    using namespace std;
    
    
    struct Graph1 //使用邻接矩阵来构造图
    {
    	int v;  //图的顶点数
    	int e;    //图的边数
    	int ** arc;  //邻接矩阵
    	int kind;    //0,为有向图,1,为无向图
    	string * info; //表示每个顶点的信息
    
    };
    
    void DFS(Graph1 g, int v, bool * & visit) //深度优先算法
    {
    	cout << g.info[v] << " ";
    	visit[v] = true;
    	for (int i = 0; i < g.v; i++) {//找出下一个没有访问过的
    		if (g.arc[v][i] == 0 || g.arc[v][i] == INT_MAX) { //如果两个顶点之间没有边
    			continue;
    		}
    		else if (!visit[i]) {
    			DFS(g, i, visit);
    		}
    	}
    }
    
    void DFS_travel(Graph1 g, int begin) //深度优先遍历函数
    {
    	bool * visit;
    	visit = new bool[g.v];
    	int i;
    	for (i = 0; i < g.v; i++) {
    		visit[i] = false;
    	}
    	cout << "DFS遍历:" << endl;
    	DFS(g, begin - 1, visit);
    	//如果图是非连通的,需要再遍历一次
    	for (i = 0; i < g.v; i++) {
    		if (!visit[i])
    			DFS(g, i, visit);
    	}
    
    }




    展开全文
  • DFS 深度优先算法

    2019-05-24 17:38:35
    题目 代码 import java.util.Scanner;...public class Main2dfs { private static int n, a[], k; /** * * 4 1 2 4 7 13 4 1 2 4 7 15 */ public static void ...

    题目

     

         

     

    代码

    import java.util.Scanner;
    
    public class Main2dfs {
    	
    	private static int n, a[], k;
    
    	/**
    	 * 
    	 *
    	 
    	 4
    	 1 2 4 7
    	 13
    	 
    	 4
    	 1 2 4 7
    	 15
    	 
    	 
    	 */
    	
    	public static void main(String[] args) {
    		// 输入n, a[], k
    		Scanner in = new Scanner(System.in);
    		n = in.nextInt();
    		a = new int[n];
    		for (int i = 0; i < n; i++) {
    			a[i] = in.nextInt();
    		}
    		k = in.nextInt();
    		
    		
    		if (dfs(0, 0)) {
    			System.out.println(true);
    		} else {
    			System.out.println(false);
    		}
    		
    	}
    	
    	// 已经从前i项得到了和sum,然后对于i项之后的进行分支
    	private static boolean dfs(int i, int sum) {
    		System.out.println("i:" + i + " sum:" + sum);
    		
    		// 如果前n项都计算过了,则返回sum是否与k相等
    		if (i == n) {
    			return sum == k;
    		}
    		
    		// 不加上a[i]的情况
    		if (dfs(i+1, sum)) {
    			return true;
    		}
    		
    		// 加上a[i]的情况
    		if (dfs(i+1, sum+a[i])) {
    			return true;
    		}
    		
    		// 无论是否加上a[i]都不能凑成k就返回false
    		return false;
    	}
    
    }
    

     

    图解

     

    题目和代码出处

    excel表单方便看自己写的

    展开全文
  • 回溯算法(DFS 深度优先算法)实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以...

    基本认识

    回溯算法(DFS 深度优先算法)实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

    基本思想与原理

    回溯法(DFS 深度优先算法)简单来说就是按照深度优先的顺序,穷举所有可能性的算法,但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否符合问题的条件。一旦不符合条件,那么就退回到上一个状态,省去了继续往下探索的时间。
    换句话说,回溯法可以理解为通过选择不同的岔路口寻找目的地,一个岔路口一个岔路口的去尝试找到目的地。如果走错了路,继续返回来找到岔路口的另一条路,直到找到目的地。省去了在错路上走下去的时间。

    适用的问题

    如果一个问题是搜索求解类的问题,而且该问题的解是树状结构(不断扩张式向量),该题就可以考虑使用回溯算法。
    回溯算法的典型例题和适用特点

    加粗样式

    求解的步骤与模板

    回溯函数的三个组成部分:

    1.回溯出口:当找到了一个问题的解时,存储该解。

    2.回溯主体:就是遍历当前的状态的所有子节点,并判断下一个状态是否是满足问题条件的,如果满足问题条件,那么进入下一个状态。

    3.状态返回:如果当前状态不满足条件,那么返回到前一个状态。

    回溯函数万能模板:

    以python3为例:

    def backtrack ( 参数 ):
    
    	#回溯出口
    	if ( 满足题意了 ):
    		计数或进行其他操作
    		return True   #有时可以省略
    	
    	#回溯主体
    	for( 查找当前节点的周围的节点 )
    		进行其他的操作;
    		标记已经搜索过的节点
    		backtrack( 下一次搜索的节点 )
    	#状态返回
    		取消标记;
    	return False	#有时可以省略
    

    引例部分

    八皇后问题:
    八皇后问题是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?

    解题思路:
    1.从棋盘的第一行开始,从第一个位置开始,依次判断当前位置是否能够放置皇后,判断的依据为:同该行之前的所有行中皇后的所在位置进行比较,如果在同一列,或者在同一条斜线上(斜线有两条,为正方形的两个对角线),都不符合要求,继续检验后序的位置。
    2.如果该行所有位置都不符合要求,则回溯到前一行,改变皇后的位置,继续试探。
    3.如果试探到最后一行,所有皇后摆放完毕,则直接打印出 8*8 的棋盘。最后一定要记得将棋盘恢复原样,避免影响下一次摆放。

    实战部分

    组合总数Ⅱ问题:
    在这里插入图片描述

    解题思路:
    这道题的思路是:以 target 为根结点,依次减去数组中的数字,直到小于0或者等于0,把等于0的结果记录到结果集中。
    “解集不能包含重复的组合”,就提示我们得对数组先排个序(“升序”或者“降序”均可,下面示例中均使用“升序”)。
    “candidates 中的每个数字在每个组合中只能使用一次”,那就按照顺序依次减去数组中的元素,递归求解即可:遇到0就结算且回溯,遇到负数也回溯。
    candidates 中的数字可以重复,可以借助「LeetCode」第 47 题:“全排列 II”(后面刷题练习部分有链接) 的思想,在搜索的过程中,找到可能发生重复结果的分支,把它剪去。
    这里借用Leetcode上一位大佬的图片来帮助理解
    这里借用Leetcode上一位大佬的图片来帮助理解

    下面附上Python3的题解代码

    class Solution:
        def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
            l=len(candidates)
            if l==0:
                return []
            candidates.sort()                                           #初始化
            path=[]
            res=[]
            
            def backtrack(begin,path,target):
                if target==0:                                           #回溯出口
                    res.append(path[:])
                for i in range(begin,l):                                #回溯主体
                    target_next=target-candidates[i]    #剪枝操作
                    if target_next<0:
                        break
                    if i>begin and candidates[i-1]==candidates[i]:
                        continue
                    path.append(candidates[i])
                    backtrack(i+1,path,target_next)
                    path.pop()                                          #状态返回
            
            backtrack(0,path,target)
            return res
    

    趁热打铁 刷题练习部分(持续更新)

    以下是LeetCode题库中一些用到回溯算法的经典例题的题目及解析,有题干,有题解代码、有解题思路(持续更新):

    No.17.电话号码的字母组合:
    https://blog.csdn.net/LanXiu_/article/details/104085787

    No.22.括号生成:
    https://blog.csdn.net/LanXiu_/article/details/104103922

    No.37.解数独:
    https://blog.csdn.net/LanXiu_/article/details/104176266

    No.39.组合总和:
    https://blog.csdn.net/LanXiu_/article/details/104176266

    No.40.组合总和Ⅱ:
    https://blog.csdn.net/LanXiu_/article/details/104176266

    No.44.通配符匹配:
    https://blog.csdn.net/LanXiu_/article/details/104177349

    No.46.全排列:
    https://blog.csdn.net/LanXiu_/article/details/104177432

    No.47.全排列Ⅱ:
    https://blog.csdn.net/LanXiu_/article/details/104177432

    展开全文
  • dfs深度优先算法

    千次阅读 2013-04-08 15:32:55
     深度优先,就是从一个点出发,一直深入下去,直到叶子节点,然后返回,在深入,直到 遍历完所有的节点,为了深刻的理解遍历的过程,可以单步跟踪一下。 单步跟踪:遇到函数按F11,进入函数;进入函数后按...

    题目:

    今天是阴历七月初五,acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日,经过调查,zb发现C小加和 never都很喜欢吃西瓜,而且一吃就是一堆的那种,zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候,遇到了一个难 题,never和C小加不在一块住,只能把西瓜分成两堆给他们,为了对每个人都公平,他想让两堆的重量之差最小。每个西瓜的重量已知,你能帮帮他么?

    输入:

    多组测试数据(<=1500)。数据以EOF结尾
    第一行输入西瓜数量N (1 ≤ N ≤ 20)
    第二行有N个数,W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量

    输出:

    输出分成两堆后的质量差

    样例输入:

    5

    5 8 13 27 14

    样例输出:

    3

     

    下面是源程序:

    #include<stdio.h>
    #include<iostream>
    #include<cstdlib>
    #include<fstream>
    
    
    using namespace std;
    
    int melon[21];
    int n;
    int mins;//不要定义为min或max,以免与库函数冲突
    int total;
    
    void findmin(int i,int sum)//i为层数;sum为当前和
    {    
        if(i==n) //到i = n;时,最后一次讨论是否包含[n-1];
        {
            int temp=abs(total - sum - sum);//当前两部分的差额    
            if(mins > temp)
                mins=temp;
            return;
        }
    /*  这里是一个剪枝;不用所有的都走到底部。
        if(sum > total/2 )//如果当前的和已经大于一半,剪枝
        {
            int temp=abs(total - sum - sum);//当前两部分的差额    
            if(mins > temp)//如果最小差额比当前的差额大
            {
                mins = temp;            
            }
            return ;
        }
    */
        findmin(i+1,sum);//不算melon[i]
        findmin(i+1,sum+melon[i]);//算上melon[i]
    }
    
    int main()
    {
        int i;    
    
        while(cin>>n)
        {    
            total=0;
            mins=9999999;
            for(i=0;i<n;i++)
            {
                scanf("%d",&melon[i]);
                total+=melon[i];//西瓜总重量
            }//for
            if(n==0)
                cout<<melon[0]<<endl;
            else
            {
                findmin(0,0);
                cout<<mins<<endl;
            }
        }//while
        return 0;
    }


     深度优先,就是从一个点出发,一直深入下去,直到叶子节点,然后返回,在深入,直到

    遍历完所有的节点,为了深刻的理解遍历的过程,可以单步跟踪一下。

    单步跟踪:遇到函数按F11,进入函数;进入函数后按F10,单步走。这样就可以清楚的查看每一步。

    下面就是跟从得到的树状图:

    注释:输入的数据是:   2      1     2

    就是从两个,分别是1和2     [0]代表第0个,[1]代表第1个。

    遍历时就会把所有的情况都遍历一遍,每个元素都可能在或不在集合中。

    展开全文
  • 数据结构_dfs深度优先算法入门(C语言) 文章目录数据结构_dfs深度优先算法入门(C语言)0.闲话1.个人理解2.全排列问题(1到n的排列组合)2.八皇后问题求解二维迷宫(1)只输走出迷宫解的个数(2)输出解的个数和...
  • DFS深度优先算法/LeetCode 93题 从一个顶点开始,沿着某条线路遍历到该路径的末端,然后回溯,再沿着另一条线进行同样的遍历,直到所有顶点都被遍历完。 算法思路: 1、任选一顶点作始点 v ,访问该顶点 2、沿深度...
  • LeetCode刷题笔记(12)DFS深度优先算法Ⅱ 背景 好几天没刷题了,出差做作业然后工作比较忙,应该改正。今天是LeetCode的深度优先算法第二部分,也结束了。 130、填充封闭区域 给定一个二维的矩阵,包含 ‘X’ 和 ...
  • 深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分 支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已...
  • 因为要遍历所有的结果,所以DFS深度优先算法 #include #include using namespace std; #define N 20 int m,n; int dirctions[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int visited[N][N]; char map[N][N]; int sum=...
  • DFS深度优先算法java算法

    千次阅读 2014-11-24 21:29:23
     我学习算法,按照老师给的算法弄的…… 完成时间2014年11月24日
  • 来源:https://www.bilibili.com/video/BV1Ks411575U/?spm_id_from=333.788.videocard.0 BFS广度优先算法 graph = { "A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B", "D", "E...
  • 深度优先算法实现图的遍历代码如下: #include &lt;iostream&gt; using namespace std; int book[101],sum,n=5,e[101][101]; void dfs(int cur) { cout&lt;&lt;" "&lt;&lt;...
  • 深度优先搜索算法(英语:Depth-First-Search,简称DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将...
  • #include <...void DFS(int a[10][10], int flag[], int start); int main() { int a[10][10]; int flag[10]; for (int i = 1; i <= 8; i++) { flag[i] = 0; } for (int i = 1; i &.
  • 还是那句话,数据量小,要求简单,果断DFS! 这道题目跟以前的题目稍微有点不一样的是方向有点变化,由原来的四方向变成了八个方向,其实是一样的 只不过是在遍历的时候多几个而已,直接给出代码 #include ...
  • void DFS(int x,int y) { int nx,ny; for(int i=0;i;i++) { nx=x+dirctions[i][0]; ny=y+dirctions[i][1]; if(map[nx][ny]=='.'&&nx>=0&&nx<m&&ny>=0&&ny[nx][ny]==0) { visited[nx][ny]=1; sum++; DFS...
  • DFS(深度优先搜索算法)

    万次阅读 多人点赞 2018-10-07 16:32:43
    深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到...
  • DFS深度优先搜索算法

    2019-08-07 19:38:59
    深度优先搜索算法(英语:Depth-First-Search,简称DFS) 是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索...
  • 1.dfs深度优先搜索算法 算法导论中是通过三种标记颜色来介绍dfs的,white代表还没被搜过,grey代表被搜了一些,还没结束,white表示已经搜索完成的状态。 c/c++复现dfs代码 #include<iostream> #include<...
  • 深度优先搜索算法(DFS) 深度优先搜索算法思路:(有点贪心算法的意思) 1,从某个给定结点a出发,访问它 ...下面给出了在邻接矩阵存储情况下的深度优先算法,每个被访问过的结点用visited数组标记: void...
  • 算法DFS深度优先搜索算法 几种特殊的情况 空树 判断的当前节点为空,则需要返回最小深度为0 只有一个节点 这一个节点就是叶子结点,无需递归,但深度也需要加一 两个结点 根节点的左节点递归一次,深度为2,右节点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,197
精华内容 1,678
关键字:

dfs深度优先算法