Графы. Поиск циклов. Определение предков в дереве
Определение Предок (в наиболее используемом понимании), родитель – это вершина, из которой был совершён переход в данную. Предок вершины в дереве – любая вершина, расположенная на пути от данной до корня. Наименьший общий предок двух вершин – это вершина максимально удалённая от корня дерева, которая является предком для обоих этих вершин. Алгоритм поиска циклов Проведём поиск в глубину. Если граф ненаправленный, то дополнительно для каждой вершины будем хранить родителя (номер вершины, из которой мы пришли в текущую), переход в родителя осуществлять не будем. Если в какой-то момент обхода мы зашли в серую вершину, то мы нашли цикл. С момента нахождения цикла будем добавлять текущую вершину в перечень вершин цикла и откатываться к предыдущей, пока не дойдём то старта цикла.