| DFS算法概念原理详细图解 Python代码实现DFS算法 | 您所在的位置：网站首页 › dfs算法讲解 › DFS算法概念原理详细图解 Python代码实现DFS算法 |
DFS算法概念原理详细图解 Python代码实现DFS算法
|
DFS算法又名深度优先搜索，作为递归算法，通过堆栈，在避免循环的同时遍历目标所有节点。 DFS算法的工作原理图解以具有5个节点的无向图为例，如下图：  从节点0开始，DFS算法首先将其放入Visited列表并将其所有相邻顶点放入堆栈。  接着，访问堆栈顶部的节点1，并转到其相邻节点。因为0已经被访问过，所以访问2。  节点2有一个未访问的相邻节点4，因此我们将其添加到堆栈顶部并访问它。  现在，还有最后一个节点没有访问，我们继续往下。在最后访问3之后，已经没有还未访问的相邻节点，因此我们完成了该无向图的深度优先遍历。  DFS算法伪代码在init()函数中，请注意我们在每个节点上运行DFS函数。这是因为图可能有两个不同的不连贯部分，因此为了确保覆盖每个顶点，我们还可以在每个节点上运行DFS算法。 DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v)init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}Python代码实现DFS算法def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start)print(start) for next in graph[start] - visited: dfs(graph, next, visited) return visited graph = {'0': set(['1', '2']), '1': set(['0', '3', '4']), '2': set(['0']), '3': set(['1']), '4': set(['2', '3'])} dfs(graph, '0') |
【本文地址】
公司简介
联系我们