Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Алгоритмы поиска в графе. Поиск в глубину и в ширину. Классификация рёбер

Технический Университет Молдовы

Факультет Вычислительной техники, Информатики и Микроэлектроники

Кафедра Информационных Технологий

Курсовая работа

на тему:

Алгоритмы поиска в графе.

Поиск в глубину и в ширину.

Классификация рёбер.

Выполнил: ст. гр. С-114 Келембет Т.

Проверил: Фалько Н.С.

Кишинёв 2012

Введение.

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

Начало теории графов единодушно относят к 1736 г., когда Л.Эйлер не только решил популярную в то время задачу о кенигсберских мостах, но и нашел критерий существования в графе специального маршрута ( эйлерова цикла, как его теперь называют ). Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине 19 века инженер - электрик Г.Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А.Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев. К тому же периоду относится появление знаменитой проблемы четырех красок.

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

Основные понятия и определения

Термин "граф" впервые появился в книге выдающегося венгерского математика Д.Кенига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (18 век).

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

G(V,E) =

, V ¹ Æ, E Í V ´ V

Если в элементах множества E допускается перестановка вершин, тогда граф называется неориентированным.

Пусть v₁ и v₂ - вершины, е = (v₁, v₂) - соединяющее их ребро. Тогда вершина v₁и ребро е инцидентны, вершина v₂ и ребро е также инцидентны. Ребра, инцидентные одной и той же вершине, называются смежными. Две вершины, инцидентные одному ребру, также называются смежными.

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

Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.

На рис. 1 приведен пример диаграммы графа, имеющего четыре вершины и четыре ребра. В этом графе вершины v₁ и v₂, v₂ и v₃, v₄ и v₁, v₂ и v₄ смежны, а вершины v₁ и v₃, v₃ и v₄ не смежны. Смежные ребра: е₁и е₂, е₂ и е₃, е₁ и е₃, е₄и е₁, е₄и е₃. Несмежные ребра: е₂ и е₄.

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

Рис.1

Часть графа G ( V, E) - это такой граф G' (V',E'), что V' Í V, E' Í E.

Подграфом графа G ( V, E) называется такая его часть G' (V',E'), которая вместе со всякой парой вершин содержит и ребро, если только оно есть в G ( V, E).

Если V' = V, то G' (V',E') называется остовным подграфом G ( V, E).

Путем (маршрутом) в графе называется чередующаяся последовательность вершин и ребер

v_0, e₁, v₁, e₂, v₂, …, e_k, v_k,

в которой любые два соседних элемента инцидентны.

Длиной пути называется количество ребер в нем ( с повторениями). Если путь М = v_0,e₁, v₁, e₂, v₂, …, e_k, v_k, то длина М равна k ( обозначается | М | = k.

Если v₀= v_k, то путь замкнут.

Если все ребра различны, то путь называется цепью. Если все вершины ( а значит и ребра) различны, то путь называется простой цепью.

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

Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины.

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

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

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

Дополнением простого графа G называется граф G' , имеющий те же вершины, а его ребра являются дополнением G до полного графа.

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

Пример дерева

Рис.2

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

Пустой граф (дерево) - это граф с пустым множеством вершин.

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

Рис. 3

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

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

Корневое дерево - это связный орграф без циклов, удовлетворяющий следующим условиям:

а). имеется ровно одна вершина, называемая корнем, к которой не ведет ни одна дуга;

б). к каждой вершине, отличной от корня, ведет ровно одна дуга;

в). преемники всякой вершины упорядочены.

Вершины корневого дерева, не имеющие преемников, называются листьям

Рис. 4

Способы задания графов

Существует три основных способа дискретного задания графа:

1). Матрица инцидентности;

2). Матрица смежности;

3). Список смежности ( инцидентности );

Рассмотрим подробнее каждый из этих способов задания графа:

Матрица инцидентности графа

Матрицей инцидентности для неориентированного графа с n вершинами и m ребрами называется матрица , строки которой соответствуют ребрам, а столбцы - вершинам.

Элементы

Матрицей инцидентности для ориентированного графа с n вершинами и m ребрами называется матрица , строки которой соответствуют ребрам, а столбцы - вершинам.

Элементы

Например, для неориентированного графа на рис.1 матрица инцидентности

имеет следующий вид (рис. 5):

	v₁	v₂	v₃	v₄
