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

DFS [А) DFSm V W

DFS (6)

RETURN RETURN

RETURN RETURN

Рис. 3.5.4. Содержимое стека при реализации алгоритма DFS.

от данной вершины к первой непросмотренной вершине, DPS достигает нижней вершины дерева самым быстрым из возможных способов. Видно, что на рис. 3.5.6 у дерева T(G) ровно в два раза больше ребер, чем у G, и каждое ребро сети G встречается дважды в T(G).

Доказательство правильности алгоритма DPS может быть основано на следующих замечаниях:

1. Ребро прибавляется к Т только в том случае, если одна из его двух вершин еще не просмотрена. Это означает, что Т не может содержать цикла.

2. Если каждая из М-I вершин, отличных от начальной вершины, на самом деле проверена, то к Т прибавляется М-1 ребер.

3. Остовное дерево Т в сети G с М вершинами состоит из М-1 ребер, не образующих цикла.

С помощью этих замечаний вы можете попробовать построить доказательство правильности алгоритма DPS.

Завершим обсуждение алгоритма DPS анализом его сложности. Число операций, необходимых при работе алгоритма с сетью G= (V, Е), есть 0{}Е\), т. е. линейная функция от числа ребер в сети. Это следует из того факта, что алгоритм проходит каждое ребро G дважды и обработка любого ребра требует не больше 12 шагов. Также заметим, что к DPS производится в точности 1 V\ обращений.

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

PR06RftH SPftN tINPOT»OUTPUT,TAPE5iINPUTiTftPE6=0UTPUTI

С ЭТА ПРОГРАММА НАХОДИТ ОСТОВНОЕ ДЕРЕВО В НЕВЗВЕШЕННОЙ СЕТИ G. С ОНА ИЛЛЮСТРИРУЕТ ПРЕДСТАВЛЕНИЕ СЕТИ СВЯЗАННЫМ СПИСКОМ И, С В ПОДПРОГРАММЕ DFS, ИСПОЛЬЗОВАНИЕ СТЕКА КАК СРЕДСТ8А С РЕАЛИЗА11КИ РЕКУРСИВНОГО АЛГОРИТМА НА ФОРТРАНЕ. С

с ПЕРЕМЕННАЯ. ОПИСАНИЕ

С ADJ (К) МАССИВЫ ДЛЯ ЗАПОМИНАНИЯ Р СВЯЗАННЫХ СПИСКОВ

С MEXTIK) ВЕРШИН, СМЕ)НЫХ С ДАННОЙ. ДЛЯ 1 .LE. К .LE.P

С ADJ(K> = О, И ЕСЛИ J = NEXT(K), ТОГДА ADJ(J)-nEPBAB

d ВЕРШИНА, СМЕЖНАЯ С К. СЛЕДУЮЩАЯ ВЕРШИНА,

С СМЕЖНАЯ С К, СОДЕРЖИТСЯ В ADJ QNEXTCJ)), .И Т.Д.

С TPEE(Jill J-E РЕБРО, ВЫБРАННОЕ ДЛЯ ОСТОВНОГО ДЕРЕВА.

С TREE(Ji2)

С р «I число ВЕРШИН И РЕБЕР, СООТВЕТСТВЕННО, В С.

С ВЕРШИНЫ G ПОМЕЧЕНЫ 1, 2, .... Р.

.с Ui U РЕБРО В е МЕЖДУ ВЕРШИНАМИ UHV.

с WORDS WORDS = Р + Z*tt, ЧИСЛО СЛОВ ПАМЯТИ ДЛЯ МАССИВОВ

С AOJ П NEXT.

С"

INTEGER Р. Qt Т« и. М, VOROS

INTEGER ADJdOOOli NEXTllOOOli TREE(100i2)

С СЧИТЫВАНИБ ЧИСЛА ВЕРШИН И РЕБЕР 6.

READ(S«1000» P«Q 1000 FORMAT

I = Р + 1

uoRDs = p t г « ct

с ИНИЦИАЛИЗАЦИЯ МАССИеОВ ADJ и NEXT.

DO ЮО И = It Р ADJ(n) = О NEXTtH! = О 100 CONTINUE

с СЧИТЫВАНИЕ й РЕБЕР 6 И ОРГАНИЗАЦИЯ СВЯЗАННОГО .СПИСКА.

00 гой N = It а

READ (StlOOOl U,V NEXTCII ч NEXT(U> ADJdl s V UEXTIU) я I 1 = 1*1 WEXTdl = HEXTJV) ADJdl = и

. WEXT(V» = I 1 = 1 + 1 200 CONTINUE

С ВЫЗОВ DFS ДЛЯ НАХОЖДЕНИЯ ОСТОВНОГО ДбРЕВА G,

С НАЧИНЯЯ С V=l. DFS ПОМЕСТИТ РЕБРА ОСТОВНОГО ДЕРЕВА

С В МАССИВ TREE.

CAUU DFs f AOJt NEXTt It TREEt Pt WORDSt T ) С ПЕЧАТЬ СЕТИ Q И ОСТОВНОГО ДЕРЕВА е.

Рис. 3.5.5. Реализация алгоритма DFS на Фортране. (Текст в операторе 2000: «Представление списком сети G»; 2100: «Ребра остовного дерева»; 2300: «Заметим, что сеть не связная»; 1000: «Ошибка в подпрограмме DFS>>.)

WRITE (6i2000) (l.ADjdJ.NExTd). I = 1,WORDS) 2000 FORMAT t ХНИЗвН THE LIST REPRESENTATION OF NETWORK G > Л + 23H I ADJ NEXT </. { IHOt I8i lEi !£) )

