Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

В настоящее время дискретная математика и смежные с ней разделы привлекают большое внимание специалистов различных областей науки и техники, являясь эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Особое значение с практической точки зрения имеет теория графов, использующаяся при проектировании интегральных схем и схем управления, исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, при разработке вычислительных и информационных сетей, в схемотехническом и конструкторско-топологическом проектировании, и т.д. Обширное применение теория графов находит в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании ЭВМ, баз данных, систем логического управления.

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

Темой курсовой работы является алгоритмы поиска в ориентированных графах.

Но в ней будут также рассмотрены и способа представления ориентированных графов в виде различных матриц, графически и другими способами.

СПОСОБЫ ПРЕДСТАВЛЕНИЯ

Существует много различных способов представления ориентированных и неориентированных графов. Графы можно изображать с помощью рисунков, можно задавать как пары множеств, следуя определению:

ориентированный граф G задается двумя множествами G=( V, E ), где V- конечное множество, элементы которого называют вершинами или узлами; Е - множество упорядоченных пар на V , т.е. подмножество множества V х V, элементы которого называют дугами. Но такой способ довольно громоздкий и интересен больше с теоретической точки зрения. Развитие алгоритмических подходов к анализу свойств графов требует иных способов описания графов, более пригодных для практических вычислений , в том числе с использованием ЭВМ. Рассмотрим три наиболее распространенных способа представлений графов.

Предположим, что все вершины и все ребра неориентированного графа или все вершины и все дуги ( включая петли) ориентированного графа пронумерованы начиная с единицы. Граф (неориентированный или ориентированный) может быть представлен в виде матрицы типа п x m, где п- число вершин, а m- число ребер или дуг.

Для неориентированного графа элементы матрицы задаются так:

1, для i-ой вершины j-ое ребро инцидентное;

bij =

0, иначе;

Для ориентированного графа элементы матрицы задаются так:

1, для i-й вершины j-я дуга выходящая

aij= - 1, для i-й вершины j- дуга заходящая

0, иначе.

Матрицу (аij) типа n x m, определенную указанным способом, называют МАТРИЦЕЙ ИНЦИДЕНЦИЙ.

ПРИМЕР:

Для ориентированного графа, представленного на рисунке, нумерация вершин уже задана. Зададим нумерацию дуг следующим образом : дуге (v1, v2) присвоим номер 1, дуге (v1, v3) - 2, дуге ( v2, v3) - 3 и дуге (v3, v2) - 4.

Матрицу инциденций удобно заполнять по столбцам, записывая для k-й дуги (vi,vj) 1 в i-й и -1 в j-й строках k-го столбца и 0 во всех остальных строках k-го столбца. В результате получим матрицу:

v2

1 1 0 0

v1 -1 0 1 -1 .#

0 -1 -1 1

v3

Несмотря на то, что представление графа в виде матрицы инциденций играет весьма большую роль в теоретических исследованиях, практически этот способ весьма неэффективен. Прежде всего, в матрице в каждом столбце только два ненулевых элемента, что делает этот способ представления графа неэкономным при большом количестве вершин. Кроме того, решение практических задач с помощью матрицы инциденций весьма трудоемко.

Оценим, например, временные затраты на решение с помощью матрицы инциденций такой простой задачи в ориентированном графе:

для данной вершины vк найти ее «окружение» - множество приемников и множество предшественников вершины vк, т.е. множество всех вершин, непосредственно достижимых из vк, и множество всех вершин, из которых она непосредственно достижима.

Для решения этой задачи на матрице инциденций ориентированного графа нужно идти по строке с номером k до появления ненулевого элемента (+1 или -1). В случае, если обнаружена +1, в соответствующем столбце надо найти строку, в которой записано число -1. Номер строки, в которой стоит это число, дает номер вершины, непосредственно достижимой из данной вершины. Если обнаружена -1, в столбце надо найти строку, в которой записана 1, и получить номер вершины, из которой непосредственно достижима данная вершина. Для получения всего «окружения» надо проделать указанный поиск для всех ненулевых элементов k-й строки. Наиболее трудоемкой процедурой является поиск ненулевого элемента в столбце. Число таких процедур поиска равно степени вершины vк.

Будем в этом случае говорить, что сложность алгоритма анализа окружения вершины vк составляет О(dg vк) (порядка dgvк).

Можно увидеть, что поиск «окружения» всех вершин займет время, порядка произведения числа вершин ориентированного графа на сумму степеней всех вершин, которая, как можно показать, пропорциональна числу дуг ориентированного графа. Таким образом, сложность алгоритма поиска « окружения » составляет 0(nm), т.е. поиск занимает время порядка произведения числа вершин на число дуг.

Более эффективной матричной структурой, представляющей граф, служит матрица смежности вершин, или булева матрица графа. Это квадратная матрица B порядка n, элементы которой определяют следующим образом:

для неориентированного графа

1, i-я и j-я вершины смежные

bij =

0, иначе;

для ориентированного графа

1, из i-й вершины в j-ю ведет дуга;

bij =

