Овај чланак показује процедуру за имплементацију ДФС-а за дато стабло или граф.
Како имплементирати претрагу у дубину или ДФС за графикон у Јави?
ДФС се првенствено користи за претрагу графа посетом сваке гране/темена тачно једном. Може да открије или идентификује циклусе у графикону који помаже у спречавању застоја. Може се користити за решавање загонетки или проблема са лавиринтом. ДФС се може имплементирати/користити у алгоритмима графова, претраживању веба и дизајну компајлера.
За објашњење, посетите доњи код за Дептх Фирст Сеарцх или ДФС:
класа Граф {
приватни ЛинкедЛист аддНоде [ ] ;
приватни боолеан Пређено [ ] ;
Граф ( инт темена ) {
аддНоде = Нова ЛинкедЛист [ темена ] ;
Пређено = Нова боолеан [ темена ] ;
за ( инт и = 0 ; и < темена ; и ++ )
аддНоде [ и ] = Нова ЛинкедЛист ( ) ;
}
празнина аддЕдге ( инт срц, инт почетак ) {
аддНоде [ срц ] . додати ( почетак ) ;
}
Опис горњег кода:
- Прво, класа под називом „ Граф ' је створен. Унутар њега, изјављује „ ЛинкедЛист ' назван ' аддНоде[] ” и низ логичког типа под називом „ прешао[] ”.
- Затим пренесите врхове за конструктор „ Граф ” класа као параметар.
- Након тога, „ за ” петља се креира за кретање кроз сваки чвор изабране гране.
- На крају, тип празнине „ аддЕдге() ” се користи за додавање ивица између врхова. Ова функција узима два параметра: извор темена “ срц ” и одредишни врх “ почетак ”.
Након креирања графикона, сада додајмо код за претрагу у дубину или ДФС за горе креирани графикон:
празнина ДФС ( инт вертек ) {
Пређено [ вертек ] = истина ;
Систем . оут . принт ( вертек + ' ' ) ;
Итератор ово = аддНоде [ вертек ] . листИтератор ( ) ;
док ( ово. хасНект ( ) ) {
инт адј = ово. следећи ( ) ;
ако ( ! Пређено [ адј ] )
ДФС ( адј ) ;
}
}
У горњем блоку кода:
- Прво, „ ДФС() ” креира се функција која добија „ вертек ” као параметар. Тај врх је означен као посећен.
- Затим одштампајте посећени врх користећи „ оут.принт() ” метод.
- Затим креирајте инстанцу „ Итератор ” који се понавља преко суседних врхова тренутног темена.
- Ако се врх није посећен, онда он прослеђује тај врх у „ ДФС() ” функција.
Сада, хајде да направимо „ главни() ” функционални део да креирате графикон, а затим примените ДФС на то:
јавности статична празнина главни ( Низ аргс [ ] ) {
Графикон к = Нова Граф ( 4 ) ;
к. аддЕдге ( 0 , 1 ) ;
к. аддЕдге ( 1 , 2 ) ;
к. аддЕдге ( 2 , 3 ) ;
к. аддЕдге ( 3 , 3 ) ;
Систем . оут . принтлн ( „Следи прелазак у дубину прво“ ) ;
к. ДФС ( 1 ) ;
}
}
Објашњење горњег кода:
- Прво направите објекат ' к ' за ' Графикон() ” метод.
- Затим, „ аддЕдге() ” метода се користи за додавање ивица између више врхова. Ово ствара структуру нашег графикона.
- На крају, проследите било коју вредност темена као аргумент већ креираном „ ДФС() ” функција. Да бисте пронашли путању тог врха од корена, користите алгоритам претраге у дубину. На пример, вредност „ 1 ” се преноси на „ ДФС() ” функција.
Након завршетка фазе компилације:
Излаз показује да је претрага у дубину успешно спроведена.
Закључак
Дептх Фирст Сеарцх је алгоритам за обилажење графа који чини основу за многе алгоритме графа као што је проналажење најкраће стазе, стабла која се протежу и анализа повезаности. Почиње од коренског чвора, а затим се помера што је дубље могуће до излазног чвора или последњег чвора те гране пре враћања уназад. Овај чланак је демонстрирао процедуру за имплементацију претраге у дубину или ДФС за граф у Јави.