write: (612100) 2100 FORMAT { 1H1,22H SPANfJINS TREE EDGES )

К = T - 1

WRITE (6f2200) (( TREEdiJIi J=l«2)i IsitK S 2200 FORMAT ( IHOi I10« I6 ) С •♦

IF I T ,E(J, P I STOP

WRITE {б«азоо)

2300 FORMAT { 1H1,41H NOTE THAT THE NETWORK IS NOT CONNECTED. )

STOP END

SUBROUTINE DFS С ADJ. NEXTi Ut TREE. Pi WORDS. T I

ПРИМЕНЕНИЕ РЕКУРСИВНОГО АЛГОРИТМА ТАРЬЯНА ПОИСКА В ГЛУБИНУ. DFS НАХОДИТ ОСТОВНОЕ ДЕРЕВО СВЯЗАННОЙ-НЕВЗВЕШЕННОИ СЕТИ G, ИМЕЮЩЕЙ Р .LE. 100 ВЕРШИН И й РЕБЕР. G ПРЕДСТАВЛЕНА СВЯЗАННЫМИ СПИСКАМИ, С ИСПОЛЬЗОВАНИЕМ МАССИВОВ AOJ(WOBOS) И NEXT (WORDS), ГДЕ WORDS = Р-Н 2*Q. DFS ПОМЕЩАЕТ ВЫБРАННЫЕ для ОСТОВНОГО ДЕРЕВА РЕБРА В МАССИВ TREE И НАЧИНАЕТ ПОИСК ОСТОВНОГО ДЕРЕВА В ВЕРШИНЕ V. ЕСЛИ G НЕ СВЯЗАНА, DFS НАЙДЕТ ОСТОВНОЕ ДЕРЕВО СВЯЗНОЙ КОМПОНЕНТЫ G, СОДЕРЖАЩЕЙ V. DFS МСЩЕЛИРУЕТ СТЕК, ЧТОБЫ РЕАЛИЗОВАТЬ РЕКУРСИНЗ В АЛГОРИТМЕ.

ПЕРЕМЕННАЯ ОПИСАНИЕ

V В ЛЮБОЙ МОМЕНТ РАССИАТТИВАЕМ ВЕРШИНУ V.

М СЛЕДУЮЩАЯ ВЕРШИНА, СМЕЖНАЯ С V.

VISIT(VI=I ОЗНАЧАЕТ, ЧТО V БЫЛА 1-Й ВЕРШИНОЙ, ПРОСМОТРЕННОЙ ВПЕРВЫЕ. VISIT(.V) = 0 ОЗНАЧАЕТ, ЧТО V ЕЩЕ НЕ ПРОСМОТРЕНА.

STORE СТЕКИСПОЛЬЗОВАН для ЗАПОМИНАНИЯ ПРОШЛОЙ

ПОСЛЕДОВАТЕЛЬНОСТИ ПРОСМОТРЕННЫХ ВЕРШИН. СТЕК НУЖЕН, ЧТОБЫ ЗАПОМНИТЬ ТЕКУЩУЮ ВЕРШИНУ V и ЗАПОМНИТЬ, НАСКОЛЬКО ПРОДВИНУЛСЯ УКАЗАТЕЛЬ к в СПИСКЕ СМЕЖНОСТИ V. ЕСЛИ Р .LE. 100, ТО В СТЕКЕ не БУДЕТ ХРАНИТЬСЯ БОЛЕЕ 200 ЭЛЕМЕНТОВ.

PTR УКАЗАТЕЛЬ НА ВЕРХ СТЕКА.

Т- СЧЕТЧИК ЧИСЛА РЕБЕР В ОСТОВНОМ ДЕРЕВЕ.

К УКАЗАТЕЛЬ, ИСПОЛЬЗУЕМЫЙ ПРИ ПРОХОЖДЕНИИ

СВЯЗАННЫХ СПИСКОВ СМЕЖНОСТЕЙ.

INTEGER Р. PTR. Т. V. U. WORDS INTEGER ADJ(W0RDS1. NEXT(W0RDS1, STORE(200l. TREE«lO0i2) INTEGER VlSITtlOB)

С ИНИЦИАЛИЗАЦИЯ ПЕРЕМЕННЫХ.

00 100 I s 1,100 VISIT(I) = 0

100 CONTINUE PTR = 0 T = I