0, иначе.

Заметим, что в k - й строке матрицы ориентированного графа количество единиц равно полустепени исхода dg+ vk вершины vk , а количество единиц в k-м столбце -- полустепени захода dg- vk.

Для неориентированного графа матрица смежности вершин симметрическая.

Для ориентированного графа матрица смежности вершин имеет вид:

0 1 1

0 0 1

0 1 0

Рассмотрим решение задачи поиска «окружения» с использованием матрицы смежности вершин. Для определения «окружения» вершины vk нужно сначала идти по k-й строке матрицы и искать ненулевые элементы. Если элемент аki = 1, то вершина vi достижима из вершины vk. После просмотра k-й строки надо просмотреть k-й столбец. Если элемент ajk = 1, то вершина vk достижима из вершины vj.

Можно показать, что с использованием матрицы смежности вершин решение задачи поиска «окружения» всех вершин ориентированного графа будет иметь сложность порядка n?, что эффективнее предыдущей оценки nm, если число дуг ориентированного графа превышает число его вершин, а это часто бывает в практических задачах.

Матрица смежности вершин является достаточно эффективным способом представления графов. Однако эту матрицу удобно строить по графу, уже заданному каким-либо способом, например рисунком. Во многих задачах граф создается динамически, т.е. в ходе решения задачи меняется множество вершин и множество ребер (или дуг). В этом случае эффективным способом машинного представления графа являются списки смежности (или списки инцидентности).

Рассмотрим ориентированный граф. Для задания множества вершин, непосредственно достижимых из вершины v, используют линейный однонаправленный список. Каждый элемент такого списка включает данные (например, некоторое число) и указатель на следующий элемент списка. Список в целом задается указателем на его первый элемент (голову списка). Последний элемент списка содержит «пустой» указатель.

. . .

Задать для вершины v ее список смежности означает в произвольном порядке поместить в данные элементов списка номера вершин u , для которых в ориентированном графе есть дуга из v в u (v u). Список смежности вершины v обозначают L(v).

Отметим, что список смежности вершины может при необходимости дополняться. Для этого в последнем элементе списка «пустой» указатель заменяется указателем на добавленный элемент, который становится последним элементом списка с «пустым» указателем.

Если количество вершин ориентированного графа известно заранее, то ориентированный граф удобно задавать в виде структуры, называемой массивом лидеров.

Под массивом мы понимаем матрицу-столбец, элементами которой могут быть некоторые объекты (например, элементы списка смежности). Их называют элементами массива. Число элементов массива лидеров равно числу вершин графа.

Элементами массива лидеров являются первые элементы списков смежности вершин ориентированного графа. Пример представления ориентированного графа списками смежности, собранными в массив лидеров:

v1 v5

v1 v2

v2 v2 v2 v3 v4 v5

v3 v1

v4

v5 v2

v3 v4

С использованием списков смежности совсем просто решается задача поиска преемников данной вершины: для это достаточно просмотреть список смежности вершины, затратив на это время, пропорциональное ее полустепени исхода. Тогда на решение этой задачи для всего ориентированного графа потребуется время порядка числа его дуг.

Менее эффективно решается задача поиска предшественников вершины, так как в этом случае необходимо, вообще говоря, просмотреть списки смежности всех вершин с целью поиска в них данной вершины.

Таким образом, задача поиска «окружения» с использованием списков смежности является более трудоемкой, чем в случае использования матриц. Однако удобство динамического формирования описания ориентированного графа в данном случае перевешивает. Если задача поиска предшественников возникает часто, можно использовать двусторонние списки смежности, сопоставляя каждой вершине уже два списка - преемников и предшественников.

Описанные способы представления графа списками не исчерпывают всех возможных вариантов, а в литературе по программированию можно найти разнообразные варианты организации списков. Поскольку эти особенности относятся к технологии программирования, мы не будем в них углубляться и в дальнейшем для простоты при описании различных алгоритмов будем считать, что (односторонние) списки смежности собраны в массив лидеров, так как в рассматриваемых ниже алгоритмах анализа графов именно анализ множества преемников вершины наиболее важен.

Рассмотрим еще одну матрицу, характеризующую граф, - так называемую матрицу достижимости. Это квадратная матрица С порядка |V|, каждый элемент сij которой равен 1, если j-я вершина достижима из i-й вершины, и равен 0 если иначе. Отметим, что, согласно определению достижимости, элементы сii = 1.

Метод вычисления матрицы достижимости ориентированного графа по его матрице смежности будет рассмотрен в примере далее.

Матрица достижимости несет очень важную информацию об ориентированном графе. Ее анализ позволяет, например, найти его бикомпоненты и компоненты.

По определению, в бикомпоненту входят взаимно достижимые вершины. Для двух таких вершин с номерами i и j должно выполняться равенство сij = сji = 1.

