Дискретная математика

148 Разобьем вершины графа на три класса: 1 - вершины, вошедшие в уже построенную часть дерева; 2 - вершины, окаймляющие построенную часть; 3 - еш;ё не рассмотренные вершины (для полного графа 3-ий класс будет пустым). Начнем с произвольной верхшгны графа и включим ее в остовное дерево. Все вершины, соединенные ребром с выбранной на к-и шаге вершиной, добавляем в кайму. Затем выполняется цикл поиска ребра с наименьшей длиной среди ребер, соединяюш;их вершины построенного дерева с каймой. Выбранное ребро вместе со своей новой верппшой добавляется в дерево, и производится обновление каймы. Более формальная запись алгоритма Дейкстры - Прима имеет следуюш.ий вид. Выбрать начальный узел Сформировать начальную кайму, состоящую из вершин, соседних с начальным узлом while в графе есть вершина, не попавшая в дерево do выбрать ребро из дерева в кайму с наименьшей длиной добавить конец ребра к дереву изменить кайму, для чего добавить в кайму вершины, соседние с новой обновить список ребер из дерева в кайму так, чтобы он состоял из ребер с наименьшей длиной end Реализация алгоритма Дейкстры - Прима для графа G представлена на рис. 5.21, б): выбранные вершины графа отмечены кружочками, вершины, попадающие в кайму, - штриховыми кружочками; ребра, соединяющие выбранные вершины и вершины каймы, нарисованы жирными штриховыми линиями. Результат применения пятого и шестого шага алгортма представлен на последнем варианте рисунка. Алгоритм получает на вход связный граф. В процессе работы алгоритма все вершины, еще не попавшие в дерево, хранятся в очереди с приоритетами. Время работы алгоритма Дейкстры - Прима зависит от того, как организована очередь и может иметь порядок О(mlogiw), либо - порядок 0(т+п1о§2п), где т - число ребер графа, а и - число его вершин. Сделаем следующее важное замечание. Пусть, например, п городов расположены на равнине (плоскости), а длина ребер есть расстояние между точками. Требуется соединить их телефонной или газовой сетью, но так, чтобы минимизировать суммарную длину телефонного кабеля или газопроводов соответственно. Предложенные алгоритмы решают эту задачу, но если ввести в граф новые вершины (разветвления вне заданных городов), то решение окажется более экономным.