DFS算法(python) 🐍 python dfs
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()`函数,对每个节点进行深度优先搜索。
免责声明:本答案或内容为用户上传,不代表本网观点。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。 如遇侵权请及时联系本站删除。