е₁	1	1	0	0
е₂	0	1	1	0
е₃	0	1	0	1
е₄	1	0	0	1

Рис. 5

Для ориентированного графа на рис. 3 матрица инцидентности

имеет следующий вид (рис. 6):

	v₁	v₂	v₃	v₄
e₁	-1	1	0	0
e₂	0	-1	1	0
e₃	-1	0	1	0
e₄	-1	0	0	1
e₅	0	0	1	-1

Рис. 6

Как легко можно заметить, этот способ задания графа довольно неэффективен: каждая строка такой матрицы содержит только 2 ячейки с ненулевыми значениями ( очевидно, так как одно ребро (дуга) может быть инцидентно не более чем двум вершинам). В результате мы имеем довольно неэкономное использование оперативной памяти ЭВМ.

Типичный пример задания матрицы инцидентности на языке Pascal - при помощи двумерного массива m на n:

Matr_Ints: array [1..LinksCount, 1..TopsCount] of integer;

Матрица смежности графа

Матрицей смежности неориентированного графа с n вершинами называется матрица , в которой

Например, для неориентированного графа на рис.1 матрица смежности

имеет следующий вид (рис. 7):

	v₁	v₂	v₃	v₄
v₁	0	1	0	1
v₂	1	0	1	1
v₃	0	1	0	0
v₄	1	1	0	0

Рис. 7

Матрицей смежности ориентированного графа с n вершинами называется матрица , в которой

Например, для ориентированного графа на рис. 3 матрица смежности имеет следующий вид (рис. 8):

	v₁	v₂	v₃	v₄
v₁	0	1	1	1
v₂	0	0	1	0
v₃	0	0	0	0
v₄	0	0	1	0

Рис. 8

При более подробном рассмотрении можно заметить, что в случае графа без петель матрица смежности имеет ряд особенностей:

во-первых, главная диагональ матрицы всегда заполнена нулями, так как вершина не может быть смежна сама себе;

во-вторых, если наш граф неориентированный - то часть матрицы под главной диагональю и над ней абсолютно идентичны.

Петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом.

На Pascal-е матрица смежности, как и матрица инцидентности чаще всего задается при помощи двумерного массива:

Matr_Sm :array [1..TopsCount,1..TopsCount] of byte,

либо

Matr_Sm :array [1..TopsCount,1..TopsCount] of boolean;

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

Список смежности

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

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

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

Пусть задан граф на n вершинах и требуется создать некоторую структуру переменных в памяти ЭВМ, отображающую список смежности, составленный для данного графа. Для начала выясним, что будет представлять собой данная структура. Так как строка списка содержит номера вершин, то естественно предположить, что мы должны иметь некоторую цепочку динамических переменных целочисленного типа, связанных между собой. Такая связь обеспечивается использованием указателей, обьединенных вместе с целочисленной переменной в запись ( Pascal: record ). Для того, чтобы обеспечить хранение входных указателей в такие цепочки, используется одномерный массив указателей, имеющий длину, равную количеству вершин графа. Признаком конца цепочки можно использовать какое либо значение, не допускаемое при нумерации вершин ( например - "0" ), занесенное в целочисленную переменную последнего блока. Например, для ориентированного графа на рис. 4 список смежности имеет следующий вид :

1 - 2,3,4,0

2 - 3,0

3 - 0

4 - 3,0

Такой список будет представляться в памяти ЭВМ следующим образом (Рис. 9):

массив указателей динамические переменные

на входы в цепочки. состоящие из указателя и

целочисленной переменной.

Рис. 9

Для создания такой структуры предварительно необходимо сделать объявления такого рода:

Type

BlockPtr = ^BlockType;

BlockType = record

Number :integer;

Point :BlockPtr;

end;

Var In_Ptr :array [1..TopsCount] of BlockPtr;

Создание цепочки в памяти осуществляется при вводе списка смежности при помощи процедуры New (BlockPtr_Type_Variable), где BlockPtr_Type_Variable - переменная типа BlockPtr.

Поиск в графе.

Алгоритм поиска в глубину.

Структуры данных:

списки

Каждый тип списков определяет множество конечных последовательностей элементов, имеющий заданный базисный тип. Число элементов списка, называемое его длиной, в разных списках одного типа может быть различным. Список, не имеющий элементов, называется пустым. Для списка определены понятия начального, конечного и текущего элементов, а также следующего и предыдущего элементов по отношению к текущему. Текущий элемент - это тот единственный элемент списка, который в данный доступен для обработки.

