Блог

Ниже приведен мой код для DFS [Поиск в глубину], и мой код мог обрабатывать сложный график, но не смог обработать простой график, подобный приведенному мной, поэтому мой вопрос в том, как с этим справиться? Я делаю это рекурсивно. Приветствуется любая помощь.

 graph = { 'A' : ['B','S']}

def dfs(graph,start_node,visited):
    if start_node:
        if start_node not in visited:
            visited.append(start_node)
            for node in graph[start_node]:
                  dfs(graph,node,visited)
    else:
        return visited
    return visited

visited=dfs(graph,"A",[])
print(visited)
  

Как вы представляете графики? Если это стандартный граф (с двухсторонними ребрами), представленный в виде словаря, управляемого узлами, в котором значения представляют собой списки смежных узлов, то ваш «график» вообще не является графиком, поскольку в нем отсутствуют списки ребер для 'B' и 'S' . Но тогда почему вы используете его в качестве тестового примера? Единственный актуальный вопрос для такого ввода — хотите ли вы проверить, корректно ли выполняется сбой вашего кода на них (ваш — нет, но правильная обработка ошибок имеет непосредственное отношение к вашему вопросу).).

С другой стороны, если это направленные графики, то ваш пример имеет смысл (интерпретация значений как соответствующих исходящим ребрам, а ключи — это узлы, которые имеют исходящие ребра). Но в этом случае вам не удается обработать терминальные узлы. Вы можете либо явно проверить, есть ли узел в словаре, прежде чем выполнять рекурсию по нему, либо обработать список непосредственно достижимых узлов для конечных узлов как неявный [] и использовать метод dictionary get() , чтобы вернуть его в этих случаях:

 def dfs(graph,start_node,visited):
    if start_node:
        if start_node not in visited:
            visited.append(start_node)
            for node in graph.get(start_node,[]):
                  dfs(graph,node,visited)
    else:
        return visited
    return visited
  

Это будет работать как ожидалось, при печати ['A', 'B', 'S'] .