Новиков Ф.А. Дискретная математика для программистов (860615), страница 53
Текст из файла (страница 53)
Если узел не связан сильно с другими, то считаем, что он сам образует КСС. Конденсацией G* орграфа G(или графом Герца, или фактор-графом) называется орграф, который получаетсястягиванием в один узел каждой КСС орграфа G.ПримерНа рис. 8.8 показаны диаграммы орграфа и его конденсации.8.5. Связность в орграфах283ЗАМЕЧАНИЕФактор-граф не содержит контуров.8.5.3. Выделение компонент сильной связностиСледующий алгоритм, основанный на методе поиска в глубину, находит всекомпоненты сильной связности орграфа.Алгоритм 8.2 Выделение компонент сильной связностиВход: орграф G(V, Е), заданный списками смежности Г(г>).Выход: список С компонент сильной связности, каждый элемент которого естьсписок узлов, входящих в компоненту сильной связности.С: = 0for v е V doM[v]: ={г>} { M[v] список узлов, входящих в ту же КСС, что и v }e[v]: = 0 { все узлы не рассмотрены }end forwhile V Ф 0 doselect v eV { взять v из V }v —» T { положить v в стек }e[v\: = 1 { отметить v }КСС { вызов процедуры КСС }end whileОсновная работа выполняется рекурсивной процедурой без параметров КСС, которая использует стек Т для хранения просматриваемых узлов.
Процедура КССвыделяет все компоненты сильной связности, достижимые из узла, выбранногов основном алгоритме,if Т = 0 thenreturn { негде выделять }end ifv: = top Т { v — верхний элемент стека}if Г [и] П V = 0 thenC: = CUM[v] { это КСС }V : — V — v { удалить узел }v <— Т { снять узел v со стека }КСС { возврат из тупика }elsefor и е r[v] doif е[и] = 0 thenи —> Т { положить узел и в стек }е[и]: = 1 { отметить узел и }elserepeatwТ { w — склеиваемый узел }V : = V - w { удалить узел }284Глава 8. СвязностьГ [и]: = Г[и] U F[w] { з а п о м н и т ь с м е ж н о с т ь }М[и]: = М[и] U M[w] { с к л е и в а н и е у з л о в }until и — ww —> Т { чтобы не убрать тот узел, }V : = V + w { с которого начали }end ifКСС { поиск в глубину }end forend ifДостаточно заметить, что любой контур принадлежит ровно однойКСС, и более того, если в КСС входит несколько узлов, то они обязательно принадлежат некоторым контурам.
Поэтому, если при обходе в глубину мы попадаемв уже отмеченный узел и, то это означает, что обнаружен контур, причём предшествующие узлы найденного контура находятся на стеке, начиная от вершиныстека и до рассматриваемого отмеченного узла и, который также присутствует встеке. Все узлы контура найденного контура можно «склеить». При склеиванииузла w его список смежности и список уже найденных узлов той КСС, которойпринадлежит узел w, объединяются с соответствующими списками узла и.
После этого можно продолжить поиск в глубину от узла и, который для этой целиследует оставить в стеке.•ОБОСНОВАНИЕ8.6. Кратчайшие путиЗадача нахождения кратчайшего пути в графе имеет столько практических применений и интерпретаций, что читатель, без сомнения, может сам легко привестимножество примеров. Здесь рассматриваются четыре классических алгоритма,которые обязан знать каждый программист.8.6.1.
Длина дугАлгоритм Уоршалла (алгоритм 1.11) позволяет ответить па вопрос, достижимали вершина v из вершины и, то есть существует ли цепь (u,v). Часто нужно нетолько определить, существует ли цепь, по и найти эту цепь.Если задай орграф G(V, Е), в котором дуги нагружены числами (эти числа обычно называют весами, или длинами, дуг), то этот орграф можно представить в видематрицы весов (длин) С:{О,для г = j,Cij, конечная величина, если есть дуга из узла i в узел j,оо, если нет дуги из узла г в узел j.Длиной пути называется сумма длин дуг, входящих в этот путь.
Наиболее частопа практике встречается задача отыскания кратчайшего пути.ЗАМЕЧАНИЕДанное представление, равно как и последующие алгоритмы, применимы как к графам,так и к орграфам.8.6. Кратчайшие пути2858.6.2. Алгоритм ФлойдаАлгоритм Флойда 1 находит кратчайшие пути между всеми парами вершин (узлов) в (ор)графе. В этом алгоритме для хранения информации о путях используется матрица Н: array [l..p, 1 ..р] of 1 ..р, гдеjju1 — I е с л и ^ — п е Р в а я вершина, достигаемая на кратчайшем пути из i в j\1 0, если из вершины г в вершину j нет пути.Алгоритм 8.3 Алгоритм ФлойдаВход: матрица С[1..р, 1..р] длин дуг.Выход: матрица Т[1..р, 1 ..р] длин путей и матрица Я[1..р, 1 ..р] самих путей,for i from 1 to p dofor j from 1 to p doT[i,j]:—C[i,j]{ инициализация }if C[i,j] = oo thenH[i, j]: = 0 { пет дуги из i в j }elseH[i,j]: = j { есть дуга из i в j }end ifend forend forfor i from 1 to p dofor j from 1 to p dofor к from 1 to p doif i ф j & T[j, i] ф oo к г ф к к Т[г, к] ф оо к (T[j, к] = оо V T[j, к] >> T[j,i]+ T[i,k])thenH[j, к]: = H[j, i] { запомнить новый путь }T[j, к]: = T\j, г] + T[i, к] { и его длину }end ifend forend forfor j from 1 to p doif T[jJ] < 0 thenstop { пет решения: вершина j входит в цикл отрицательной длины }end ifend forend forОТСТУПЛЕНИЕМатрица H размера 0 ( р 2 ) хранит информацию обо всех (кратчайших) путях в графе.Заметим, что всего в графе 0(р2) путей, состоящих из 0(р) вершин.
Таким образом, непосредственное представление всех путей потребовало бы памяти объема 0(р3). Экономияпамяти достигается за счет интерпретации представления, то есть динамического вычисления некоторой части информации вместо её хранения в памяти. В данном случае любойконкретный путь (и, v) легко извлекается из матрицы с помощью следующего алгоритма.1Роберт Флойд (1936-2001).286w:=u;Глава 8. Связностьyield w { первая вершина }while w ф v dow : = H[w, v]\ yield w { следующая вершина }end whileЗАМЕЧАНИЕЕсли в G есть цикл с отрицательным весом, то решения поставленной задачи не существует, так как па этом цикле можно «накручивать» сколь угодно короткий путь.Алгоритм Флойда имеет много общего с алгоритмом Уоршалла(алгоритм 1.11).
Покажем по индукции, что после выполнения г-го шага основного цикла по г элементы матриц T[j, к] и H[j, к] содержат, соответственно, длинукратчайшего пути и первую вершину па кратчайшем пути из вершины j в вершину к, проходящем через промежуточные вершины из диапазона 1.Л. База:i = 0, то есть до начала цикла элементы матриц Т и Я содержат информацию о кратчайших путях (если таковые есть), пе проходящих ни через какиепромежуточные вершины. Пусть теперь перед началом выполнения тела циклана г-м шаге T[j, к] содержит длину кратчайшего пути от j к к, a H[j, /с] содержитпервую вершину па кратчайшем пути из вершины j в вершину к (если таковой есть).
В таком случае, если в результате добавления вершины г к диапазонупромежуточных вершин находится более короткий путь (в частности, если этовообще первый найденный путь), то он записывается. Таким образом, после окончания цикла, когда i = р, матрицы содержат кратчайшие пути, проходящие черезпромежуточные вершины 1 ..р, то есть искомые кратчайшие пути. Алгоритм невсегда выдаёт решение, поскольку оно пе всегда существует. Дополнительныйцикл по j служит для прекращения работы в случае обнаружения в графе циклас отрицательным весом.•ОБОСНОВАНИЕ8.6.3. Алгоритм ДейкстрыАлгоритм Дейкстры 1 находит кратчайший путь между двумя данными вершинами (узлами) в (ор)графе, если длины дуг неотрицательны.Алгоритм 8.4 Алгоритм ДейкстрыВход: орграф G(V, Е), заданный матрицей длин дуг С : array [1 ..р, l..p] of real;s и t — вершины графа.Выход: векторы Т : array [l..p] of real; и Я : array [l..p] of 0..р.
Если вершина vлежит на кратчайшем пути от s к t, то T[v] — длина кратчайшего пути от s кv; H[v] — вершина, непосредственно предшествующая v на кратчайшем пути,for v from 1 to р doT[v]: = оо { кратчайший путь неизвестен }X[v]: = 0 { все вершины не отмечены }end for1Эдсгер Дейкстра (1930-2002).2878.6. Кратчайшие путиH[s]: = 0 { s ничего не предшествует }T[s]: = 0 { кратчайший путь имеет длину 0...}X[s]: = 1 { ... и он известен }v: = s { текущая вершина }М: { обновление пометок }for и е Г(и) doif Х[и] = 0 к Т[и] > T[v] + C[v, и] thenТ[и]: = T[v] + C[v, и] { найден более короткий путь из s в и через v }H[u]:—v { запоминаем его }end ifend form : = oo; v : = 0{ поиск конца кратчайшего пути }for и from 1 to p doif X[u] = 0 к T[u] < m thenv: = u;m: = T[u] { вершина v заканчивает кратчайший путь из s }end ifend forif v = 0 thenstop { нет пути из s в t }end ifif v = t thenstop { найден кратчайший путь из s в t }end ifX[v]: = l { найден кратчайший путь из s в v }goto MЗАМЕЧАНИЕДля применимости алгоритма Дейкстры достаточно выполнения неравенства треугольника::Vu, v, w € V (d(u, v) ^ d(u, w) + d(w, v ) ) ,которое, очевидно, выполняется, если длины дуг неотрицательны.
Если же допускаютсяотрицательные длины дуг, то алгоритм Дейкстры может оказаться неприменимым. Например, в графе с тремя узлами s, t и и, если C[s,t) = 2, C[s,u] = 3 и C[u,t] = —2,алгоритм 8.4 не найдет кратчайшего пути длиной 1 и выдаст путь длиной 2.Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М,в качестве v используется вершина, для которой известен кратчайший путь извершины s. Другими словами, если X[v] = 1, то T[v) = d(s,v), и все вершины напути (s,v), определяемом вектором Н, обладают тем же свойством, то естьОБОСНОВАНИЕVu (Х[и] = 1Т[и) = d(s, и) к Х[Н[и\) = 1).288Глава 8. СвязностьДействительно (по индукции), первый раз в качестве v используется вершина s,для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны).
Пусть Т[и] = d(s,u)для всех ранее помеченных вершин и. Рассмотрим вновь помеченную вершину v, которая выбрана из условия T[v] — min Т[и]. Заметим, что если известенX[ti]=0путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что T[v] > d(s,v), то есть найденный путь,ведущий из s в v, не является кратчайшим. Тогда на этом пути должны бытьнепомеченные вершины. Рассмотрим первую вершину w на этом пути, такую,что X[w] = 0. Имеем: T[w\ = d(s,w) ^ d(s,v) < T[v], что противоречит выборувершины v.•ЗАМЕЧАНИЕИзвестно, что применение алгоритма Флойда в среднем примерно вдвое менее трудоёмко,чем применение алгоритма Дейкстры для всех пар вершин.8.6.4.
Дерево кратчайших путейАлгоритм Дейкстры можно использовать и в том случае, когда нужно найтикратчайшие цепи (пути) от вершины s до всех остальных вершин.ЗАМЕЧАНИЕВ предыдущем подразделе мы отметили, что алгоритм Дейкстры применим как к графам,так и к орграфам в равной мере. Действительно, в этом алгоритме достаточно знать, какиевершины (узлы) являются соседними и какова цена (длина) перехода. Для графа матрицадлин С и отношение смежности Г симметричны, для орграфа это пе так, но для работы алгоритма Дейкстры данное обстоятельство не имеет значения. Таким образом, алгоритм 8.5,равно как и предшествующий, применим как к графам, так и к орграфам. Именно поэтому в этом разделе мы позволяем себе вольности, используя в одном контексте термины,относящиеся к графам («вершина») и к орграфам («путь»).Если достаточно знать только длины путей и все вершины достижимы из s, а длины дуг положительны, то алгоритм можно записать в следующей компактной инаглядной форме.Алгоритм 8.5 Алгоритм Дейкстры для вычисления дерева кратчайших путейВход: орграф G(V, Е), заданный матрицей длин дуг С : array [l..p, l..p] of real исписками смежности Г; s — исходная вершина графа.Выход: вектор Т : array [l..p] of real длин кратчайших путей от s.for и е V doТ[и]: =C[s,u] { начальное приближение определяется матрицей }Х[и\: = 0 { все вершины пе отмечены }8.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