очередь

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

Набор базисных операций над списками, являющимися очередями, состоит из четырех операций:

1) Создание пустой очереди;

2) Проверка очереди на пустоту;

3) Выборки первого элемента из очереди с одновременным его удалением;

4) Занесения некоторого значения базисного типа в качестве нового последнего элемента очереди.

стек

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

Набор базисных операций над списками, являющимися стеками, состоит из пяти операций:

1) Создание пустого стека;

2) Проверка стека на пустоту;

3,4) Выборки последнего элемента из стека без удаления его из стека или с его удалением;

5) Занесения некоторого значения базисного типа в качестве нового последнего элемента стека.

деревья

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

Набор базисных операций для деревьев состоит из следующих операций : Создание тривиального дерева по элементу базисного типа и выборки или замены корня дерева или списка его поддеревьев, а также всех операций (для списка поддеревьев), которые являются базисными для списка.

Обход графа в глубину

При обходе дерева в глубину (известном также как прохождение в прямом порядке) вершины дерева посещаются в соответствии со следующей рекурсивной процедурой: сначала посетить корень дерева q; затем если корень рассматриваемого дерева не является листом, то для каждого сына p корня q рекурсивно обратиться к процедуре обхода в глубину для того, чтобы обойти все поддеревья с корнями p в порядке упорядоченности вершин p как сыновей корня q. Если использовать стек S для хранения текущего пути по дереву, т.е. пути, который начинается в корне дерева и кончается в вершине, посещаемой в данный момент, то можно построить нерекурсивный алгоритм для обхода дерева в глубину:

Посетить корень дерева и поместить его в пустой стек S;

WHILE стек S не является пустым DO

BEGIN

пусть p - вершина, находящаяся на верху стека S;

IF сыновья вершины p еще не посещались

THEN посетить старшего сына вершины p и поместить его в

стек S

ELSE BEGIN

удалить вершину p из стека S

IF p имеет братьев THEN посетить брата вершины p и

поместить его в стек S

END

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

WHILE имеется хотя бы одна не посещенная вершина DO

BEGIN

пусть p - первая (т.е. минимальная) из не посещенных вершин;

посетить вершину p и поместить ее в пустой стек S;

WHILE стек S не пуст DO

BEGIN

пусть p - вершина, находящаяся на верхушке стека S;

IF у вершины p есть не посещенные смежные вершины

THEN BEGIN

пусть q - первая не посещенная вершина из вершин,

смежных вершине p;

пройти по ребру (p,q), посетить вершину q и

поместить ее в стек S;

END

ELSE удалить вершину p из стека S

END

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

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

Поместить в стек исходную вершину графа и пометить ее;

WHILE стек не пуст DO

BEGIN

извлечь вершину из стека;

IF есть непомеченные вершины и смежные с данной

THEN пометить их и загрузить в стек;

END

Алгоритм поиска в ширину.

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

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

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

Взять пустые очереди O1 и O2;

Поместить корень в очередь O1;

WHILE одна из очередей O1 и O2 не пуста DO

IF O1 не является пустой THEN

BEGIN

пусть p - вершина, находящаяся в голове очереди O1;

посетить вершину p и удалить ее из O1;

поместить всех сыновей вершины p в очередь O2, начиная со

старшего сына;

END

ELSE в качестве O1 взять непустую очередь O2, а в качестве

O2 взять пустую очередь O1;

Следует заметить, что обход дерева поиска в ширину позволяет обходить дерево поиска одновременно с его построением. Таким образом, можно решать задачу нахождения какого-нибудь решения в форме вектора (а1, а2, ...) неизвестной длины (не зная r), если только известно, что существует конечное решение задачи.

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

Алгоритм обхода графа в ширину:

Взять две пустые очереди O1 и O2;

Поместить исходную вершину в очередь O1 и пометить ее;

WHILE очередь O1 не пуста DO

BEGIN

посетить вершину в голове очереди O1 и удалить ее из очереди;

IF вершины непомечены и смежны с данной

THEN поместить их в очередь O2;

END

Классификация рёбер графа

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

Алгоритмы поиска в графе. Поиск в глубину и в ширину. Классификация рёбер 📙 Курсовая → 🆔 6388