c语言深度优先搜索 (Depth-First Search,DFS)

发布时间:2023年12月26日

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

以下是一个简单的深度优先搜索的Python代码示例和注释:

# 建立一个字典来表示图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

visited = set() # 准备一个集合用来存储已经访问过的节点

def dfs(visited, graph, node): # 定义深度优先搜索函数
    if node not in visited: # 如果节点没有被访问过
        print (node) # 打印节点
        visited.add(node) # 把节点添加到已访问集合中
        for neighbour in graph[node]: # 对于节点的每一个邻居
            dfs(visited, graph, neighbour) # 递归调用深度优先搜索函数

# 从节点'A'开始
dfs(visited, graph, 'A')
  1. 首先我们定义了一个图,这个图包含了一些节点和它们的邻居。
  2. 我们创建了一个名为visited的集合,用来保存已经访问过的节点。
  3. 函数dfs()是我们的深度优先搜索函数,它接受三个参数:一个已访问节点集合,一个图以及一个当前节点。
  4. 在函数内部,首先检查当前节点是否已经被访问过。如果没有,就打印这个节点并把它添加到已访问节点的集合中。
  5. 然后,对于当前节点的每一个邻居,我们递归地调用深度优先搜索函数。这就是深度优先搜索:我们首先访问一个节点的一个邻居,然后再访问那个邻居的邻居,以此类推,直到找不到未被访问的邻居为止,然后再回溯到上一个节点,继续访问其他的邻居。

以上就是深度优先搜索的一种简单实现方法和它的基本思想。在实际应用中,深度优先搜索可能会更复杂,并且可能需要处理一些特殊情况,例如环路、权重等等。

文章来源:https://blog.csdn.net/weixin_44738632/article/details/135219350
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。