Задание. Опишите класс – ориентированный граф, необходимый для решения задачи, указанной в вашем варианте задания

Опишите класс – ориентированный граф, необходимый для решения задачи, указанной в вашем варианте задания, и реализуйте его методы. Составьте программу решения задачи, указанной в вашем варианте задания. В программе необходимо продемонстрировать работу основных методов работы с графом: построение, вывод, просмотр (т.е. программа должна иллюстрировать работу с графом как в примере выполнения задания).

Исходный граф может содержать петли и циклы.

Если требуется реализовать граф с помощью циклического или двусвязного списка, то в число обязательных операций должны быть включены: построение, обход, очистка графа и операции, необходимые для их реализации. Специальные для каждого задания операции указаны в скобках.

Варианты заданий

1. Определить кратчайший путь между узлами n 1 и n 2 и его длину во взвешенном графе.

2. Определить, является ли один граф подграфом другого.

3. Задана карта дорог в виде графа. Найти города, расположенные на расстоянии более X от заданного узла.

4. Реализовать граф с помощью односвязных циклических списков (включение и исключение узла).

5. Найти все узлы графа, к которым можно добраться из заданного узла.

6. Определить кратчайший путь между узлами n 1 и n 2 и его длину во взвешенном графе.

7. Определить, является ли ориентированный граф несвязным.

8. Составить список узлов, расстояние от которых до заданного узла не превышает величину X.

9. Определить, является ли один граф суграфом другого.

10. Реализовать граф с помощью односвязных циклических списков (определение начального и конечного узлов каждой дуги).

11. Найти все узлы графа, из которых можно добраться до заданного узла.

12. Определить расстояние между узлами n 1 и n 2 во взвешенном циклическом графе.

13. Определить, является ли один граф частью другого.

14. На основе обхода в ширину найти все узлы заданного графа, недостижимые из заданного узла.

15. На основе поиска в ширину определить, является ли граф несвязным.

16. Перечислить узлы графа по возрастанию расстояния до них от заданного узла.

17. Реализовать граф с помощью двусвязных списков (включение и исключение узла).

18. Задана карта дорог в виде графа. Найти города, расположенные на расстоянии X от заданного узла.

19. На основе обхода в ширину найти узел с заданным значением в графе и исключить его.

20. Найти узел графа, ближайший к заданному злу.

21. На основе поиска в ширину определить, является ли граф связным.

22. Реализовать граф с помощью односвязных циклических списков (включение и исключение дуги, определение количества узлов).

23. Найти все циклы в графе.

24. Определить, является ли один граф дополнением другого.

25. Задана карта дорог в виде графа. Найти города, расположенные на расстоянии не более X от заданного узла.

26. На основе обхода в глубину найти все узлы заданного графа, недостижимые из заданного узла.

27. Определить, является ли граф полным.

28. Найти все узлы графа, к которым можно добраться из заданного узла по пути не длиннее заданного значения.

29. Определить длины всех путей между узлами n 1 и n 2 в невзвешенном графе.

30. Найти узел графа, наиболее удаленный от заданного узла.