时间戳

首页 > 解决方案 > 如何创建一个执行深度优先搜索的函数，该搜索在找到给定顶点时停止？

python - 如何创建一个执行深度优先搜索的函数，该搜索在找到给定顶点时停止？

问题描述

嗨，我是 python 新手，我正在努力解决我们在活动中所做的事情。我不太明白如何完成此代码，以便它可以执行深度优先搜索，该搜索在找到给定顶点时停止。

graph = {'0': ['1', '2'],
         '1': ['0', '3', '4'],
         '2': ['0', '4'],
         '3': ['1', '4'],
         '4': ['1', '2', '3', '5'],
         '5': ['4', '6'],
         '6': ['5']}



def dfs(visited, graph, vertex):
        print (vertex)
        visited.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                dfs(visited, graph, neighbour)
            
# implement this function
def dfs_stop(visited, graph, vertex, target):
    pass

dfs([], graph, '0')

print

dfs_stop([], graph, '0', '4')

标签： python

解决方案

在调用其邻居的 DFS 之前，您只需要添加一个检查源节点是否等于目标节点。

def dfs_stop(visited, graph, vertex, target):
        print (vertex)
        visited.append(vertex)
        if (vertex == target):        # to break/stop the function
            return
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                dfs_stop(visited, graph, neighbour)

推荐阅读