深度优先搜索,其核心思想就是以一个点作为搜索的起始点,沿着这个点的分支路径不断地深入,直到没有满足条件的点则退回,并以新的起始点为搜索的点,重复以上的过程,图的遍历就是以深度优先搜索思想为解决问题的核心思想。
而对于图的实现方式有两种,一种就是使用递归的方式,递归的过程可以将问题变得简单,但是同时带来了负面影响,就是当数据量较大的时候,会出现运行时间过长,耗时严重。而另一个实现的方式就是非递归的方式,如果在对解决问题的过程中有着高效率的需求的时候,就需要使用到非递归的方式,而且是借助于堆栈的结构来实现这一方式。
对于图这一结构的深度优先搜索的方式,可以从以下这个例子来表明:
添加图片注释,不超过 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]
这里使用的是递归的方式来实现的。