首页 > 快讯 > 系统 >

DFS算法(python) 🐍 python dfs

发布时间:2025-02-28 16:25:23来源:

DFS(Depth-First Search)算法是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

下面是在Python中实现DFS算法的一个例子:

```python

定义一个类表示图

class Graph:

def __init__(self):

self.graph = {}

添加边

def add_edge(self, u, v):

if u not in self.graph:

self.graph[u] = []

self.graph[u].append(v)

深度优先搜索

def dfs(self, start):

visited = set()

self._dfs(start, visited)

def _dfs(self, node, visited):

if node not in visited:

print(node)

visited.add(node)

for neighbour in self.graph[node]:

self._dfs(neighbour, visited)

g = Graph()

g.add_edge('A', 'B')

g.add_edge('A', 'C')

g.add_edge('B', 'D')

g.add_edge('B', 'E')

g.dfs('A')

```

上述代码定义了一个`Graph`类,用于创建图,并添加边。`dfs()`函数实现了深度优先搜索算法。首先初始化一个空集合,然后调用内部的`_dfs()`函数,对每个节点进行深度优先搜索。

免责声明:本答案或内容为用户上传,不代表本网观点。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。 如遇侵权请及时联系本站删除。