Все знают, что такое ориентированный или же неориентированный граф, ведь да?) Большинство знает и про сильно связные графы(ортограф, у которого верно следующее условие: из одной любой вершины существует путь в любую другую) и слабо связные графы(догадаетесь сами?:3). Есть еще виды ортографов, например, DAG-граф. По-русски говоря, это направленный(то есть ориентированный) ациклический(не имеющей вершины, являющейся началом и концом для одного и того же ребра) граф. Что это значит? А это означает, что если существует путь S из вершины v1 в v2, то НЕ существует S1 из v2 в v1. Подобные графы очень часто встречаются, например, в бизнесе. Если есть задача B, такая, что для её достижения необходима задача A, то она была бы нерешаема, если бы обратное условие было так же необходимо. Теперь вернемся к информатике и разберем стандартную задачу на нахождение, например, всех возможных путей из вершины А в вершину Н(ну, рисунок вы и сами сможете сделать, учитывая, что все ребра указаны в коде. помните, что ребро AB означает, что существует путь из A в B, но оно не гарантирует наличие пути из B в А) Сначала "запишем" граф в код: s = "AB AC AD BC BG CF CD DE EF EH FG FH GH".split() Введем функцию Z(A -> D) = Z(A -> B) + Z(A - C) Заметим, что Z(A -> A) = A(или же 0) -> задачу можно решить рекурсивным алгоритмом. def travel(cur, path): n = [b for a, b in s if a == cur] if not len(n): print(*path, "H") for x in n: travel(x, path + [cur]) Справедливым замечанием будет то, что нам необходимо количество путей, поэтому итоговый код: s = "AB AC AD BC BG CF CD DE EF EH FG FH GH".split() ans = [] def travel(cur, path): n = [b for a, b in s if a == cur] if not len(n): ans.append(path) for x in n: travel(x, path + [cur]) travel("A", []) print(len(ans)) Спасибо за прочтение🥹! Если кто-то до сюда дошел, то отпишите в комментариях, про что делать следующий пост?(bfs, dfs, алгоритм Дейкстры, Минимальное Остовое дерево) #графы 📺Channel