Часть 5. Алгоритмы на графах. struct node { int cnt; vector <int> edges; }; struct graph { int V; int E; vector <node> adj; };

struct node { int cnt; vector < int> edges; }; struct graph { int V; int E; vector < node> adj; };

Граф есть совокупность числа вершин, числа ребер и вектора вершин. Вершина со­держит число ребер и вектор с одним индексом вершины, соответствующей каждому смежному ребру.

• 17.53. Добавьте к вашему решению упражнения 17.52 функцию, которая, аналогич­
но упражнению 17.34, удаляет петли параллельные ребра.

о 17.54. Разработайте реализацию АДТ статического графа, описанного в упражнении 17.51, которая использует всего лишь два вектора для представления графа: один век­тор - это вектор Е вершин, второй — вектор V индексов или указателей на первый вектор. Получите реализацию функции io:: show для этого представления.

• 17.55. Добавьте к вашему решению упражнения 17.54 функцию, которая удаляет петли
и параллельные ребра, как в упражнении 17.34.

17.56. Разработайте интерфейс АТД графа, который связывает координаты (х, у) с
каждой вершиной, что позволит работать с чертежами графов. Включите функции
drawV и drawE для нанесения на чертеж, соответственно, вершин V и ребер Е.

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

17.58. Разработайте реализацию интерфейса из упражнения 17.56, создающую програм­
му PostScript, выходом которой служат чертежи (см. раздел 4.3.).

17.59. Найдите соответствующий графический интерфейс, который позволил бы раз­
работать реализацию интерфейса из упражнения 17.56, способную непосредственно вы­
водить на экран чертежи графов в специальном окне.

• 17.60. Распространите ваше решение на упражнения 17.56 и 17.59 с таким расчетом,
чтобы они содержали функции удаления вершин и ребер и были способны вычерчи­
вать их в различных стилях с тем, чтобы вы могли писать клиентские программы, спо­
собные осуществлять динамические графические анимации алгоритмов обработки гра­
фов в процессе работы.