深度优先搜索(DFS
时间: 2023-12-07 07:38:40 浏览: 34
深度优先搜索(DFS)是一种在图或树中遍历所有节点的算法。其基本思想是从起点开始,沿着一条路径一直走到底,直到无法继续为止,然后回溯到上一个节点,再沿着另一条路径继续走到底,直到所有节点都被访问过为止。DFS使用栈(递归)来存储待处理节点,每个节点仅被访问一次。处理一个节点时,先访问它的一个未被访问的相邻节点,若不存在这样的节点则回溯到上一层节点。DFS算法复杂度为O(V+E),V为节点数,E为边数。
以下是一个Python实现的DFS算法的例子:
```python
# 定义一个图的类
class Graph:
def __init__(self, graph_dict=None):
if graph_dict is None:
graph_dict = {}
self.__graph_dict = graph_dict
# 添加节点
def add_node(self, node):
if node not in self.__graph_dict:
self.__graph_dict[node] = []
# 添加边
def add_edge(self, edge):
edge = set(edge)
(node1, node2) = tuple(edge)
if node1 in self.__graph_dict:
self.__graph_dict[node1].append(node2)
else:
self.__graph_dict[node1] = [node2]
# 获取所有节点
def get_nodes(self):
return list(self.__graph_dict.keys())
# 获取所有边
def get_edges(self):
edges = []
for node in self.__graph_dict:
for neighbour in self.__graph_dict[node]:
if {neighbour, node} not in edges:
edges.append({node, neighbour})
return edges
# 定义DFS算法
def dfs(self, start_node):
visited = set()
self.__dfs(start_node, visited)
def __dfs(self, node, visited):
visited.add(node)
print(node, end=' ')
for neighbour in self.__graph_dict[node]:
if neighbour not in visited:
self.__dfs(neighbour, visited)
```