深度优先搜索算法,图的深度优先搜索

发布时间:2024年01月04日

深度优先搜索,其核心思想就是以一个点作为搜索的起始点,沿着这个点的分支路径不断地深入,直到没有满足条件的点则退回,并以新的起始点为搜索的点,重复以上的过程,图的遍历就是以深度优先搜索思想为解决问题的核心思想。

而对于图的实现方式有两种,一种就是使用递归的方式,递归的过程可以将问题变得简单,但是同时带来了负面影响,就是当数据量较大的时候,会出现运行时间过长,耗时严重。而另一个实现的方式就是非递归的方式,如果在对解决问题的过程中有着高效率的需求的时候,就需要使用到非递归的方式,而且是借助于堆栈的结构来实现这一方式。

对于图这一结构的深度优先搜索的方式,可以从以下这个例子来表明:

添加图片注释,不超过 140 字(可选)

对于如上这个图需要进行深度优先遍历,从而得到返回值。

添加图片注释,不超过 140 字(可选)

添加图片注释,不超过 140 字(可选)

图的深度优先遍历实现的方式如下:


class graph: 
def __init__(self,point,graph):
    self.graph = graph 
    self.point = point 
    self.sum =0 
    self.visit = [0 for j in range(len(graph))] 

def dfs(self,n): 
    self.visit[n]=1 print(self.point[n]) 
    self.sum +=1 
    if self.sum == len(self.visited):
        return 
    for i in range(len(self.graph): 
        if self.graph[n][i]==1 and self.visited[i]==0: 
            self.dfs[i]

这里使用的是递归的方式来实现的。

文章来源:https://blog.csdn.net/Mrsawyer/article/details/135396284
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。