Лекции по информатике (984119), страница 11
Текст из файла (страница 11)
Две вершины называются смежными, если в графе есть ребро, соединяющее эти вершины. 298 Говорят, что в графе существует путь из вершины А в вершину В, если найдется такая последовательность всрп<ии Ад, А2,..., А„такая, что Ад — — А, А„= ЕЗ и Чъ' = 1,...,и — 1 верн<ивы А;, А; > являются смежными (т. е. А, и А,, < соединены ребром). Путь называется ггХ>осадим, если на нем все промежуточные верн>ины А2,..., А„> попарно различны, Граф называется с«лз><ь<м, если имеется путь между любыми двумя вершинами графа. ХХиклом называется простой путь длины не менее 3 от какой-либо вершины до нее самой (т.
е. путь, более сложный, чем движение по некоторой дуге и возврат обратно по этой же дуге). Ориентированным графом называется граф, каждому ребру которого приписано определенное направление (ребро в ориентированном графе называется дугой). Говорят, что в ориентированном графе существует путь из вершины Л в вершину В, если найдется такая последовательность вершин А,, А2,..., А„, причем А, = А, А„= В и >Хг' = 1.... < и, — 1 существует дуга из вершины А, в вершину А,, (т. е. путь по дугам с учетом их направления). Подробно теория графов рассматривается в курсе дискретной математики. Здесь же отметим, что в программировании задачи с использованием теории графов возникают достаточно часто, например,в задачах проектирования электрических схем, в системах искусственного интеллекта.
Одна из основных проблем, возника<ощих щ>и использовании графов, связана с поискоъ< путей между вершинаъли. Рассмотрим способы представления графов в памяти ЭВМ, обеспечивающие достаточно удобные возможности решения этой проблемы. Граф представляется матрицей смежности. Пусть граф содержит << вершин. Тогда матрицей смежности называется квадратная булевская матрица ЛХ размерности /с х А, в которой значения элементов определены так: ЛХ< = Ха1ве, если нет ребра, соеди<тающего г-тую вершину с >чтой, и <1Х,> — — багие в противном случае. Для неориентированных графов матрица см<ъжности симметрична. Для ориентированного графа элемент ЛХ, матрицы смежности равен багие тогда и только тогда, когда граф содержит лугу, начинаюп<ук>ся в г-той вершине и оканчивающуюся в чтой вершине.
Для нахождения путей в графе используют операции над матрицами смежности. Произведение и сумма булевских матриц опрсделян>тся так же, как и дпя обычных матриц, только вместо умножения и сложения чис<л используются булевские операции Й («и ) и Ч («илия), соответственно. По аналогии с обычными числовыми матрипами определяется степень булевской матрицы. С праведливо утверждение, что в графе с ъ. ;вершинами и матрицей смежности М существует путь из вершины номер ъ к вершине номер > тогда и только тогда, когда в матрице ЛХ+ элемент ЛХ,.' истинен. Матрица определяется как Признаком цикла лля вершины номер ъ' в ориентированном графе служит истинное значение элемента ЛХ ' (г, г). Для получения значения матрицы ЛХ+ необходимо вычислить булевский матрочлен за 0(<У~) шагов. Эффективный алгоритм вычисления матрицы ЛХ (алгоритм Уоршалла) опи<.'ан в книгах ~70, 77.
36~. Его сложностная оценка есть 0(Л'а). Граф с Й вер)пинами можно представить с помощью 1; списков, каждый из которых соответствует вершине графа и содержи"г номера ес смежных вершин. Указатели этих списков размещаются в одном массиве. Для представления графа можно воспользоваться одномерным массивом целых чисел. Обозна~<им этОт массив идентификатором А. П<.'рвы<'. Й элем<'.нтов массива А содерж))т индек<)ы эл«м<'.нтОВ массиВа, <' кОтОрых на'1инаются НОследОВательнОсти нОмерОВ ВС1>Н1ин, смежных с данной, а начиная с 1) -~- 1 элеЕмента массива А подряд размещав)тся сами последовательности ном<)ров Верн)ин. В начал< каждой последовательности указывается число смежных вершин, а потом перечисляются их номера. Так для г-той ве1нпины А[г) индекс описания вершины номер г в массиве А.
Обозначим 1> = А(г]. Тогда А(Р) - число вершин, смежных с г-той, а элементы А(Р + 1),..., А(Р+ А(Р)) задают их номера. Граф с 1< вершинами можно представить целочисленным ма< сивом из 1> столбцов и т строк, где и -- максимальное число вершин, смежных с произвольной вершиной графа. Элементы столбца матрицы содер>кат номера смежных верн<ни.
Если у вершины меньше, чем т. ребер, то последние э><ементы столбца за<юлняются нулями. Этот способ удобен в случаях. когда в графе у большинства вершин одинаковое или почти одинаковое число смежных вершин, равное или близкое к т, и число т, существенно меньше /с. Если граф меняется в процессе обработки, т. е. добавляются и удаляются вершины и дуги, то удобно использовать списки. Граф описывается с помощью основного списка вершин и списков дуг. В основной список включены узлы для каждой вершины графа. С каждам узлом основного списка связан свой список дуг. Каждый узел списка дуг содержит указатель на узел основного списка, в который входит соответствующая дуга.
На рисунке показан граф и его представление с помощью списков. Для того, чтобы избавиться от мпогочисле)шых пересечений стрелок. на этом рисунке в представлении узлов для дуг вместо стрелок, веду)цих к вершинам, поставлены имена вершин. В Слева граф, справа его представление: над узлами основного списка проставлены названия вершин, а в узлах списков дуг вместо стрелок записаны имена вершин ~44~. 300 5.12.1 Алгоритмы на графах 5.12.1.1 Поиск в глубину Реализация поиска в графе в глу.бину отличается от поиска в дереве тем, то при всякой попытке перейти в новую вершину осуществляется проверка, была ли посещена уоке эта вершина.
Это связано с тем, что в графе, в отличие от дерева, могут быть циклы и петли, в силу чего «наивный» алгоритм просто зациклится. ргоигаш ВерС1гБеагс1эГЭегпоСшрпС, опСрпС): 1' Граф представляется в вээде матрицьг смеоюпости 3 Суре Сгарй аггау ~1..5, 1..5~ о1 Ьоо1еап; / Пугаг в графе — последовательность !список) версиин, ) Суре РаСЬ вЂ” 1лзС 1' о! 1аСедег ): ргосес1пге Сгеасс(чаг 1: Расй); Сппссюп Р1гвс(чаг 1: Рас1э): 1сегасог: Сппссюп 1.авсСчаг 1: Расй); 1сегасог; Гппссюп 1пвегС(чаг1; Рас1ц чаг ~: !сегасог; 1: шсеиег): 1Сегасог; Сппссюп Гэе!есеСчаг 1: РаС1э, чаг 1: 1сегасог): 1сегаСог: ргосес1пге Лезсгоу(чаг 1: Расй); Сппсс1оп ХосЕс1па1(айаг 11эа„г1те: 1сегасог): Ьоо1еап; 1' Описание итератора слегка изменено для удобства: функция, а не проиедура ) Сппссюп ХехСлаг 1: 1СегаСог): 1Сегаиэг; 1' Аналогично орегаСог —,' — ' в ЯТ1 для зИ:: 1гзС<Т'.-::ИегаСог ) Сппссюп РгечСчаг 1: 1Сегасог): 1СегаСог; Сппссюп ГеСссэ!чаг 1: 1СегаСог): шсеиег; Объявление ~тд заимсгпвовано из ЬТ1л 180« 1ЕС 14882:1998(Е), р.,Ц6 ) Сппсс1оп йпг1СйгвС, 1азс: !СегаСог: чаг х: шсеиег): 1СегаСог; чаг 1оппс1: Ьоо1еап; Ьеиш 1ошЫ: - Га1ве; жЫ1е поС 1ошэс1 апг! ХоСЕ«1па1(йгвС,!азС) с1о Ьенш 1С' Регсй( бгзС ) — х СЬеп Йэпш1: Сгпе:, епс1:, ЬЫ: й гас:, епс1; 1' Печать списка с последнего .элемента до первого 3 ргосес1пге ргшс(бгвс, 1аас: 1ссгасог); Ьефп итЬ1!е Х<эсЕ<1па1(ангес, 1аес) с1о Ьеи1п Ргеч( 1аас ); 301 ъът1Се(1гсгсЬ(1авг), епс1; мгг1Се1п; епс1; 1' Бер11гЯеагс1г ищет все нути в графе меогсду тУ и уоо1 и вглводит их но, пинать з~ ргосес1пге ВерСЬЯеагсЬ(1п11, доа1: шСедег: маг С: СгарЬ); тхаг Р; Раг1г; ргосес1пге веагсЬ; тгаг 1, 1с: шСедег; Ье~дп 1с: - ГегсЬ(Г1гвг(Ь)); 11 1с =- цоа1 СЬеп рг1пС(Г1гвС (Р), Ьавг(Р)) е1ве Сог 1:- 1 Со 5 с1о 11' С[1с, 1] апс1 ХоСЕс1па1(йг1с1(Г1гвС(Р), Ьавг(Р), 1), Ьавг(Р)) СЬеп Ьец1п 1пвега (Р, Гьгвс(Р), 1): 1' Вершины пути хранятся в обратном порядке для удобства програлслсирования Г' веагсЬ; с1е1еге (Р, Гп вС (Р) ): епс1; епс1 Ьедш Сгеаге(Р); гавсгг (Р, йгвг (Р), 1гпС); всагсЬ; !зевггоу(Р); епс1; айаг С: Сга1зЬ; : шСееег; Ьедш 1 Создание графа без дуг г Сог 1: -- 1 Со 5 с1о СЬг ]:-- 1 Со 5 с1о С[1, ]]:-- Ка1ве1 1' Добавим несколько дуг 3 С[1, 2]:-- Сгпе; С[1., 3]:-- Сгпе; С[2, 4]: — Сгпе; С]3, 2]: — — Сгпе; С[3, 5]:= Сгпе: С[4,.
3]: =- Сгпе; С[4, 5]: - Сгпе; ЬгерСЬЯеагсЬ(1, 5, С): епс1. 5.12.1.2 Поиск в ширину фшс1пс1е <говСгеагп> фшс1пс1е = 11вС> фшс1пс1е <с1пепе> фшс1пс1е <а1 ~ог1СЬпг> сопяС шС МАХ 5; вСс1::овСгеапй орегаСог«[вГс1:;овсгеагпй в, вСс1::ЬвС<шС> р) Гог[вСс1 с 1гвг <шС>::1СегаГог 1 -- р.1>ед1п[); 1 . 'р.епс1[); 1+ — ) и сс в - ' $1 геСпгп [в « вСс1пепс11); ,~,~' Источники: [57, 58] чоЫ Ьгеас1СЬ веагсЬ[Ьоо1 дгарЬ[МАХ][МАХ], шС ппг, шС яоа1) ( вСс1:: 11вС <шС> р[1, 1п1С); вСс1 и с1пепе<вгс1::11вС <шС» с1; с1.рпвЬ[р); Мп1е [! с1.епгрСу[) ) ( р -- с~ХгопС [); с1,рор[); шС ч.
р.Ьас1с[); Ям — — доа1) вгс1::сопг « р:, е1яе Гог[шС 1 -- О; 1 < МАХ; р Ь) ЖВ 1.Ь[ ]['] йй (вгсЬ:5 1(р.1еа [), 1., 1[), ) — - т. ° 1[))) ( р.рцвЬ Ьас1с[1); с1 1~~~в1г[р)' р.рор Ьас1с[); 1пС ша1п[тгоЫ) Ьоо1 фМАХ][МАХ] --= ((Га1яе, Сгпе, Сгпе, Га1яе. Га1яе), (Га1яе, Га1яе, Га1яе, Сгпе, Га1яе), (Са1яе, Сгпе, Га1яе, Га1яе, Сгпе), (Га1яе, Ха1яе, Сгпе, Са1яе, Сгпе), Глава 6 Сортировка и поиск 6.1 Алгоритмы поиска Одно из наиболее часто встречающихся в программировании действий поиск [65]. Эффективность поиска часто является основным критерием качества различных структур данных [54].
К классическим задачам поиска слова в тексте или отыскания данных в базах данных в последние годы добавились такие актуальшяе задачи, как поиск в интернете, антивирусное сканирование программного кода и антиспамовская фильтрация почтовых сообщений. Быстрый мпогокритериальный семантический поиск необходим лля очистки и анализа данных (с1ага гп1шпк) и в оперативно-розыскной деятельности спецслужб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