Поэтому, чтобы найти бикомпоненту, в которую входит i-я вершина ориентированного графа, нужно просмотреть i-ю строку и i-й столбец матрицы достижимости С и сформировать множество Рi={p: cip = cpi = 1} номеров вершин, порождающих искомую бикомпоненту. Из определения матрицы достижимости вытекает, что в Рi, содержаться номера всех вершин данной бикомпоненты. Поскольку две различные бикомпоненты не пересекаются, вершины с номерами из множества Рi при поиске других бикомпонент из рассмотрения можно исключить. Процесс поиска целесообразно начать с первой вершины. Он закончится, когда для каждой вершины будет найдена содержащая ее бикомпонента. При этом может оказаться, что некоторые ( а может быть, и все) бикомпоненты содержат только по одной вершине, поскольку каждая вершина, по определению, достижима сама из себя.

Поиск компонент ориентированного графа сложнее, так как в компоненту входят вершины с номерами i и j, для которых сij = 1 или сji = 1. Кроме того, одна и та же вершина может входить в несколько различных компонент. Отметим, что любая бикомпонента или не пересекается с некоторой компонентой, или целиком в нее входит.

Пример для ориентированного графа, матрица достижимости:

1 1 1 1 1 0 0

0 1 1 1 1 0 0

0 1 1 1 1 0 0

С = 0 0 0 1 1 0 0

0 0 0 1 1 0 0

0 0 0 1 1 1 1

0 0 0 1 1 1 1

Начнем с поиска бикомпонент. Для первой вершины множество Р1 ={1},включает только ее саму. Для второй вершины имеем Р2 ={2,3}, для четвертой - Р4 ={4,5} и для шестой -

Р6 = {6,7}. Соответственно полученные множества вершин порождают бикомпоненты В1, В2, В3 и В4, изображенные на рисунке.

Перейдем к поиску компонент. Используя матрицу С, выпишем для каждой вершины vi, i=1,7 , множество Кi, состоящее из тех вершин, которые достижимы из i-й вершины или и которых достижима она.

В рассматриваемом ориентированном графе для вершины v1 в множестве К1 входят вершины, для которых с1j = 1 или сj1 = 1, т.е. К1 = {v1,v2,v3,v4,v5}. Для вершин v2 и v3 множества К2 и К3 совпадают с множеством К1. Поскольку все элементы четвертого и пятого столбцов матрицы С равны единице, то для вершин v4 и v5 имеем К4 = К5 = {v1,v2,v3,v4,v5,v6,v7}.

Для вершин v6 и v7 получим К6 = К7 = {v4,v5,v6,v7}.

Отметим, что множество Кi построено так, что любая компонента, содержащая вершину vi может содержать только вершины из множества Кi.

(Утверждение) Кроме того, если некоторая компонента Ср содержит вершины vi и vj, то вершина vm будет принадлежать этой компоненте в том и только в том случае, если vm Ki ? Kj.

Доказательство:

действительно, пусть вершина vm принадлежит компоненте Ср вместе с вершинами vi и vj. Тогда либо вершина vm достижима из вершины vi, либо, наоборот, vi достижима из vm, и следовательно, что vm Ki. Из аналогичных рассуждений вытекает, что vm Kj. Таким образом, вершина vm принадлежит пересечению множеств Ki и Kj.

Пусть теперь вершины vi и vj принадлежат компоненте Ср и

Vm Ki ? Kj. Тогда вершина vm также принадлежит компоненте Ср, поскольку либо вершина vi достижима из vm, либо vm достижима из vi, и для вершин vj и vm ситуация аналогична.

Начнем строить компоненты, содержащие вершину v1. Рассмотрим множество К1. Так вершина v2 принадлежит множеству К1, найдется по крайней мере одна компонента, в которую входят обе эти вершины. Обозначим ее через С1. Вершина v3 будет принадлежать этой компоненте в том и только в том случае, если v3 K1 ? K2. Непосредственная проверка показывает, что последнее условие выполняется.

Можно заметить, что К1 ? К2 ? К3 ? К4 ? К5 = К1, поэтому компонента С1 есть подграф, порожденный множеством К1, и вершина v1 не может входить какую-либо другую компоненту, отличную от С1. Поскольку в компоненту С1 вошли все вершины из множества К2 и К3, то вершины v2 и v3 также не входят ни в какие другие компоненты.

Перейдем к поиску компонент, отличных от С1, в которые входит вершина v4. В множестве К4 содержится вершина v5. Пересечению множеств К4 и К5 принадлежат вершины v6 и v7, не вошедшие в выделенную компоненту С1. Рассуждая аналогично и учитывая, что v4 и v5 принадлежат бикомпоненте В3, а v6 и v7 - бикомпоненте В4, получаем, что компонента С2 порождается множеством вершин

К4 ? К5 ? К6 ? К7 = К7,

и других компонент в рассматриваемом ориентированном графе нет.

ДЕРЕВЬЯ

Неориентированным деревом называют связный и ациклический неориентированный граф.

Ориентированным деревом называют бесконтурный ориентированный граф, у которого полустепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0.

Опираясь на данное определение, можно доказать, что в ориентированном дереве любая вершина достижима из корня.

