Тази статия демонстрира процедурата за прилагане на DFS за предоставено дърво или графика.
Как да внедрите първо търсене в дълбочина или DFS за графика в Java?
DFS се използва предимно за търсене в графика чрез посещение на всеки клон/върх точно веднъж. Той може да открие или идентифицира цикли в графика, което помага за предотвратяване на задънени блокировки. Може да се използва за решаване на пъзели или проблеми с лабиринти. DFS може да бъде внедрен/използван в графични алгоритми, уеб обхождане и дизайн на компилатор.
За обяснение посетете кода по-долу на Depth First Search или DFS:
клас Графика {
частен LinkedList addNode [ ] ;
частен булево Преминат [ ] ;
Графика ( вътр върхове ) {
addNode = нов LinkedList [ върхове ] ;
Преминат = нов булево [ върхове ] ;
за ( вътр аз = 0 ; аз < върхове ; аз ++ )
addNode [ аз ] = нов LinkedList ( ) ;
}
невалиден addEdge ( вътр src, вътр започнете ) {
addNode [ src ] . добавете ( започнете ) ;
}
Описание на горния код:
- Първо, класът с име „ Графика ' е създаден. Вътре в него декларира „ LinkedList ' на име ' addNode[] ” и масив от булев тип с име „ Преминат[] ”.
- След това предайте върховете за конструктора на „ Графика ” като параметър.
- След това „ за ” се създава цикъл за преминаване през всеки възел на избрания клон.
- В крайна сметка празният тип ' addEdge() ” се използва за добавяне на ръбове между върховете. Тази функция приема два параметъра: източникът на върха “ src ” и целевия връх “ започнете ”.
След създаването на графика, сега нека добавим код за първо търсене в дълбочина или DFS за създадената по-горе графика:
невалиден DFS ( вътр връх ) {
Преминат [ връх ] = вярно ;
Система . навън . печат ( връх + ' ' ) ;
Итератор това = addNode [ връх ] . listIterator ( ) ;
докато ( това. hasNext ( ) ) {
вътр прил = това. следващия ( ) ;
ако ( ! Преминат [ прил ] )
DFS ( прил ) ;
}
}
В горния кодов блок:
- Първо, „ DFS() ' се създава функция, която получава ' връх ” като параметър. Този връх е маркиран като посетен.
- След това отпечатайте посетения връх, като използвате „ out.print() ” метод.
- След това създайте екземпляр на „ Итератор ”, който итерира през съседните върхове на текущия връх.
- Ако върхът не е посетен, той предава този връх към „ DFS() ” функция.
Сега нека създадем „ основен () ”, за да създадете графиката и след това да приложите DFS към това:
публичен статичен невалиден основен ( низ аргументи [ ] ) {
Графика k = нов Графика ( 4 ) ;
к. addEdge ( 0 , 1 ) ;
к. addEdge ( 1 , 2 ) ;
к. addEdge ( 2 , 3 ) ;
к. addEdge ( 3 , 3 ) ;
Система . навън . println ( „Следва първо обхождане на дълбочина“ ) ;
к. DFS ( 1 ) ;
}
}
Обяснение на горния код:
- Първо създайте обект ' к ' за ' графика() ” метод.
- След това „ addEdge() ” методът се използва за добавяне на ръбове между множество върхове. Това създава структурата на нашата графика.
- В крайна сметка предайте произволна стойност на върха като аргумент към вече създадения „ DFS() ” функция. За да намерите този път на върха от корена, използвайте алгоритъм за търсене в дълбочина. Например стойност на „ 1 ” се предава на „ DFS() ” функция.
След края на фазата на компилиране:
Резултатът показва, че търсенето първо в дълбочина е приложено успешно.
Заключение
Търсенето първо в дълбочина е алгоритъм за обхождане на графики, който формира основата за много алгоритми на графики, като намиране на най-краткия път, обхващащи дървета и анализ на свързаността. Започва от основния възел и след това се придвижва възможно най-дълбоко до напускащия възел или последния възел на този клон преди обратно проследяване. Тази статия демонстрира процедурата за прилагане на първо търсене в дълбочина или DFS за графика в Java.