![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
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.3-17.5 исследуются основные классические представления графа и реализации функций АТД из программы 17.1. Для нас эти реализации представляют собой основу для расширения интерфейсов с тем, чтобы охватить задачи обработки графов, которые станут объектами нашего внимания на протяжении ряда последующих глав. Первое решение, которое следует принять при разработке реализации АТД, касается того, каким представлением графа необходимо воспользоваться. Во-первых, мы должны уметь приноравливаться ко всем типам графов, с которыми нам могут встретиться в приложениях (мы, скорее всего, не захотим впустую растрачивать пространство памяти). Во-вторых, мы должны уметь эффективно строить требуемые структуры данных. В третьих, мы хотим построить эффективные алгоритмы решения задач, связанных с обработкой графов, и не быть связанными ограничениями, накладываемыми представлением графа. Эти требования остаются в силе для любой рассматриваемой нами предметной области; здесь мы еще раз обращаем на них внимание, поскольку, как будет показано далее, различные представления являются причиной возникновения больших различий даже в случае самых простых задач. Например, мы можем рассматривать представление вектора ребер (vector of edges) в качестве базы для реализации АТД (см. упражнение 17.16). Это прямое представление яв- Часть 5. Алгоритмы на графах
|