Графы: топологическая сортировка, Деревья

Графом называется множество объектов произвольной природы (вершин) и связанных между собой попарно посредством ребер. Виды графов, способы их описания, различные алгоритмы на них и многое другое описывает такой обширный раздел дискретной математики как теория графов [1].
Графы являются одним из естественных способов описания реального мира и происходящих в нем процессов, что обуславливает их широкое практическое применение в различных областях от полетов в космос до решения примитивных бытовых задач [2].
В частности, графы и деревья применяются в таких областях как:
в сетях и телекоммуникационных системах графы используются для моделирования коммуникационных сетей, телефонных сетей, компьютерных сетей, Интернета;
в транспорте и логистике графы используются для планирования маршрутов, дизайна дорог, управления логистическими системами и т.д.
в графическом моделировании графы используются для моделирования процессов и объектов, включая логическое проектирование, анализ и оптимизацию производственных процессов;
в социальных сетях графы используются для изучения связей между людьми в социальных сетях, анализом параметров групп и состоящих в группах людей;
в компьютерной графике графы используются для создания и рендеринга 3D-моделей и сцен;
в вычислительной теории деревья используются для реализации алгоритмов поиска и сортировки;
в области искусственного интеллекта (ИИ) и машинного обучения деревья решений используются для определения оптимального пути в классификации данных;
в криптографии деревья используются для хранения и защиты ключевых данных и информации;
в базах данных деревья используются при построении индексов для быстрого поиска, сортировки и обработки больших объемов информации в базах данных;
в играх деревья используются для построения иерархических структур и объектов в играх, сюжетных стратегий и т.д.
Таким образом, графы и деревья широко используются во многих областях, где необходима организация, классификация, анализ, сортировка и поиск информации.
Целью данной работы является создание программы, решающей две задачи: одну на ориентированном графе и одну на дереве.
Для достижения цели необходимо реализовать следующие задачи:
проанализировать задачи;
определить входные и выходные данные по каждой задаче;
создать и описать алгоритмы решения задач;
провести тестирование созданной программы по каждой из задач.


1ЗАДАЧА 1
1.1Постановка задачи
Графом называется конечное множество вершин и множество ребер. Каждому ребру сопоставлены две вершины – концы ребра [3]. В данном определении концы у каждого ребра равноправны, т.е. в нет разницы где начало, а где конец у ребра.
Топологическая сортировка, однако, подразумевает что граф ориентирован и не содержит циклов и петель [6,7].
Цикл – это путь в графе, проходящий через несколько ребер и вершин начинающийся и заканчивающийся в одной и той же ве