![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Смежности
Если мы обнулим главную диагональ матрицы смежности орграфа, квадрат такой матрицы будет представлять собой граф с ребрами, соответствующими каждому пути длиной 2 (вверху). Если установить каждый элемент главной диагонали в 1, то квадрат такой матрицы будет представлять собой граф с ребрами, соответствующий каждому пути длиной 1 или 2 (внизу). Часть 5. Алгоритмы на графах
На рис. 19.15 представлены различные степени матрицы смежности для одного и того же, взятого в качестве примера орграфа, постепенно сходящиеся к транзитивному замыканию. Рассматриваемый метод предусматривает V умножений матриц самой на себя, для каждого из которых требуется время, пропорциональное V3, что в конечном итоге составит V4. Фактически мы можем вычислить транзитивное замыкание для любого орграфа всего лишь за счет выполнения [дgV] операций булевого умножения матриц: мы вычисляем А2, A4, A 8,..., до тех пор, пока не достигнем показателя степени, большего или равного V4. Как следует из доказательства свойства 19.6, А = A у для любого t > V; таким образом, результатом этого вычисления, требующего на свое выполнение времени, пропорционального V3 lgV будет Ау, т.е. транзитивное замыкание. И хотя только что описанный подход привлекает своей простотой, тем не менее, существует еще более простой метод. Мы можем вычислить транзитивное замыкание, применив всего лишь одну операцию такого рода, предусматривающую построение транзитивного замыкания матрицы смежности вместо самой матрицы: for (i = 0; i < V; i++) for (s = 0; s < V; s++) for (t = 0; t < V; t++) if (A[s][i] & & A[i][t]) A[s][t] = 1; Этот классический метод, предложенный С. Уоршаллом (S. Warshall) в 1962 г., наиболее предпочтителен при вычислении транзитивных замыканий насыщенных орграфов. Приведенный выше программный код подобен коду, который можно использовать для возведения в квадрат булевой матрицы: различие (что очень важно!) заключается в порядке выполнения циклов for. Свойство 19.7. С помощью алгоритма Уоршалла мы можем вычислить транзитивное замыкание орграфа за время, пропорциональное V3. Доказательство: Оценка времени выполнения рассматриваемого программного кода непосредственно следует из его структуры. Мы докажем, что он способен вычислить транзитивное замыкание методом индукции по i. После выполнения первой итерации цикла в матрице на пересечении строки s и столбца t стоит 1 в том и только том случае, когда существуют пути s-t или s-0-t. Вторая итерация проверяет все пути между s и t, которые содержат вершину 1 и, возможно, 0, такие как, например, s-1-t, s-1-0-t и s-0-l-t. Мы Глава 19. Орграфы и ориентированные ациклические графы
Мы можем повысить производительность алгоритма Уоршалла путем простого преобразования программного кода: мы вынесем проверку элемента A[s][i] из внутреннего цикла, поскольку по мере изменения t его значение не меняется. Это действие позволит нам избежать выполнения t-ro цикла полностью, когда элемент A[s][i] равен нулю. Экономия, которую мы получим от данного усовершенствования, зависит от особенностей орграфа и в большинстве случаев весьма существенна (см. упражнения 19.53 и 19.54). Программа 19.3 реализует это усовершенствование и представляет собой метод Уоршалла в виде, позволяющем клиентам сначала выполнить предварительную обработку орграфа (вычислить транзитивное замыкание), затем дать за постоянное время ответ на любой запрос относительно достижимости. Мы заинтересованы в получении более эффективных решений, в частности, для разреженных графов. Мы хотели бы сократить время предварительной обработки, равно как и пространства памяти, поскольку оба эти фактора предъявляют к системе, использующей алгоритм Уоршалла, такие требования, что стоимость обработки крупных разреженных орграфов по соображениям фактически становится просто запредельной. В современных приложениях абстрактные типы данных предоставляют нам возможность выделить идею операции из любой конкретной реализации с тем, чтобы можно было сосредоточить свои усилия только на эффективных реализациях. В случае транзитивного замыкания эта точка зрения приводит к признанию того факта, что нам не обязательно вычислять всю матрицу, чтобы предоставить клиентам абстракцию транзитивного замыкания. Вполне вероятно, что одна из возможностей заключается в том, что транзитивным замыканием является крупная разреженная матрица, поэтому возникает необходимость в представлении графа в виде списков смежных вершин, поскольку сохранение графа в матричном виде чересчур накладно. Даже если транзитивное замыкание насыщено, клиентские программы могут проверять только крошечную часть возможных пар вершин, так что вычисление полной матрицы попросту расточительно.
|