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

Question

Я здесь пытаюсь поделиться своей реализацией углубленного первого поиска (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:). Спасибо за вашу помощь!

Answer 1

Ты хочешь:

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

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

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

Answer 2

Я уже нашел свою проблему. @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)