Блог

Главная - Вопросы по программированию - Как я могу создать функцию, которая выполняет поиск в глубину, который останавливается, когда находит заданную вершину?

Как я могу создать функцию, которая выполняет поиск в глубину, который останавливается, когда находит заданную вершину?

#python

#python

Вопрос:

Привет, я новичок в python, и я борюсь с тем, что мы делаем в activity. Я не совсем понимаю, как закончить этот код, чтобы он мог выполнять поиск в глубину, который останавливается, когда находит заданную вершину.

 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')

Комментарии:

1. как насчет простой проверки этого vertex == target ?

2. Почему вы используете 2 функции для 1 DFS?

3. Мне нужно реализовать приведенный ниже код, но я не знаю, как это сделать.

Ответ №1:

Вам просто нужно добавить проверку, равен ли исходный узел целевому узлу, прежде чем вызывать 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)