Задачи № 2

1. Написать программу, находящую вершину наибольшей степени.

2. Написать программу, проверяющую связность графа.

3. Написать программу, находящую компоненты связности графа.

4. Написать программу, определяющую по двум вершинам принадлежность их к одной компоненте связности.

5. Написать программу, находящую наибольшую по числу вершин компоненту связности графа.

6. Написать программу, находящую наибольшую по числу рёбер компоненту связности графа.

7. Написать программу, определяющую является ли граф деревом.

8. Написать программу, определяющую содержит ли граф циклы.

9. Написать программу, строящую остов связного графа.

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

11. Написать программу, проверяющую Эйлеровость связного графа.

12. Написать программу, проверяющую Эйлеровость связного графа.

13. Реализовать поиск в глубину.

14. Реализовать поиск в глубину в ориентированном графе.

15. Проверить достижимость вершины графа их указанного множества вершин.

16. Построить дерево кратчайших путей из указанной вершины в графе.

17. Построить дерево кратчайших путей из указанной вершины в ориентированном графе.

18. Найти мосты в связном неориентированном графе.

19. Проверить неориентированный граф на двудольность.

20. Реализовать поиск в ширину.

21. В неориентированном графе найти минимальный путь между двумя вершинами.

22. Во взвешенном неориентированном графе найти минимальный путь между двумя вершинами.

23. Реализовать алгоритм топологической сортировки

24. Найти точки сочленения в связном неориентированном графе

25.     С помощью поиска в глубину определить число компонент связности графа.

26.     С помощью поиска в ширину определить число компонент связности графа.

27.     С помощью поиска в глубину проверить существование маршрута между вершинами U и V графа, если маршрут существует, то восстановить его.

28.     С помощью поиска в ширину проверить существование маршрута между вершинами U и V графа, если маршрут существует, то восстановить его.

29.     Для графа дерева найти длину пути от вершины U до V  (использовать поиск в глубину и счётчик рекурсии WG).

30.     Для графа дерева найти длину пути от вершины U до V  (использовать поиск в ширину и счётчик слоёв).

31.     Построить остов графа с помощью поиска в глубину.

32.    С помощью поиска в глубину проверить является ли заданное ребро графа мостом.

33.    С помощью поиска в ширину проверить является ли заданное ребро графа мостом.

34.   Проверить, является ли граф деревом с помощью построения его остова с помощью поиска в ширину.

35.   Реализовать алгоритм поиска в ширину и определить вершину, наиболее удалённую от начальной  вершины r.

36.   С помощью поиска в глубину проверить, что данное множество вершин является базой.

37.   С помощью поиска в ширину проверить, что данное множество вершин является базой.

Класс tList

Класс TList — универсальный список. Он представляет собой массив нетипизированных указателей и поэтому годится для хранения набора любых, в том числе разнотипных, данных и объектов. При добавлении/удалении в список данные не создаются и не уничтожаются — эта обязанность лежит на программисте. Приведем доступные ему методы и свойства класса:

property Items[Index: Integer]: Pointer;	Возвращает указатель на содержимое элемента списка с индексом Index. Это свойство является векторным свойством, принимаемым по умолчанию, и его имя можно при записи опускать (см. раздел "Свойства").
property Count: Integer;	Определяет число элементов в списке.
property Capacity: Integer;	Определяет максимальное число элементов в списке. Оно может изменяться как явно — пользователем, так и при добавлении элементов в список, в том случае, когда Count>=Capacity. Максимальная емкость списка — 16380 элементов.

Управляют списком следующие методы:

function Add(Item: Pointer): Integer;	Добавляет в конец списка элемент, который будет равен Item (т. е. указывать на те же данные).
function Remove(Item: Pointer): Integer;	Удаляет из списка элемент, который равен Item.
procedure Insert(Index: Integer; Item: Pointer) ;	Вставляет элемент, равный Item, перед элементом с индексом Index.
procedure Delete(Index: Integer);	Удаляет из списка элемент с индексом Index.
procedure Clear;	Очищает список, устанавливая величины Count и Capacity в 0.
procedure Exchange(Indexl, Index2: Integer);	Меняет местами элементы списка с индексами Indexl и Index2.
function Expand: TList;	При соблюдении равенства Count=Capacity расширяет список. При емкости списка менее пяти элементов, он по умолчанию расширяется на четыре элемента, при пяти-восьми — на восемь, более восьми — на шестнадцать.
function First: Pointer; function Last: Pointer;	Возвращают значения первого п последнего (с индек­сом Count-1) элементов списка соответственно.
function IndexOf(Item: Pointer): Integer;	Возвращает индекс элемента, равного Item.
procedure Move(CurIndex, Newlndex: Integer) ;	Перемещает элемент списка с положения Curlndex в положение Newlndex.
procedure Pack;	Упаковывает список, сдвигая элементы к началу на пустующие места.

VECTOR

Для создания вектора вам необходимо подключить <vector>. Затем создание вектора почти ничем не отличается от создания переменной и/или массива:

vector <type> name; //здесь type- тип данных в векторе, а name - имя вектора

Для записи в вектор достаточно набрать имя вектора.push_back(что положить)

vector <int> test;

test.push_back(10);

test.push_back(20);

Обращение к n-ому элементу ничем не отличается от обращения к элементу массива:

test[0]++;

cout<<test[1];

test[1]=222;

Для удаления последнего элемента вектора используется функция pop_back()

test.pop_back();

Еще немного полезных функций:

• test.at(i) - равносильно записи test[i], но при этом, если i-ого элемента не существует, программа не вылетит:)

• test.asign(n,m) - записывает в массив n элементов со значением m

• test.asign(start,end) - записывает в вектор значения от start до end.Внимание!!! start и end - интераторы (указатели) на элементы другого вектор.

• test.front() - возвращает ссылку на первый элемент

• test.back() - возвращает ссылку на последний элемент

• test.begin() - возвращает интератор первого элемента вектора

• test.end() - последнего + 1

• test.clear() - очищает вектор

• test.erase(i) или test.erase(start,end) - удаляет элемент с итератором i или элементы с интераторами между старт и енд

• test.size() - возвращает количество элементов в векторе

• test.swap(test2) - меняет местами содержимое вектора test и  вектора test2

• test.insert(a,b) - вставляет в test переменную b перед элементом с интератором a и возвращает интератор вставленного элемента

• test.insert(a,n,b) - вставляет n копий b

• test.insert(a,start,end) - вставляет элементы между между итераторами start и end перед a