Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
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. Алгоритмы на графах ляется простым, однако оно не позволяет эффективно выполнять базовые операции обработки графов, к изучению которых мы вскоре приступим. У нас будет возможность убедиться в том, что большинство приложений, выполняющих обработку графов, можно применять с большим или меньшим успехом, если пользоваться всего лишь двумя несколько более сложными по сравнению с вектором ребер представлениями, а именно, в виде матриц смежности {adjacency-matrix) и в виде списков смежных вершин {adjacency-list) гр афа. Эти представления графов, которые будут рассматриваться в разделах 17.3 и 17.4, основаны на элементарных структурах данных (в самом деле, мы их обсуждали как в главе 3, так и в главе 5, как примеры применения последовательного и связного распределения). Выбор какого-либо из них зависит главным образом от того, является ли граф насыщенным или разреженным, хотя, как обычно, характер выполняемых операций также играет важную роль при принятии решения в пользу того или другого представления.
|