精华内容
下载资源
问答
  • 本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考,具体如下: 深度优先搜索 伪代码 (Pseudocode)如下: 将起点标记为已走过并压栈; while (栈非空) { 从栈顶弹出一个点p; if (p这个...
  • C#深度优先搜索算法

    2020-08-30 04:28:24
    主要介绍了C#深度优先搜索算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 该代码是DFS算法的实现,讲解部分可以查看我的博客
  • MATLAB源码集锦-基于深度优先搜索算法图论代码
  • 深度优先搜索算法

    2016-04-09 17:56:52
    深度优先C代码
  • 主要介绍了PHP实现深度优先搜索算法(DFS,Depth First Search),简单分析了深度优先搜索算法的原理并结合具体实例给出了php实现深度优先搜索的具体步骤与相关操作技巧,需要的朋友可以参考下
  • 基于matlab的深度优先算法,输入邻接矩阵,如果联通返回1,否则返回零
  • 人工智能,八数码问题,深度优先搜索算法,c语言编写
  • (DFS)深度优先搜索算法详解

    千次阅读 多人点赞 2021-09-13 01:37:08
    DFS 英文全称为(Depth First Search),中文简称深度优先搜索算法,其过程为沿着每一个可能的路径向下进行搜索,直到不能再深入为止,并且每一个节点只能访问一次。 算法的搜索遍历图的步骤 (1)首先找到初始...

    背景

    DFS 英文全称为(Depth First Search),中文简称深度优先搜索算法,其过程为沿着每一个可能的路径向下进行搜索,直到不能再深入为止,并且每一个节点只能访问一次。
     

    算法的搜索遍历图的步骤

    (1)首先找到初始节点A

    (2)依此从A未被访问的邻接点出发,对图进行深度优先遍历

    (3)若有节点未被访问,则回溯到该节点,继续进行深度优先遍历

    (4)直到所有与顶点A路径想通的节点都被访问过一次

     举个例子,在下方的无向连通图中,假设我们要从起始点A出发,使用深度优先搜索算法进行搜索,首先访问A->B->E,走不通了,回溯到A起始点,走第二个分支节点B,路径为A->C->F->H->G->D,走不通了,再回溯到起始点A,发现所有的节点都已经走过一次了,因此本次搜索结束。

     DFS的应用

    深度优先搜索算法常常被用于解决迷宫问题。

    首先我们定义一个5*5的迷宫矩阵 maze

    0 1 0 0 0
    0 1 1 1 0
    0 0 0 0 0
    0 1 1 1 0
    0 0 0 1 0

    其中0代表迷宫走可以走的路,1代表迷宫中的墙壁

    要求从左上角出发,走到左下角结束(0,0)出发,走到(4,4)

    我们使用深度优先搜索算法进行求解

    (1)从起始点(0,0)出发,第一步只能往下走(1,0),第二步走到交叉路口(2,0)

    01000
    01110
    00000
    01110
    00010

    (2)由于出口在右下角,设定优先顺序,下>右>左>上

    (3)走到(2,0)处开始往下走,直到走到(4,2)发现走不通

    01000
    01110
    00000
    01110
    00010

    (4)此时回溯到上一节点(2,0),开始沿着另一个分支进行深度优先搜索

    01000
    01110
    00000
    01110
    00010

    (5)在节点(2,4)中再次遇到分支,优先往下走,最终走到(4,4)走出迷宫

    01000
    01110
    00000
    01110
    00010

    (6)因此最终走出迷宫的路径为:

    (0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)

    (6)假设迷宫的出口在(2,0),则回溯到最近的未走过的分支顶点(2,4)往上走,最终走到终点

    01000
    01110
    00000
    01110
    00010

    代码

    def DFS(x, y):
        if x <0 or x >= len(maze) or y < 0 or y >= len(maze[0]):#走出了迷宫墙外,不合法
            return False
        if maze_visit[x][y] == True:#防止走回头
            return False
        if maze[x][y] == 1:#标记为1的不能走
            return False
        maze_visit[x][y] = True#标记本次递归路线,防止走回头
        if x == N and y == M:#走到终点停止递归
            myStack.append((x,y))
            return True
        for m in move:#四个方向尝试走
            next_x = x+m[0]
            next_y = y+m[1]
            if DFS(next_x, next_y):#判断能不能走通,能走通继续下一步递归
                myStack.append((x,y))#将走通的路径记录下来
                return True
        return False
     
    maze = [[0, 1, 0, 0, 0],
            [0, 1, 1, 1, 0],
            [0, 0, 0, 0, 0],
            [0, 1, 1, 1, 0],
            [0, 0, 0, 1, 0]]#定义迷宫
    maze_visit = [[False, False, False, False, False],
                  [False, False, False, False, False],
                  [False, False, False, False, False],
                  [False, False, False, False, False],
                  [False, False, False, False, False]]#记录路线是否已经走过,防止走反
    
    move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
    N, M = 4, 4 #定义出口的位置
    myStack = []#记录走通的路径
    DFS(0,0)#递归求解
    myStack = myStack[::-1]#反转列表
    for row in myStack:
        print('(' + str(row[0]) + ','+ str(row[1]) + ')')

    输出迷宫路线

    >>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
    >>>N, M = 4, 4 #定义出口的位置
    >>>myStack = []#记录走通的路径
    >>>DFS(0,0)#递归求解
    >>>myStack = myStack[::-1]#反转列表
    >>>for row in myStack:
    ...    print('(' + str(row[0]) + ','+ str(row[1]) + ')')
    (0,0)
    (1,0)
    (2,0)
    (2,1)
    (2,2)
    (2,3)
    (2,4)
    (3,4)
    (4,4)
    01000
    01110
    00000
    01110
    00010

    变更出口位置

    >>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
    >>>N, M = 0, 2 #定义出口的位置
    >>>myStack = []#记录走通的路径
    >>>DFS(0,0)#递归求解
    >>>myStack = myStack[::-1]#反转列表
    >>>for row in myStack:
    ...    print('(' + str(row[0]) + ','+ str(row[1]) + ')')
    (0,0)
    (1,0)
    (2,0)
    (2,1)
    (2,2)
    (2,3)
    (2,4)
    (1,4)
    (0,4)
    (0,3)
    (0,2)
    01000
    01110
    00000
    01110
    00010

    递归的回溯过程

    以入口为(0,0),出口为(0,2)为例,详细说一下递归的回溯过程

    01000
    01110
    00000
    01110
    00010

    在代码中添加增加埋点,使每次发生递归时,对参数(x,y)进行输出

    def DFS(x, y):
        print("end:", str((x, y)))
        if x <0 or x >= len(maze) or y < 0 or y >= len(maze[0]):#走出了迷宫墙外,不合法
            print("False: 走出了迷宫墙外,不合法")
            return False
        if maze_visit[x][y] == True:#防止走回头
            print("False: 往回走,不合法")
            return False
        if maze[x][y] == 1:#标记为1的不能走
            print("False: 穿墙,不合法")
            return False
        maze_visit[x][y] = True#标记本次递归路线,防止走回头
        if x == N and y == M:#走到终点停止递归
            print("True: 到达终点")
            myStack.append((x,y))
            return True
        for m in move:#四个方向尝试走
            print("strat:", str((x,y)), "move:", str(m))
            next_x = x+m[0]
            next_y = y+m[1]
            if DFS(next_x, next_y):#判断能不能走通,能走通继续下一步递归
                myStack.append((x,y))#将走通的路径记录下来
                return True
            print("回溯上一节点")
        return False

    创建好埋点后执行代码,输出如下:

    >>>maze = [[0, 1, 0, 0, 0],
    ...        [0, 1, 1, 1, 0],
    ...        [0, 0, 0, 0, 0],
    ...        [0, 1, 1, 1, 0],
    ...        [0, 0, 0, 1, 0]]#定义迷宫
    >>>maze_visit = [[False, False, False, False, False],
    ...              [False, False, False, False, False],
    ...              [False, False, False, False, False],
    ...              [False, False, False, False, False],
    ...              [False, False, False, False, False]]#记录路线是否已经走过,防止走反
    >>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
    >>>N, M = 0, 2 #定义出口的位置
    >>>myStack = []#记录走通的路径
    >>>DFS(0,0)#递归求解
    end: (0, 0)
    strat: (0, 0) move: (0, 1)
    end: (0, 1)
    False: 穿墙,不合法
    回溯上一节点
    strat: (0, 0) move: (0, -1)
    end: (0, -1)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (0, 0) move: (1, 0)
    end: (1, 0)
    strat: (1, 0) move: (0, 1)
    end: (1, 1)
    False: 穿墙,不合法
    回溯上一节点
    strat: (1, 0) move: (0, -1)
    end: (1, -1)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (1, 0) move: (1, 0)
    end: (2, 0)
    strat: (2, 0) move: (0, 1)
    end: (2, 1)
    strat: (2, 1) move: (0, 1)
    end: (2, 2)
    strat: (2, 2) move: (0, 1)
    end: (2, 3)
    strat: (2, 3) move: (0, 1)
    end: (2, 4)
    strat: (2, 4) move: (0, 1)
    end: (2, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (2, 4) move: (0, -1)
    end: (2, 3)
    False: 往回走,不合法
    回溯上一节点
    strat: (2, 4) move: (1, 0)
    end: (3, 4)
    strat: (3, 4) move: (0, 1)
    end: (3, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (3, 4) move: (0, -1)
    end: (3, 3)
    False: 穿墙,不合法
    回溯上一节点
    strat: (3, 4) move: (1, 0)
    end: (4, 4)
    strat: (4, 4) move: (0, 1)
    end: (4, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (4, 4) move: (0, -1)
    end: (4, 3)
    False: 穿墙,不合法
    回溯上一节点
    strat: (4, 4) move: (1, 0)
    end: (5, 4)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (4, 4) move: (-1, 0)
    end: (3, 4)
    False: 往回走,不合法
    回溯上一节点
    回溯上一节点
    strat: (3, 4) move: (-1, 0)
    end: (2, 4)
    False: 往回走,不合法
    回溯上一节点
    回溯上一节点
    strat: (2, 4) move: (-1, 0)
    end: (1, 4)
    strat: (1, 4) move: (0, 1)
    end: (1, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (1, 4) move: (0, -1)
    end: (1, 3)
    False: 穿墙,不合法
    回溯上一节点
    strat: (1, 4) move: (1, 0)
    end: (2, 4)
    False: 往回走,不合法
    回溯上一节点
    strat: (1, 4) move: (-1, 0)
    end: (0, 4)
    strat: (0, 4) move: (0, 1)
    end: (0, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (0, 4) move: (0, -1)
    end: (0, 3)
    strat: (0, 3) move: (0, 1)
    end: (0, 4)
    False: 往回走,不合法
    回溯上一节点
    strat: (0, 3) move: (0, -1)
    end: (0, 2)
    True: 到达终点

    接下来详细对每一步进行解析,先看方向依次为:右>左>下>上

    move = [(0,1), (0,-1), (1,0), (-1,0)]

    第一步:(0,0)往右走到(0,1)穿墙,不合法,回溯到(0,0)

    第二步:(0,0)往左走到(0,-1)走出了迷宫墙外,不合法,回溯到(0,0)

    第三步:(0,0)往下走到(1,0)合法,将(1,0)作为起点,进入DFS(1,0)

    end: (0, 0)
    strat: (0, 0) move: (0, 1)
    end: (0, 1)
    False: 穿墙,不合法
    回溯上一节点
    strat: (0, 0) move: (0, -1)
    end: (0, -1)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (0, 0) move: (1, 0)
    end: (1, 0)
    01000
    01110
    00000
    01110
    00010

    第四步:(1,0)往右走到(1,1)穿墙,不合法,回溯到(1,0)

    第五步:(1,0)往左走到(1,-1)走出了迷宫墙外,不合法,回溯到(1,0)

    第六步:(1,0)往下走到(1,0)合法,将(2,0)作为起点,进入DFS(2,0)

    strat: (1, 0) move: (0, 1)
    end: (1, 1)
    False: 穿墙,不合法
    回溯上一节点
    strat: (1, 0) move: (0, -1)
    end: (1, -1)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (1, 0) move: (1, 0)
    end: (2, 0)
    01000
    01110
    00000
    01110
    00010

    第七步:(2,0)往右走到(2,1)合法,将(2,1)作为起点,进入DFS(2,1)

    第八步:(2,1)往右走到(2,2)合法,将(2,2)作为起点,进入DFS(2,2)

    第九步:(2,2)往右走到(2,3)合法,将(2,3)作为起点,进入DFS(2,3)

    第十步:(2,3)往右走到(2,4)合法,将(2,4)作为起点,进入DFS(2,4)

    第十一步:(2,4)往右走到(2,5)走出了迷宫墙外,不合法,回溯到(2,4)

    第十二步:(2,4)往左走到(2,3)往回走,不合法,回溯到(2,4)

    第十三步:(2,4)往下走到(3,4)合法,将(3,4)作为起点,进入DFS(3,4)

    strat: (2, 0) move: (0, 1)
    end: (2, 1)
    strat: (2, 1) move: (0, 1)
    end: (2, 2)
    strat: (2, 2) move: (0, 1)
    end: (2, 3)
    strat: (2, 3) move: (0, 1)
    end: (2, 4)
    strat: (2, 4) move: (0, 1)
    end: (2, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (2, 4) move: (0, -1)
    end: (2, 3)
    False: 往回走,不合法
    回溯上一节点
    strat: (2, 4) move: (1, 0)
    end: (3, 4)
    01000
    01110
    00000
    01110
    00010

    第十四步:(3,4)往右走到(3,5)走出了迷宫墙外,不合法,回溯到(3,4)

    第十五步:(3,4)往左走到(3,3)往回走,不合法,回溯到(3,4)

    第十六步:(3,4)往下走到(4,4)合法,将(4,4)作为起点,进入DFS(4,4)

    strat: (3, 4) move: (0, 1)
    end: (3, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (3, 4) move: (0, -1)
    end: (3, 3)
    False: 穿墙,不合法
    回溯上一节点
    strat: (3, 4) move: (1, 0)
    end: (4, 4)
    01000
    01110
    00000
    01110
    00010

    第十七步:(4,4)往右走到(4,5)走出了迷宫墙外,不合法,回溯到(4,4)

    第十八步:(4,4)往左走到(4,3)穿墙,不合法,回溯到(4,4)

    第十九步:(4,4)往下走到(4,4)走出了迷宫墙外,不合法,回溯到(4,4)

    第十九步:(4,4)往上走到(3,4)往回走,不合法,回溯到(4,4)

    第二十步:此时四个方向都走不通,因此回溯到上一个交叉路口(3,4),在第十四到第十八步(3,4)节点已经往右,左,下三个方向走过一次了(move循环到了第三位),因此只剩往上走一种选择,(3,4)往上走到(2,4)往回走,不合法,回溯到(2,4)

    第二十一步:同理(2,4)在第十一到第十三步已经往右,左,下三个方向走过一次了,因此只剩往上走一种选择,(3,4)往上走到(1,4),合法,将(1,4)作为起点,进入DFS(1,4)

    strat: (4, 4) move: (0, 1)
    end: (4, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (4, 4) move: (0, -1)
    end: (4, 3)
    False: 穿墙,不合法
    回溯上一节点
    strat: (4, 4) move: (1, 0)
    end: (5, 4)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (4, 4) move: (-1, 0)
    end: (3, 4)
    False: 往回走,不合法
    回溯上一节点
    回溯上一节点
    strat: (3, 4) move: (-1, 0)
    end: (2, 4)
    False: 往回走,不合法
    回溯上一节点
    回溯上一节点
    strat: (2, 4) move: (-1, 0)
    end: (1, 4)
    01000
    01110
    00000
    01110
    00010

    从(1,4)开始到达终点的步骤再次就不进行详细解析了~~~(同理)最终到达终点(0,2)

    strat: (1, 4) move: (0, 1)
    end: (1, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (1, 4) move: (0, -1)
    end: (1, 3)
    False: 穿墙,不合法
    回溯上一节点
    strat: (1, 4) move: (1, 0)
    end: (2, 4)
    False: 往回走,不合法
    回溯上一节点
    strat: (1, 4) move: (-1, 0)
    end: (0, 4)
    ~~~~~~~~~~~~~~~~~~~~
    strat: (0, 4) move: (0, 1)
    end: (0, 5)
    False: 走出了迷宫墙外,不合法
    回溯上一节点
    strat: (0, 4) move: (0, -1)
    end: (0, 3)
    ~~~~~~~~~~~~~~~~~~~~
    strat: (0, 3) move: (0, 1)
    end: (0, 4)
    False: 往回走,不合法
    回溯上一节点
    strat: (0, 3) move: (0, -1)
    end: (0, 2)
    True: 到达终点

    !!!!!!!!!!!!!!!!!!递归结束!!!!!!!!!!!!!!!!!!!!

    使用递归求解的案例

    匈牙利算法寻找最大匹配_202xxx的博客-CSDN博客

    【牛客网华为机试】HJ28 素数伴侣_202xxx的博客-CSDN博客

    【牛客网华为机试】HJ43 迷宫问题_202xxx的博客-CSDN博客

    展开全文
  • 数据结构当中深度优先搜索算法和广度优先搜索算法的c语言算法
  • 重庆邮电大学 数学大类专业 2008 级数学建模与数学实验课程设计 设计题目 图的深度优先搜索遍历算法分析及其应用 设计时间 2010.9.72010.9. 12 设计成绩 姓名 班级 学号 指导教师 图的深度优先搜索遍历算法分析及其...
  • 针对电网故障事件等级判定需要自动识别电力故障元器件的问题,文中提出了一种基于深度优先搜索算法的电力系统拓扑建模方法。首先根据电气元件端子数建立了各元器件的数据表;然后根据各端子连接情况,构建配电网拓扑...
  • 主要介绍了Python数据结构与算法之图的广度优先与深度优先搜索算法,结合实例形式分析了图的广度优先与深度优先搜索算法原理与相关实现技巧,需要的朋友可以参考下
  • C++算法之深度优先搜索算法详解

    万次阅读 多人点赞 2018-09-28 20:23:41
    1.深度优先搜索算法  深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行...

    1.深度优先搜索算法

             深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。

    2.实现原理

            深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.

            举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束).简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort. 

                                                                  

    深度优先遍历图的方法是,从图中某顶点v出发:
    (1)访问顶点v;
    (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

    (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索(BFS).

    3.算法框架及说明

            所有的搜索算法从其最终的算法实现上来看,都可以划分成两个部分──控制结构和产生系统。正如前面所说的,搜索算法简而言之就是穷举所有可能情况并找到合适的答案,所以最基本的问题就是罗列出所有可能的情况,这其实就是一种产生式系统。我们将所要解答的问题划分成若干个阶段或者步骤,当一个阶段计算完毕,下面往往有多种可选选择,所有的选择共同组成了问题的解空间,对搜索算法而言,将所有的阶段或步骤画出来就类似是树的结构(如图)。从根开始计算,到找到位于某个节点的解,回溯法(深度优先搜索)作为最基本的搜索算法,其采用了一种“一只向下走,走不通就掉头”的思想(体会“回溯”二字),相当于采用了先根遍历的方法来构造搜索树。

    4.深度优先算法代码实现

    bool visited[MaxVnum];
    void DFS(Graph G,int v)
    {
        visited[v]= true; //从V开始访问,flag它
        printf("%d",v);    //打印出V
        for(int j=0;j<G.vexnum;j++) 
            if(G.arcs[v][j]==1&&visited[j]== false) //这里可以获得V未访问过的邻接点
                DFS(G,j); //递归调用,如果所有节点都被访问过,就回溯,而不再调用这里的DFS
    }
    
    void DFSTraverse(Graph G) {
        for (int v = 0; v < G.vexnum; v++)
            visited[v] = false; //刚开始都没有被访问过
    
        for (int v = 0; v < G.vexnum; ++v)
            if (visited[v] == false) //从没有访问过的第一个元素来遍历图
                DFS(G, v);
    }

    5.深度优先算法的应用

    (1).应用1

             基于深度优先遍历算法的应用实现.

    /*
    基于深度优先遍历算法的应用。
    假设图G采用邻接矩阵存储:
    (1)判断图G中从顶点u到v是否存在简单路径;
    (2)输出图G中从顶点u到v的一条简单路径(假设至少存在一条路径);
    (3)输出从图G中从顶点u到v的所有简单路径(假设至少存在一条路径);
    (4)输出从图G中从顶点u到v的长度为s的所有简单路径;
    (5)求图中通过某顶点k的所有简单回路(若存在)。
    */
    #include <iostream>
    #include <stdio.h>
    #include <malloc.h>
    #define MAXV 50
    using namespace std;
    int visited[MAXV];
    //邻接表类型
    typedef struct ANode
    {
        int adjvex;             //该边的编号
        struct ANode *nextarc;  //指向下一条边的信息
    } ArcNode;                  //边节点的类型
     
    typedef struct Vnode
    {
        ArcNode *firstarc;      //指向第一条边
    } VNode;                    //邻接表头节点类型
     
    typedef VNode AdjList[MAXV];
    typedef struct
    {
        AdjList adjlist;       //邻接表
        int n,e;               //图中顶点数n和边数e
    } ALGraph;                 //完整的图邻接表类型
     
    void ArrayToList(int *Arr, int n, ALGraph *&G)  //用普通数组构造图的邻接表
    {
        int i,j,count=0;  //count用于统计边数,即矩阵中非0元素个数
        ArcNode *p;
        G=(ALGraph *)malloc(sizeof(ALGraph));
        G->n=n;
        for (i=0; i<n; i++)                 //给邻接表中所有头节点的指针域置初值
            G->adjlist[i].firstarc=NULL;
        for (i=0; i<n; i++)                 //检查邻接矩阵中每个元素
            for (j=n-1; j>=0; j--)
                if (Arr[i*n+j]!=0)      //存在一条边,将Arr看作n×n的二维数组,Arr[i*n+j]即是Arr[i][j]
                {
                    p=(ArcNode *)malloc(sizeof(ArcNode));   //创建一个节点*p
                    p->adjvex=j;
                    p->nextarc=G->adjlist[i].firstarc;      //采用头插法插入*p
                    G->adjlist[i].firstarc=p;
                }
     
        G->e=count;
    }
     
    void DispAdj(ALGraph *G)   //输出邻接表G
    {
        int i;
        ArcNode *p;
        for (i=0; i<G->n; i++)
        {
            p=G->adjlist[i].firstarc;
            printf("%3d: ",i);
            while (p!=NULL)
            {
                printf("-->%d ",p->adjvex);
                p=p->nextarc;
            }
            printf("\n");
        }
    }
     
    /*
    判断图G中从顶点u到v是否存在简单路径:
    在深度优先遍历的基础上增加has和v两个形参,其中has表示顶点u到v是否有路径,其初值为false,
    当顶点u遍历到顶点v后,置has为true并返回。
    */
    void ExistPath(ALGraph *G,int u,int v,bool &has)
    {
        int w;
        ArcNode *p;
        visited[u]=1;              //置初始顶点为已访问标记
        if(u==v)                   //找到一条路径
        {
            has=true;
            return ;
        }
        p=G->adjlist[u].firstarc;  //p指向顶点u的第一个邻接点
        while(p!=NULL)
        {
            w=p->adjvex;           //w为u的相邻顶点
            if(visited[w]==0)
                ExistPath(G,w,v,has);
            p=p->nextarc;          //p指向顶点u的下一个相邻点
        }
    }
     
    /*
    输出图G中从顶点u到v的一条简单路径:
    在深度优先遍历的基础上增加v、path和d三个形参,其中path存放顶点u到v的路径,d表示path中的路径长度,初值为-1
    当顶点u遍历到顶点v后,输出path并返回。
    */
    void FindaPath(ALGraph *G,int u,int v,int path[],int d)
    {
        int w,i;
        ArcNode *p;
        visited[u]=1;              //置初始顶点为已访问标记
        d++;
        path[d]=u;                 //路径长度d增1,顶点u加入到路径中
        if(u==v)                   //找到一条路径,输出并返回
        {
            cout<<"输出从u到v的一条简单路径:";
            for(i=0; i<=d; i++)
                cout<<path[i];
            cout<<endl;
            return;
        }
        p=G->adjlist[u].firstarc;  //p指向顶点u的第一个邻接点
        while(p!=NULL)
        {
            w=p->adjvex;           //w为u的相邻顶点
            if(visited[w]==0)
                FindaPath(G,w,v,path,d);
            p=p->nextarc;          //p指向顶点u的下一个相邻点
        }
    }
     
    /*
    输出从图G中从顶点u到v的所有简单路径:
    在深度优先遍历的基础上增加v、path和d三个形参,其中path存放顶点u到v的路径,d表示path中的路径长度,初值为-1
    当从顶点u出发遍历时,先将visited[u]置为1,并将u加入到路径path中,若满足顶点u就是终点的v的条件时,
    则找到了一个从顶点u到v的一条路径,则输出path并继续;再从顶点u找一个未访问过的相邻顶点w,若存在这样的顶点w,
    则从w出发继续进行,若不存在这样的顶点w,则说明从顶点u再往下找找不到路径,所以置visited[u]为0,以便顶点u作为
    其他路径上的顶点。
    */
    void FindPath(ALGraph *G,int u,int v,int path[],int d)
    {
        int w,i;
        ArcNode *p;
        d++;
        path[d]=u;                 //路径长度d增1,顶点u加入到路径中
        visited[u]=1;              //置初始顶点为已访问标记
        if(u==v&&d>=1)                   //找到一条路径则输出
        {
            for(i=0; i<=d; i++)
                cout<<path[i];
            cout<<endl;
        }
        p=G->adjlist[u].firstarc;  //p指向顶点u的第一个邻接点
        while(p!=NULL)
        {
            w=p->adjvex;           //w为u的相邻顶点
            if(visited[w]==0)
                FindPath(G,w,v,path,d);
            p=p->nextarc;          //p指向顶点u的下一个相邻点
        }
        visited[u]=0;              //恢复环境,使该顶点可重新使用
    }
     
    /*
    输出从图G中从顶点u到v的长度为s的所有简单路径;
    只需将路径输出条件改为u==v且d==s。
    */
    void PathAll(ALGraph *G,int u,int v,int s,int path[],int d)
    {
        int w,i;
        ArcNode *p;
        visited[u]=1;
        d++;
        path[d]=u;                 //路径长度d增1,顶点u加入到路径中
        if(u==v&&d==s)                   //找到一条路径则输出
        {
            for(i=0; i<=d; i++)
                cout<<path[i];
            cout<<endl;
        }
        p=G->adjlist[u].firstarc;  //p指向顶点u的第一个邻接点
        while(p!=NULL)
        {
            w=p->adjvex;           //w为u的相邻顶点
            if(visited[w]==0)
                PathAll(G,w,v,s,path,d);
            p=p->nextarc;          //p指向顶点u的下一个相邻点
        }
        visited[u]=0;              //恢复环境,使该顶点可重新使用
    }
     
    /*
    求图中通过某顶点k的所有简单回路(若存在):
    利用深度优先搜索方法,从顶点u开始搜索与之相邻的顶点w,若w等于顶点v(其初值为u),且路径长度大于0,表示找到了一条回路,
    输出path数组,然后继续搜索顶点u的未访问的相邻点查找其它通路。
    */
    void DFSPath(ALGraph *G,int u,int v,int path[],int d)
    {
        int w,i;
        ArcNode *p;
        visited[u]=1;
        d++;
        path[d]=u;                 //路径长度d增1,顶点u加入到路径中
        p=G->adjlist[u].firstarc;  //p指向顶点u的第一个邻接点
        while(p!=NULL)
        {
            w=p->adjvex;             //w为顶点u的相邻点
            if(w==v&&d>0)                   //找到一条路径则输出
            {
                for(i=0; i<=d; i++)
                    cout<<path[i];
                cout<<v<<endl;
            }
            if(visited[w]==0)        //若w未访问,则递归访问之
                DFSPath(G,w,v,path,d);
            p=p->nextarc;          //p指向顶点u的下一个相邻点
        }
        visited[u]=0;              //恢复环境,使该顶点可重新使用
    }
     
    int main()
    {
        int i,path[MAXV];
        bool f;
        ALGraph *G,*G1,*G2;
        int A[5][5]=
        {
            {0,1,1,0,0},
            {0,0,1,0,0},
            {0,0,0,1,1},
            {0,0,0,0,1},
            {1,0,0,0,0}
        };
        int B[5][5]=
        {
            {0,1,0,1,1},
            {1,0,1,1,0},
            {0,1,0,1,1},
            {1,1,1,0,1},
            {1,0,1,1,0}
        };
        int C[5][5]=
        {
            {0,1,1,0,0},
            {0,0,1,0,0},
            {0,0,0,1,1},
            {0,0,0,0,1},
            {1,0,0,0,0}
        };
        ArrayToList(A[0], 5, G);
        ArrayToList(B[0], 5, G1);
        ArrayToList(C[0], 5, G2);
        for (i=0; i<G->n; i++)
            visited[i]=0; //访问标志数组初始化
        printf("有向图G的邻接表:\n");
        DispAdj(G);
        cout<<endl;
        for (i=0; i<G->n; i++)
            visited[i]=0; //访问标志数组初始化
        ExistPath(G,1,4,f);
        cout<<"是否存在一条u到v的路径?";
        if(f)
            cout<<"存在"<<endl;
        else
            cout<<"不存在"<<endl;
        for (i=0; i<G->n; i++)
            visited[i]=0; //访问标志数组初始化
        cout<<endl;
        FindaPath(G,1,4,path,-1);
        cout<<endl;
        for (i=0; i<G1->n; i++)
            visited[i]=0; //访问标志数组初始化
        printf("无向图G1的邻接表:\n");
        DispAdj(G1);
        cout<<endl;
        for (i=0; i<G1->n; i++)
            visited[i]=0; //访问标志数组初始化
        printf("输出G1从1到4的所有简单路径:\n");
        FindPath(G1,1,4,path,-1);
        cout<<endl;
        for (i=0; i<G1->n; i++)
            visited[i]=0; //访问标志数组初始化
        cout<<"输出从图G中从顶点u到v的长度为s的所有简单路径:\n";
        PathAll(G1,1,4,3,path,-1);
        cout<<endl;
        for (i=0; i<G1->n; i++)
            visited[i]=0; //访问标志数组初始化
        printf("有向图G2的邻接表:\n");
        DispAdj(G2);
        cout<<endl;
        for (i=0; i<G1->n; i++)
            visited[i]=0; //访问标志数组初始化
        cout<<"经过顶点k的所有回路:\n";
        DFSPath(G2,0,0,path,-1);
        cout<<endl;
        return 0;
    }

    程序执行输出:

    展开全文
  • 深度优先搜索算法(DFS,Depth-First-Search),是搜索算法的一种。 基本思想:沿着树的深度来遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这...

    彻底搞懂DFS算法法(JAVA版本)

    深度优先搜索算法(DFS,Depth-First-Search),是搜索算法的一种。

    基本思想:沿着树的深度来遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。


    深度优先搜索算法也是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最长路径、最短路径问题等等。
    因发明“深度优先搜索算法”,霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖:图灵奖.

    DFS适合此类题目:给定初始状态跟目标状态,要求判断从初始状态到目标状态是否有解。

    例如:利用DFS算法进行无向图的遍历问题
    假设初始状态是图中所有顶点都未被访问,则深度优先搜索方法的步骤是:
    1)选取图中某一顶点Vi为出发点,访问并标记该顶点;
    2)以Vi为当前顶点,依次搜索Vi的每个邻接点Vj,若Vj未被访问过,则访问和标记邻接点Vj,若Vj已被访问过,则搜索Vi的下一个邻接点;
    3)以Vj为当前顶点,重复步骤2),直到图中和Vi有路径相通的顶点都被访问为止;
    4)若图中尚有顶点未被访问过(非连通的情况下),则可任取图中的一个未被访问的顶点作为出发点,重复上述过程,直至图中所有顶点都被访问。

    例1. 无向图的DFS访问

    例如,在下图中,我们从顶点2开始遍历。当我们到达顶点0时,我们寻找它的所有相邻顶点。2也是0的相邻顶点。如果我们不标记访问过的顶点,那么2将再次被处理,它将成为一个非终止过程。下图的深度优先遍历是2、0、1、3。

     


     算法分析

    上图有4个结点(顶点):0,1,2,3

    边的数量:6

    边的表示:(0,1)(0,2)(1,2)(2,0)(2,3)(3,3)

    如果我们想构造出这个图,可以采用邻接表表示。定义一个类 DFSGraph类来表示这个无向图(DFSGraph.java)

    定义DFSGraph类

    public class DFSGraph{
    
     //此处补充代码
    }

    首先声明结点(顶点)和图的邻接表。邻接表采用JAVA中的LinkedList类的对象来表示。这里为什么选择LinkedList类呢?

    补充一点点JAVA的基础知识吧!如下图所示:

    • List 是一个接口,它继承于Collection的接口。它代表着有序的队列。
    • AbstractList 是一个抽象类,它继承自AbstractCollection抽象类。AbstractList实现List接口中除size()、get(int location)之外的方法。
    • AbstractSequentialList 是一个抽象类,它继承自AbstractList抽象类。AbstractSequentialList 实现了“链表中,根据index索引值操作链表的全部方法”。
    • ArrayList, LinkedList, Vector, Stack是List接口的4个实现类。

    其中各自的特点:

    • ArrayList 是一个数组队列,相当于动态数组。它由数组实现,随机访问效率高,随机插入、随机删除效率低。
    • LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低,但随机插入、随机删除效率高。
    • Vector 是矢量队列,和ArrayList一样,它也是一个动态数组,由数组实现。但是ArrayList是非线程安全的,而Vector是线程安全的。
    • Stack 是栈,它继承于Vector。它的特性是:先进后出(FILO, First In Last Out)。

    好了,言归正传,我们使用LinkedList类的对象来定义图的邻接表,用 adj[]数组表示。 

    public class DFSGraph{
    
        private int V; // 定义结点(vertices)
    
        // 图的邻接表表示( Adjacency List)
        private LinkedList<Integer> adj[];
    
        //此处补充代码
    
    }}

    创建构造方法

    adj数组的长度为顶点数,而adj数组的每一个数组元素其实都是一个LinkedList类型的对象。

    public class DFSGraph {
    	
    	private int V; // 定义结点(vertices)
    
    	// 图的邻接表表示( Adjacency List)
    	private LinkedList<Integer> adj[];
    
    	// 构造图的构造方法
    	DFSGraph(int v) {
    		V = v;
    		adj = new LinkedList[v];
    		for (int i = 0; i < v; ++i)
    			adj[i] = new LinkedList();
    	}
    
        // 此处补充代码
    
    }

    向图中添加边

    public class DFSGraph {
    	
    	private int V; // 定义结点(vertices)
    
    	// 图的邻接表表示( Adjacency List)
    	private LinkedList<Integer> adj[];
    
    	// 构造图的构造方法
    	DFSGraph(int v) {
    		V = v;
    		adj = new LinkedList[v];
    		for (int i = 0; i < v; ++i)
    			adj[i] = new LinkedList();
    	}
    
        // 向图中添加边
    	void addEdge(int v, int w) {
    		adj[v].add(w); 
    	}
    
        // 此处补充代码
    
    }

    DFS算法设计

        // DFS traversal. 用来回溯调用 DFSUtil()工具
    	void DFS(int v) {
    		// 标记所有节点为未访问状态( not visited),设置初始值为false。
    		boolean visited[] = new boolean[V];
    
    		// 回溯 DFS traversal
    		DFSUtil(v, visited);
    	}

    具体访问过程通过DFSUtil方法来实现

        // DFS算法工具
    	void DFSUtil(int v, boolean visited[]) {
    		// 标记当前结点为已访问(visited)并输出
    		visited[v] = true;
    		System.out.print(v + " ");
    
    		// 访问当前的结点的所有邻接结点
    		Iterator<Integer> i = adj[v].listIterator();
    		while (i.hasNext()) {
    			int n = i.next();
    			if (!visited[n])
    				DFSUtil(n, visited);
    		}
    	}

    完整代码

     下面是完成的代码

    package com.bean.algorithm.graph;
    
    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class DFSGraph {
    	
    	private int V; // 定义结点(vertices)
    
    	// 图的邻接表表示( Adjacency List)
    	private LinkedList<Integer> adj[];
    
    	// 构造图的构造方法
    	DFSGraph(int v) {
    		V = v;
    		adj = new LinkedList[v];
    		for (int i = 0; i < v; ++i)
    			adj[i] = new LinkedList();
    	}
    
    	// 向图中添加边
    	void addEdge(int v, int w) {
    		adj[v].add(w); 
    	}
    
    	// DFS算法工具
    	void DFSUtil(int v, boolean visited[]) {
    		// 标记当前结点为已访问(visited)并输出
    		visited[v] = true;
    		System.out.print(v + " ");
    
    		// 访问当前的结点的所有邻接结点
    		Iterator<Integer> i = adj[v].listIterator();
    		while (i.hasNext()) {
    			int n = i.next();
    			if (!visited[n])
    				DFSUtil(n, visited);
    		}
    	}
    
    	// DFS traversal. 用来回溯调用 DFSUtil()工具
    	void DFS(int v) {
    		// 标记所有节点为未访问状态( not visited),设置初始值为false。
    		boolean visited[] = new boolean[V];
    
    		// 回溯 DFS traversal
    		DFSUtil(v, visited);
    	}
    
    	public static void main(String args[]) {
    		DFSGraph g = new DFSGraph(4);
    
    		g.addEdge(0, 1);
    		g.addEdge(0, 2);
    		g.addEdge(1, 2);
    		g.addEdge(2, 0);
    		g.addEdge(2, 3);
    		g.addEdge(3, 3);
    
    		System.out.println("下面是DFS搜索结果 " + "(从2号结点开始)");
    
    		g.DFS(2);
    	}
    }
    

    程序运行结果:

    下面是DFS搜索结果 (从2号结点开始)
    2 0 1 3 


    未完,持续更新中....

    展开全文
  • 本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法。分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从...
  • 实现有向图的深度优先搜索算法 ...实现有向图的深度优先搜索算法实现有向图的深度优先搜索算法实现有向图的深度优先搜索算法实现有向图的深度优先搜索算法 实现有向图的深度优先搜索算法实现有向图的深度优先搜索算法
  • 深度优先搜索算法C++实现

    热门讨论 2009-05-24 10:40:37
    用C++编写的利用有界深度优先搜索算法解决8数码问题
  • 全部功能采用Matlab编写,程序的功能是寻找从出发点到目的地的全部可行路径,最后只显示了最佳和最劣路径的动画效果,对每一步的移动进行了动画演示。
  • DFS(深度优先搜索算法)

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

    基本概念

    深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

    算法思想

    回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。 

     

    基本模板

    int check(参数)
    {
        if(满足条件)
            return 1;
        return 0;
    }
    
    void dfs(int step)
    {
            判断边界
            {
                相应操作
            }
            尝试每一种可能
            {
                   满足check条件
                   标记
                   继续下一步dfs(step+1)
                   恢复初始状态(回溯的时候要用到)
            }
    }   

    问题示例

    1、全排列问题

    //全排列问题
    #include<stdio.h>
    #include<string.h>
    
    int n;
    char  a[15];
    char re[15];
    int vis[15];
    //假设有n个字符要排列,把他们依次放到n个箱子中
    //先要检查箱子是否为空,手中还有什么字符,把他们放进并标记。
    //放完一次要恢复初始状态,当到n+1个箱子时,一次排列已经结束
    void dfs(int step)
    {
        int i;
        if(step==n+1)//判断边界
        {
            for(i=1;i<=n;i++)
                printf("%c",re[i]);
            printf("\n");
            return ;
        }
        for(i=1;i<=n;i++)//遍历每一种情况
        {
            if(vis[i]==0)//check满足
            {
                re[step]=a[i];
                vis[i]=1;//标记
                dfs(step+1);//继续搜索
                vis[i]=0;//恢复初始状态
            }
        }
        return ;
    }
    
    int main(void)
    {
        int T;
        scanf("%d",&T);
        getchar();
        while(T--)
        {
            memset(a,0,sizeof(a));
            memset(vis,0,sizeof(vis));//对存数据的数组分别初始化
            scanf("%s",a+1);
            n=strlen(a+1);
            dfs(1);//从第一个箱子开始
        }
        return 0;
    }

    2、一个环由个圈组成,把自然数1,2,…,N分别放在每一个圆内,数字的在两个相邻圈之和应该是一个素数。 注意:第一圈数应始终为1。

    input: N(0~20)

    output:输出格式如下所示的样品。每一行表示在环中的一系列圆号码从1开始顺时针和按逆时针方向。编号的顺序必须满足上述要求。打印解决方案的字典顺序。

    //Prime Ring Problem
    //与上面的全排列问题其实思路差不多,只是需要判断的条件比较多
    //化大为小
    
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    int book[25];
    int result[25];
    int n;
    int num;
    //判断是否为素数
    int prime(int n)
    {
        if(n<=1)
            return 0;
        int i;
        for(i=2;i*i<=n;i++)
        {
            if(n%i==0)
                break;
        }
        if(i*i>n)
            return 1;
        return 0;
    }
    //判断是否能将当前的数字放到当前的圈内
    int check(int i,int step)
    {
        if((book[i]==0) && prime(i+result[step-1])==1)
        {
            if(step==n-1)
            {
                if(!prime(i+result[0]))
                    return 0;
            }
            return 1;
        }
        return 0;
    }
    
    void dfs(int step)
    {
        if(step==n)//判断边界
        {
            int a;
            printf("%d",result[0]);
            for(a=1;a<n;a++)
            {
                printf(" %d",result[a]);
            }
            printf("\n");
            return ;
        }
        int i;
        for(i=2;i<=n;i++)//遍历每一种情况
        {
            if(check(i,step))//check是否满足
            {
                book[i]=1;//标记
                result[step]=i;//记录结果
                dfs(step+1);//继续往下搜索
                book[i]=0;//恢复初始状态
            }
        }
    }
    
    int main(void)
    {
    
        while(scanf("%d",&n)!=EOF)
        {
            num++;
            memset(result,0,sizeof(result));
            memset(book,0,sizeof(book));
            result[0]=1;
            printf("Case %d:\n",num);//格式比较容易出错
            dfs(1);
            printf("\n");
        }
        return 0;
    }
    

    3、油田问题

    问题:GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油,并把这个大区域分成了很多小块。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。

    input: 输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,

    1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是’*’,代表没有油,要么是’@’,表示有油。

    output: 对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。

    //A - Oil Deposits 
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    char a[105][105];
    int n,m,result;
    int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};//表示8个方向
    
    int check(int x,int y)//检查是否有油田
    {
        if(x>=0&&x<m&&y>=0&&y<n&&a[x][y]=='@')
            return 1;
        return 0;
    }
    
    int dfs(int x, int y)
    {
        int i,xx,yy;
        if(check(x,y))
        {
            a[x][y]='.'; //统计之后就可以把该油田标记,且不用恢复(要不会重复),
                        //也可以用一个数组来存每个点的访问情况,但是感觉没必要,浪费空间
            for(i=0;i<8;i++)
            {
                xx=x+dir[i][0];
                yy=y+dir[i][1];
                dfs(xx,yy);//依次检查8个方向
            }
            return 1;
        }
        return 0;
    }
    
    int main(void)
    {
        int i,j;
        while(scanf("%d %d",&m,&n)==2)
        {
            if(m==0&&n==0)
                break;
            result = 0;
            memset(a,0,sizeof(a));
            for(i=0;i<m;i++)
                scanf("%s",a[i]);
            for(i=0;i<m;i++)//在每一个点都搜索一次
            {
                for(j=0;j<n;j++)
                {
                    if(dfs(i,j))//找到油田就可以将结果加1
                        result++;
                }
            }
            printf("%d\n",result);
        }
        return 0;
    }

    4、棋盘问题

    问题:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

    input: 输入含有多组测试数据。 每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

    output:对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    int n, k, ans;
    char str[10][10];
    int vis[100];
    
    void dfs(int r, int k)
    {
        if(k==0)//判断边界,此时棋子已经放完
        {
            ans++;
            return;
        }
    
        for(int i=r; i<n; i++)//每次都从放过棋子下一行开始搜索,保证不重复
        {
            for(int j=0; j<n; j++)
            {
                //循环保证行不重复,check保证列不重复
                if(str[i][j]=='.' || vis[j]==1)
                    continue;//不满足条件直接跳过
                vis[j] = 1;//标记
                dfs(i+1, k-1);//继续下一次标记
                vis[j] = 0;//恢复初始状态
            }
        }
    }
    
    int main(void)
    {
        while(1)
        {
            scanf("%d %d", &n, &k);
            getchar();
            if(n==-1 && k==-1) 
                break;
            memset(str, '\0', sizeof(str));
            memset(vis, 0, sizeof(vis));
            ans = 0;
    
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<n; j++)
                    str[i][j] = getchar();
                getchar();
            }
    
            dfs(0, k);//从第0行开始放,此时手中还剩k个棋子
            printf("%d\n", ans);
        }
        return 0;
    }
    

    参考文章

    https://blog.csdn.net/ldx19980108/article/details/76324307#commentBox

    https://blog.csdn.net/qq_42815188/article/details/89258074

    https://www.jianshu.com/p/5cda08b4b391

    展开全文
  • DFS(深度优先搜索算法)——Java实现

    千次阅读 2020-03-14 19:32:58
    深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到...
  • 事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. 举例说明之:下图是一个无向图,如果我们从A...
  • 人工智能学习:python实现深度优先搜索算法本文博客链接:http://blog.csdn.net/jdh99,作者:jdh,转载请注明. 环境:主机:WIN10python版本:3.5开发环境:pyCharm说明:深度优先搜索原理和伪代码: 算法流程分析:数据...
  • 深度优先搜索算法 深度优先搜索算法(Depth-First-Search,简称DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v...
  • 深度优先搜索算法(java语言)

    千次阅读 2017-12-24 15:31:47
    我们在学习了图之后,需要一种机制来遍历图,图的遍历算法也叫图搜索算法。与树的遍历算法(中序、前序、... (1)深度优先搜索(DFS)。  (2)广度优先搜索(BFS)。 一、深度优先搜索  例子如下图所示:  

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,923
精华内容 25,969
关键字:

深度优先搜索算法