Отметим, что из определения нельзя убрать требование бесконтурности ориентированного графа, поскольку бесконтурность не вытекает из других условий. Например, изобразим ориентированный граф, не являющийся ориентированным деревом, хотя полустепень захода всех вершин не больше 1 и ровно одна вершина имеет полустепень захода, равную 0.

v1 v4

v2 v3 v5

Вершину v ориентированного дерева называют потомком (подлинным потомком) вершины u, если существует путь из вершины u в v (путь ненулевой длины из u в v). В этом же случае вершину u называют предком (подлинным предком) вершины v, а если длина пути из u в v равна 1,то вершину v называют сыном вершины u, которая при этом вполне естественно именуется отцом вершины v. Вершину, не имеющую потомков, называют листом.

На рисунке вершины v4 и v5 есть сыновья вершины v2, которая в свою очередь, является сыном вершины v0 - корня дерева. Вершины v4 и v5 являются подлинными потомками вершин v0 и v2, которые соответственно будут их подлинными предками. Вершины v1,v4,v5,v6,v9,v8 - листья дерева. Взаимно недостижимые вершины ориентированного дерева (например, такие, как v2 и v9) не являются ни предком, ни потомком одна другой. Каждая вершина будет сама для себя предком и потомком, но не подлинным.

Определение:

Произвольный ациклический граф называют неориентированным лесом. Если каждая слабая компонента ориентированного графа является ориентированным деревом, то такой граф называют ориентированным лесом.

Пример неориентированного леса:

 v7 v8

v10 v9 v0

v11 v12 v1 v2

v14 v13 v4 v5 v6 v3

Пример ориентированного леса:

v7 v8

v9 v11 v0

v10

v12 v15 v1 v2

v14 v13 v4 v5 v6 v3

Определение:

подграф неориентированного (ориентированного) дерева, являющейся неориентированным (ориентированным) деревом, называют поддеревом исходного дерева.

Из определения следует, что неориентированный лес - это неориентированный граф, каждая компонента которого является неориентированным деревом.

Определение:

ориентированное дерево, у которого каждая вершина отличная от корня, есть лист, называют кустом. Пример куста на рисунке:

 v1

v2 v3

Рассмотрим числовые параметры, которыми характеризуется ориентированное дерево:

Высота ориентированного дерева - это наибольшая длина пути из корня в лист; глубина d(v) вершины ориентированного дерева v - это длина пути из корня в эту вершину; высота h(v) вершины ориентированного дерева v - это наибольшая длина пути из данной вершины в лист и, наконец, уровень вершины ориентированного дерева - это разность между высотой ориентированного дерева и глубиной данной вершины.

Уровень корня равен высоте ориентированного дерева, но уровни различных листьев, так же как и их глубины, могут быть различными; высота любого листа равна нулю.

Определение:

ориентированное дерево называют бинарным, если полустепень исхода любой его вершины не больше 2; бинарное ориентированное дерево называют полным, если из любой его вершины, не являющейся листом, исходят ровно две дуги, а уровни всех листьев совпадают.

v0 v0 v0

полное неполные

дерево деревья v1

v1 v2

v1 v2 v2 v3

v3 v4 v5 v6 v3 v4

v4 v5

Теорема:

Используя индукцию по высоте ориентированного дерева, можно показать, что в полном бинарном ориентированном дереве высоты h ровно 2 листьев.

Доказательство:

Действительно, ориентированное дерево высоты 0 имеет 2?= 1 лист.

Полное бинарное ориентированное дерево высоты 1 имеет 2? = 2 листа.

Пусть полное бинарное ориентированное дерево имеет высоту k и соответственно 2k листьев. Рассмотрим полное бинарное ориентированное дерево высоты k+1. Поскольку в полном бинарном ориентированном дереве уровни всех листьев совпадают, легко видеть, что ориентированное дерево высоты k+1 можно получить из полного бинарного ориентированного дерева высоты k, если из каждого листа последнего провести по две дуги. Тогда количество листьев в ориентированном дереве высоты k+1 будет в два раза больше, чем в ориентированном дереве высоты k, т.е.2 ^k·2 = 2^k+1.

Отсюда следует, что в произвольном бинарном дереве высоты h не более 2^h листьев. Таким образом, мы получаем следующий простой, но важный результат.

Теорема: о высоте бинарного ориентированного дерева с заданным числом листьев:

Бинарное ориентированное дерево с n листьями имеет высоту, не меньшую log2n. #

Эта теорема имеет одно весьма интересное приложение. Предположим, что необходимо расположить строго по возрастанию элементы конечного линейно упорядоченного множества {a1…..,an} . Эту задачу называют задачей сортировки, а любой алгоритм, ее решающий,- алгоритмом сортировки.

С математической точки зрения алгоритм сортировки должен найти такую перестановку {ai1,…,ain} элементов множества, которая была бы согласована с заданным на нем отношением ? линейного порядка, т.е. для любых k, l из справедливости неравенства ik < il должно следовать aik<ail.

