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