Моя DFS не может обрабатывать простой граф [Python] - PullRequest
Новая
       21

Моя DFS не может обрабатывать простой граф [Python]

0 голосов
/ 22 марта 2019

Ниже приведен мой код для 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)

1 Ответ

0 голосов
/ 22 марта 2019

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

С другой стороны, еслиэто ориентированные графы, тогда ваш пример имеет смысл (интерпретируя значения как соответствующие исходящим ребрам, а ключи - узлам, которые имеют исходящие ребра).Но в этом случае вам не удается обработать терминальные узлы.Вы можете либо явно проверить, находится ли узел в словаре перед его повторением, либо обработать список непосредственно доступных узлов для терминальных узлов как неявно [] и использовать метод словаря 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'].

...