Первоначально сортируемые элементы могут быть расположены в произвольном порядке, т.е. исходной может быть любая перестановка множества, и мы не имеем никакой априорной информации об этой перестановке. Единственный способ получить такую информацию - проводить попарные сравнения элементов ai, c aj для всех i ? j. Например, можно использовать транзитивность отношения порядка.

Все сравнения, которые в принципе могут быть проведены в процессе работы некоторого алгоритма, изображаются наглядно в виде ориентированного дерева, называемого деревом решений.

На рисунке приведено дерево решений для трехэлементного множества {a,b,c}. Вершины ориентированного дерева, не являющиеся листьями, помечены проверяемыми неравенствами, а множество листьев находится во взаимно однозначном соответствии с множеством всех перестановок исходного множества.

Размещено на http://www.allbest.ru/

Поскольку в результате сортировки может получиться любая перестановка исходного множества и каждой такой перестановке соответствует лист дерева решений, в общем случае количество листьев будет равно n! - количеству перестановок n-элементного множества.

Следовательно, сортируя входную последовательность, алгоритм обязательно пройдет какой-то путь от корня дерева решений к одному из листьев, и, таким образом, число операций сравнения (число шагов алгоритма сортировки) будет величиной, пропорциональной высоте дерева решений, не меньшей чем log2n!.

Используя для оценки факториала при больших n формулу Стирлинга

n! ? (n ?e) ,

получаем, что дерево решений имеет высоту порядка nlog2n.

Таким образом, в общем случае задачу сортировки с помощью попарных сравнений нельзя решить быстрее, чем за указанное число шагов. Безусловно, конкретный путь в дереве решений из корня к одному из листов зависит от исходной перестановки. Например, в дереве решений, приведенном на рисунке выше, есть два «коротких» пути длины 2, однако остальные пути имеют длину 3.

Заметим, что в общем случае ориентированное дерево - это не связный ориентированный граф. Компонентами ориентированного дерева являются его подграфы, порожденные множеством вершин.

Остовным лесом (деревом) неориентированного (ориентированного) графа называют любой его остовной подграф, являющийся лесом (деревом).

МЕТОДЫ СИСТЕМАТИЧЕСКОГО ОБХОДА ВЕРШИН ГРАФА

алгоритм поиск ориентированный графа матрица

Важными задачами теории графов являются задачи глобального анализа как неориентированных, так и ориентированного графов. К этим задачам относятся, например, задачи поиска циклов или контуров, вычисление длин путей между парами вершин, перечисление путей с теми или иными свойствами и т.п. Глобальный анализ графа следует отличать от локального, примером которого может служить задача определения множеств предшественников и преемников фиксированной вершины ориентированного графа.

Базой для решения многих задач глобального анализа являются так называемые алгоритмы обхода или поиска.

Необходимо уметь обходить все вершины графа таким образом, чтобы каждая вершина была отмечена ровно один раз. Обычно такое «путешествие» по графу сопровождается нумерацией вершин графа в том порядке, в котором они отмечаются, а также определенной «маркировкой» ребер (или дуг) графа.

Существуют две основные стратегии таких обходов: поиск в глубину и поиск в ширину. Эти стратегии можно описать так:

при поиске в глубину, отправляясь в «путешествие» по графу из некоторой начальной вершины v0, мы действуем следующим образом. Пусть, «путешествуя» , мы достигли некоторой вершины v0 (в начале «путешествия» v = v0). Отмечаем вершину v и просматриваем вершины из ее списка смежности L[v].

При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем «путешествие» из первой такой вершины w, действуя как описано выше - «ныряем» вглубь, т.е. просматриваем вершины списка смежности L[w] вершины w, откладывая анализ других элементов L[v] как возможных продолжений поиска «на потом».

Если же неотмеченных вершин в L[v] нет, то возвращаемся из v в ту вершину, из которой мы в нее попали, и продолжаем анализировать список смежности этой вершин.

«Путешествие» прекратится в тот момент, когда мы вернемся в начальную вершину v0 и либо все вершины будут отмеченными, либо окажется, что неотмеченные вершины есть, но из v0 больше никуда пойти нельзя. В последнем случае возможны продолженияпоиска из новой вершины или остановка, что определяется конкретной версией алгоритма.

Заметим, что результат поиска в глубину зависит от порядка вершин в списках смежности, представляющих граф, а также от выбора начальной вершины v0.

Пример поиска в глубину на неориентированном и ориентированном графах:

Прокомментируем поиск в глубину в ориентированном графе изображенном на рисунке. Пусть списки смежности вершин имеют следующий вид:

v0>(v1, v3), v1>(v2), v2>( ),

v3>(v1, v4), v4>(v2),

v5>(v3, v6, v7), v6>( ), v7>( ).

«Путешествие» начинается в вершине v0, и ей присваивается номер 1. Первой в списке смежности вершины v0 стоит вершина v1.

Даем ей номер 2 и продолжаем поиск из этой вершины. В списке смежности последней только одна вершина v2. Даем ей номер 3 и, так как ее список смежности пуст, возвращаемся в вершину v1.

