Глубина первого поиска текущей проблемы реализации, когда я пытаюсь запустить его - PullRequest
Новая
       38

Глубина первого поиска текущей проблемы реализации, когда я пытаюсь запустить его

0 голосов
/ 07 января 2019

Я пытаюсь поделиться своей реализацией углубленного первого поиска (DFS). Я пытаюсь понять, как он может проходить по неориентированному графу, а это означает, что не все узлы превращаются в один граф, а два разных. Я искал небольшие основы DFS только с одним графиком. И я столкнулся с проблемой в «что произойдет, если существует более одного графа и он не подключен?» Поэтому я начал искать способ сделать это, используя свои знания из простой реализации DFS , Однако это немного сложнее, чем я думал. Вот пример кода, с которым я столкнулся: 

"""DFS implemention."""

    adjacency_matrix = {
                        1: [2, 3],
                        2: [4, 5],
                        3: [5],
                        4: [6],
                        5: [6],
                        6: [7],
                        7: [],
                        8: [9],
                        9: [8]
                        }

        def DFS_un(graph):
        """Traversal for undirected graphs."""
            vertices = graph[0]
            edges = graph[1]

        def visit(vertex):
            if vertex in visited:
                return
            visited.add(vertex)
            print(vertex)
            if vertex in edges:
                for e in edges[vertex]:
                    visit(e)
        visited = {}
        for v in vertices:
            visit(v)

    if __name__ == '__main__':
        DFS_un(adjacency_matrix)

И сообщение об ошибке гласит: 

Traceback (most recent call last):
  File "dfs.py", line 33, in <module>
    DFS_dis(adjacency_matrix)
  File "dfs.py", line 17, in DFS_dis
    vertices = graph[0]
KeyError: 0

Если вы видите, я использую один график, но он имеет неориентированные числа, которые составляют 8 и 9 (8 <-> 9). Почему я не получаю вывод правильно? Извините, я тоже немного изучаю Python3 :). Спасибо за вашу помощь!

Ответы [ 2 ]

0 голосов
/ 07 января 2019

Я уже нашел свою проблему. @blueenvelope был прав с идеей словаря, потому что здесь не используются ключевые слова, и поэтому по какой-то причине он дает мне 0 ... В конце концов, он, наконец, читает весь список графиков из не связанных вершин.

Мои переменные vertices и edges были неправильно реализованы и быстро поняли их назначение. Ключи используется для поиска определенных словарей, поэтому я извлекал ключи из вершины графа. То же самое касается моих ребер, но также извлекает значения этих ребер из определенного ключа. Вот полный фиксированный код: 

adjacency_matrix = {
                    1: [2, 3],
                    2: [4, 5],
                    3: [5],
                    4: [6],
                    5: [6],
                    6: [7],
                    7: [],
                    8: [9],
                    9: [8]
                    }

def DFS_un(graph):
    """Traversal for undirected graphs."""
    vertices = graph.keys()
    edges = graph.values()
    visited = []

    def visit(vertex):
        if vertex in visited:
            return
        print("Visited vertex: ")
        visited.append(vertex)
        print(visited)
        print("Current vertex: ")
        print(vertex)
        print("\n")
        if vertex in edges:
            for e in edges[vertex]:
                visit(e)
    for v in vertices:
        visit(v)

if __name__ == '__main__':
    DFS_un(adjacency_matrix)
0 голосов
/ 07 января 2019

Вы хотите: 

vertices = graph.keys()
edges = graph.values()

«График» - объект словаря. Запись графа [0] гласит: найдите мне значение, связанное с ключом = 0. Поскольку у вас нет ключа = 0, вы получите ошибку.

Возможно, вы путаете словари со списками. my_list [0] говорит, что получите значение 0 в my_list.

...