Graph g(v);

IO< GRAPH>:: scan(G);

if (V < 20) IO< GRAPH>:: show(G);

cout «G.E() «" edges ";

CC< GRAPH> Gcc(G);

cout «Gcc.count () «" components" «endl; }

Программа 17.6 служит примером клиентской программы обработки графов. Она ис­пользует базовый АТД программы 17.1, класс ввода/вывода программы 17.4 для считы­вания графа из стандартного ввода и его печати на стандартном устройстве вывода, а так­же класс связности программы 17.5 для отыскания количества его связных компонент. Мы используем подобные, но в то же время более сложные клиентские программы для по­строения других типов графов, для тестирования алгоритмов, для изучения других свойств графов и для использования графов при решении других проблем. Эту базовую схему можно применять в любых приложениях, выполняющих обработку графов.

В разделах 17.3-17.5 исследуются основные классические представления графа и ре­ализации функций АТД из программы 17.1. Для нас эти реализации представляют собой основу для расширения интерфейсов с тем, чтобы охватить задачи обработки графов, ко­торые станут объектами нашего внимания на протяжении ряда последующих глав.

Первое решение, которое следует принять при разработке реализации АТД, касает­ся того, каким представлением графа необходимо воспользоваться. Во-первых, мы дол­жны уметь приноравливаться ко всем типам графов, с которыми нам могут встретиться в приложениях (мы, скорее всего, не захотим впустую растрачивать пространство памя­ти). Во-вторых, мы должны уметь эффективно строить требуемые структуры данных. В третьих, мы хотим построить эффективные алгоритмы решения задач, связанных с обра­боткой графов, и не быть связанными ограничениями, накладываемыми представлением графа. Эти требования остаются в силе для любой рассматриваемой нами предметной об­ласти; здесь мы еще раз обращаем на них внимание, поскольку, как будет показано да­лее, различные представления являются причиной возникновения больших различий даже в случае самых простых задач.

Например, мы можем рассматривать представление вектора ребер (vector of edges) в ка­честве базы для реализации АТД (см. упражнение 17.16). Это прямое представление яв-

Часть 5. Алгоритмы на графах