В списке смежности вершины v1, нет других вершин, кроме вершины v1, нет других вершин, кроме вершины v2, уже помеченной номером 3, поэтому возвращаемся в вершину v0.

Второй элемент списка смежности вершины v0 - вершина v3.

Это вершина новая. Помечаем ее номером 4 и переходим к рассмотрению ее списка смежности. Первая в списке смежности вершина v1 уже получила номер 2. Поэтому переходим в новую вершину v4 и помечаем ее номером 5. Единственный элемент ее списка смежности, вершина v2, уже отмечена. Возвращаемся в вершину v3. Здесь тоже нет никаких «отложенных продолжений»,

И мы снова оказываемся в стартовой вершине v0. Все вершины из списка смежности стартовой вершины уже отмечены, т.е. все возможные пути поиска из этой вершины пройдены. Тем не менее в графе остались непосещенные (непронумерованные) вершины. Следующей по исходной нумерации вершин графа является вершина v5. Продолжим поиск из этой вершины и пометим ее номером 6. Первая вершина ее списка смежности - вершина v3 -уже отмечена. Посещаем следующую вершину - вершину v6 - и помечаем ее номером 7. Ее список смежности пуст. Возвращаемся в вершину v5. Посещаем последнюю неотмеченную вершину из ее списка смежности - вершину v7 - и помечаем ее номером 8. Поскольку все вершины из списка смежности вершины v5 отмечены, поиск в глубину закончен.

На рисунке более толстыми стрелками изображены дуги, по которым из очередной текущей вершины мы переходили к новой.

Рассмотрим теперь поиск в ширину. При поиске в ширину «правила игры» такие: достигнув некоторой вершины v , отмечаем ее. Затем просматриваем ее список смежности L[v] и отмечаем все ранее не отмеченные вершины списка ( при старте поиска v =v0 ).

После того как отмечены все вершины из L[v], вершину v считаем полностью обработанной и продолжаем обработку вершин из списка L[v] по очереди согласно описанным правилам.

Именно в обработке сразу всего списка смежности текущей вершины заключается принципиальное отличие поиска в ширину от поиска в глубину: там мы «ныряли» как можно «глубже», а здесь идем с «бреднем», «загребая» сразу все, что можно.

Поиск в ширину заканчивается, когда все вершины полностью обработаны или продолжение поиска невозможно.

Для сравнения возьмем неориентированный и ориентированный графы предыдущего примера и рассмотрим для них поиск в ширину.

Для неориентированного графа поиск из стартовой вершины v0 будем осуществлять так. Стартовой вершине присвоим номер 1. Затем пронумеруем все вершины из списка смежности стартовой вершины в порядке следования их в списке. При этом вершина v1 получит номер 2, а вершина v3 - номер 3. Теперь, когда все вершины из списка смежности вершины v0 отмечены, перейдем в первую по очереди вершину v1 . В ее списке смежности только одна ранее не отмеченная вершина - v2 . Присвоим ей номер 4 и перейдем в вершину v3 . На этом этапе номер 5 получит вершина v4, , а номер 6 - вершина v5 . Затем перейдем в вершину v2. Поскольку все вершины из списка смежности вершины v2 уже отмечены, перейдем в вершину v4 . Здесь также все вершины из списка смежности отмечены, поэтому перейдем в вершину v5. Просмотрим неотмеченные вершины из ее списка смежности и отметим вершины v6 и v7, присваивая им номера 7 и 8 соответственно. Теперь, когда список смежности вершины v5 обработан полностью, перейдем в вершину v6. Так как в ее списке смежности нет неотмеченных вершин, перейдем в вершину v7. Здесь также в списке смежности нет неотмеченных вершин. Все вершины обработаны, и поиск в ширину для графа закончен.



Результаты поиска в ширину из вершины v0 в ориентированном графе представлены на рисунке.

Обратим внимание на то, что нумерация вершин при поиске в ширину отличается от нумерации вершин при поиске в глубину. Так, в ориентированном графе мы сразу отмечаем оба элемента списка смежности вершины v0. Поэтому вершине, получившей при поиске в глубину номер 4, при поиске в ширину присваивается номер 3.

Перейдем теперь к подробному описанию алгоритмов поиска в глубину и поиска в ширину.

Рассмотрим алгоритм поиска в глубину в ориентированном графе:

он во многом аналогичен поиску в глубину в неориентированном графе. В этом случае возникает остовный ориентированный лес поиска в глубину, дуги которого - это те дуги, по которым в процессе работы алгоритма переходят от очередной вершины к новой, еще не отмеченной вершине. Можно показать, что это максимальный остовный лес исходного графа.

Слабыми компонентами этого глубинного остовного леса будут некоторые ориентированные деревья: поэтому, используемая далее терминология из теории деревьев относится к той или иной слабой компоненте глубинного остовного леса.

При поиске вершины ориентированного графа грани нумеруются в порядке их посещения. Номер вершины v графа, присваиваемый ей при поиске в глубину, обозначим D[v] и будем называть

D-номером.

