Алгоритм обхода графа в глубину
""" ****** Стандартный алгоритм обхода графа в глубину. **** 1. Начните с размещения любой вершины графа на вершине стека. 2. Возьмите верхний элемент стека и добавьте его в список посещенных. 3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в начало стека. 4. Продолжайте повторять шаги 2 и 3, пока стек не станет пустым. """ # Граф родители => потомки graph = {'A' : ['B','C'], 'B' : ['D', 'E'], 'C' : ['F'], 'D' : [], 'E' : ['F'], 'F' : [] } def dfs(graph, start, visited=[]): if start not in visited: visited.append(start) for neighbour in graph[start]: dfs(graph, neighbour, visited) print(dfs(graph, 'A'))
""" Возможно ли попасть из вершины X в вершину Y Или проверка является ли вершина X родителем Y """ # Граф родители => потомки graph = {'A' : ['B','C'], 'B' : ['D', 'E'], 'C' : ['F'], 'D' : [], 'E' : ['F'], 'F' : [] } def dfs_parent_child(graph, start, stop, visited=[]): if start not in visited: visited.append(start) for neigbor in graph[start]: dfs_parent_child(graph, neigbor, stop, visited) if stop in visited: return True return False print(dfs_parent_child(graph, 'A', 'D'))
""" Возможно ли попасть из вершины X в вершину Y Или проверка является ли вершина X родителем Y True - если класс 1 является предком(родитель) класса 2, A D """ # Граф потомки => родители (дети: родители) graph = { 'A': [], 'B': ['A'], 'C': ['A'], 'D': ['B', 'C'] } # Алгоритм: # 1. Если стартовой точки нет в пути, добавляем её туда # 2. По очередно смотрим соседей у стартовой точки # 3. С каждым из соседей проверяем 1 и 2 def dfs_child_parent(graph, rod, det, visited=[]): if det not in visited: visited.append(det) for i in graph[det]: dfs_child_parent(graph, rod, i, visited) if rod in visited: return True else: return False print(dfs_child_parent(graph, 'A', 'D'))
""" Узнать максимальную глубину графа """ graph = {'A' : ['B','C'], 'B' : ['D', 'E'], 'C' : ['F'], 'D' : [], 'E' : ['F'], 'F' : [] } def dfs_max_deep(graph, start, visited=[]): d = 1 if start not in visited: visited.append(start) for neighbor in graph[start]: d = max(d, dfs_max_deep(graph, neighbor, visited) + 1) return d print(dfs_max_deep(graph, 'A'))