Dfs — обход графа в глубину

Алгоритм обхода графа в глубину

""" ****** Стандартный алгоритм обхода графа в глубину. ****
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'))