Классификация дуг при поиске в глубину в ориентированном графе сложнее по сравнению с аналогичной классификацией ребер при поиске в глубину в неориентированном графе.

Различают четыре класса дуг:

1). Древесные дуги - каждая такая дуга ведет от отца к сыну в глубинном остовном лесу;

2). Прямые дуги - каждая такая дуга ведет от подлинного предка к подлинному потомку (но не от отца к сыну) в глубинном остовном лесу;

3).Обратные дуги - от потомков к предкам (включая все петли);

4).Поперечные дуги - все дуги, не являющиеся ни древесными, ни прямыми, ни обратными.

Следовательно, в результате работы алгоритма будут получены множества Tree - древесных дуг, Back - обратных дуг, Forward - прямых дуг, С - поперечных дуг и массив D, содержащий D-номера вершин.

В процессе работы алгоритма по сравнению с алгоритмом поиска в глубину в неориентированном графе имеется ряд особенностей. Так, если очередная вершина w, извлеченная из списка смежностей текущей вершины v, новая, т.е. w V0, то дуга (v,w) является древесной. Следует добавить дугу (v ,w) в множество древесных дуг ( Tree = Tree {(v,w)} ), сделать вершину w текущей (v = w) и начать ее обработку.

Если вершина w не новая (w V0), то дуга (v,w) будет либо прямой, либо обратной, либо поперечной.

Если D-номер вершины v строго меньше D-номера вершины w( D[v] < D[w] ), то дуга (v,w) является прямой. Добавляем ее в множество прямых дуг Forward ( Forward = Forward {(v,w)} ).

Если D-номер вершины v не меньше D-номера вершины w (D[v] ? D[w]), необходимо проверить , есть ли в стеке STACK вершина w. Если вершина w находится в стеке, то дуга (v,w) является обратной и ее следует добавить в множество обратных дуг Back ( Back = Back {(v,w)} ). Если вершины w в стеке нет, то дуга является поперечной. Тогда нужно добавить ее множество поперечных дуг С ( С = С {(v,w)} ). Далее следует перейти к рассмотрению очередной вершины из списка смежности текущей вершины (если он не пуст).

Если стек пуст, но не все вершины ориентированного графа обработаны, поиск продолжают из любой необработанной вершины.

В случае ориентированного графа поиск контуров на базе поиска в глубину существенно сложнее, чем в случае неориентированного графа, и здесь он не рассматривается. Однако можно доказать следующий критерий бесконтурности ориентированного графа: ориентированный граф является бесконтурным тогда и только тогда, когда при поиске в глубину от некоторой начальной вершины множество обратных дуг оказывается пустым.

Заметим также, что для ориентированного графа нет такой простой связи между числом опустошений стека и числом компонент, как для неориентированного графа. (Там число компонент равно числу опустошений стека от начала до конца поиска в глубину).

На базе алгоритма поиска в глубину может быть разработан эффективный алгоритм поиска бикомпонент в ориентированном графе. Однако здесь мы не будем останавливаться на задаче поиска бикомпонент, так как эта задача обсуждается в рамках общей задачи о путях в графах.

Можно показать, что алгоритм поиска в глубину имеет сложность порядка max(|V|,|E|).

Пример:

Проведем поиск в глубину на ориентированном графе, представленном на рисунке.

 1 v0 6 v7

B

v2 v1 C v5 C v6

2 F 5 7 8

C

C

3

v4 4 v3

Поиск начнем из вершины v0 . Пусть списки смежности вершин имеют следующий вид:

v0>( v2, v3, v1), v1>( v3), v2>( v4, v3),

v3>( v4), v4>( v1), v5>( v1),

v6>( v3, v5), v7>( v5, v6).

Результаты выполнения поиска в глубину представлены на рисунке: около каждой вершины указан ее D-номер, все древесные дуги выделены более толстыми стрелками, а прямые, обратные и поперечные помечены буквами F, B, C соответственно.

Первое опустошение стека происходит после обработки первых пяти вершин (в порядке обхода): v0, v2, v4, v3, v1.

После опустошения поиск продолжается из вершины v7, которой присваивается D-номер 6. (Напомним, что в приведенном выше алгоритме после опустошения стека для продолжения поиска выбирается любая из необработанных вершин). #

В отличии от алгоритма поиска в глубину, алгоритм поиска в ширину используется не стек, а очередь вершин. Мы дадим здесь вариант поиска в ширину, когда, начиная поиск в некоторой начальной вершине v0, мы останавливаемся при первом же опустошении очереди. Это значит, что некоторые из вершин могут остаться неотмеченными. Таким образом может быть решена задача распознавания достижимости от заданной вершины. Мы совместим также поиск в ширину с вычислением длины кратчайшего пути от v0 до любой вершины графа. Будем предполагать, что вершины графа пронумерованы без пропусков числами от 0 до N: V ={ vi : i = 0,N}.

Рассмотрим алгоритм поиска в ширину в ориентированном графе:

Вход. Граф G = (V,E), заданный списками смежности;

v0 - начальная вершина (не обязательно первый элемент массива лидеров)

Выход. Массив М меток вершин, где каждая метка равна длине пути от v0 до v .

0. Очередь Q положить пустой (Q = o). Все вершины пометить как недостижимые из вершины v0, присваивая элементам массива М значение + ?(М[vi] = + ?,i = 1, N).

Стартовую вершину v0 пометить номером 0, т.е. длину пути от стартовой вершины v0 до самой себя положить равной 0 ( М[v0]=0 ). Поместить вершину v0 в очередь Q. Перейти на шаг 1.

1. Если очередь Q не пуста (Q?o), то из « головы» очереди извлечь (с удалением из очереди) вершину u и перейти на шаг 2. Если очередь пуста, перейти на шаг 3.

2. Если список смежности L(u) вершины u пуст, вернуться на

шаг 1.

Если список смежности L(u) вершины u не пуст, для каждой вершины w из списка смежности, где М[w] = +?, т.е. вершины, которую еще не посещали, положить длину пути из стартовой вершины v0 до вершины w равной длине пути от v0 до вершины u плюс одна дуга (М[w] = M[u]+1) , т.е. отметить вершину w и поместить ее в очередь Q. После просмотра всех вершин списка смежности L(u) вернуться на шаг 1.

3. Распечатать массив М. Закончить работу.

Алгоритм поиска в ширину может быть дополнен процедурой «обратного хода», определяющей номера вершин, лежащих на кратчайшем пути из вершины v0 в данную вершину u. Для этого необходимо завести массив PR размера ¦V¦ , каждый элемент PR[w] которого содержит номер той вершины, из которой был осуществлен переход в вершину w при ее пометке.

Если вершина w находится в списке смежности L(u) вершины u,

заполнение элемента массива PR[w] происходит при изменении метки вершины w M[w]c +? на единицу. При этом в элементе PR[w] сохраняется номер вершины u (PR[w] = u). Для начальной вершины PR[v0] можно положить равным 0, в предположении, что начальная вершина v0 имеет номер 0 и остальные вершины пронумерованы от 1 до N.

Сложность рассмотренного алгоритма поиска в ширину, известного под названием «Алгоритм волнового фронта», составляет 0(max(|V|,|E|)).

Пример:

На рисунке дан пример работы алгоритма волнового фронта (при поиске из вершины v0 ) для ориентированного графа.

0 v0 +? v7

v2 v1 v5 v6

1 1 +? +?

2

v4 1 v3

Списки смежности ориентированного графа имеют вид

v0>( v2, v3, v1), v1>( v3), v2>( v4, v3),

v3>( v4), v4>( v1), v5>( v1),

v6>( v3, v5), v7>( v5, v6).

Около каждой вершины vi, поставлена метка М[vi], которую получает вершина при поиске в ширину. Выделены дуги, составляющие кратчайшие пути из вершины v0 в остальные.

Отметим, что вершины v5, v6 и v7 не достижимы из v0 и их начальные метки +? остались без изменения. При рассмотренном ходе алгоритма массив PR будет содержать следующие номера вершин : PR[v0] = 0, PR[v1] = 0, PR[v2] = 0, PR [v3] = 0, PR[v4] = 2.

Для остальных вершин соответствующие значения не определены, поскольку они не «посещались».

Используя массив PR, восстановим кратчайший путь из вершины v0 в вершину v4. Поскольку PR[v4] = 2, а PR[v2] = 0, искомый путь есть v0, v2, v4.

ЗАКЛЮЧЕНИЕ

Современное состояние и тенденции развития вычислительной техники как основного инструмента информатики таковы, что наряду с увеличением функциональности вычислительная техника приобретает свойства, позволяющие работать на ней пользователю, не разбирающемуся в программировании. В этот период появился более качественный интерфейс программ. Появились структуры графических данных и более крупные, интегральные информационные единицы - объекты. Следствием стало бурное развитие объектно-ориентированных систем программирования, таких как Visual C++, Visual BASIC и других, в основе которых лежит обработка объектных структур данных. Также появились новые языки программирования ADA, OCCAM.([3]) И если раньше большой популярностью пользовались простые линейные алгоритмы то в настоящее время алгоритмы таких типов как деревья, графы, списки, очереди - получают все большее распространение.

Названные алгоритмы могут найти свои применения в программах для транспортных и коммуникационных сетей, таких как: железнодорожной транспортной сети, где вершины - станции, связи - дороги, таксомоторная сеть: вершины - места стоянки автомобилей, связи - пути подъезда; перемещение потока вещества по системе труб в определенный пункт назначения и т.д. На основе алгоритма поиска в ширину в графе можно построить программу вывода дерева наименьшей стоимости, что позволит рассчитывать кратчайшие пути к определенному месту назначения (вершине)

Таким образом, развитие информационных технологий, их проникновение во все области жизнедеятельности человека требуют компьютерного отображения информации в виде соответствующих структур данных. И графы, являясь одной из частей этих структур данных, играют важную роль в современном программировании, графы встречаются в сотнях разных задач.Размещено на Allbest.ru