W tym artykule przedstawiono procedurę implementacji DFS dla podanego drzewa lub wykresu.
Jak zaimplementować wyszukiwanie w głąb lub DFS dla wykresu w Javie?
DFS jest używany głównie do przeszukiwania grafu poprzez odwiedzanie każdej gałęzi/wierzchołka dokładnie raz. Może wykrywać lub identyfikować cykle na wykresie, co pomaga zapobiegać impasom. Może być używany do rozwiązywania zagadek lub problemów z labiryntami. DFS można zaimplementować/wykorzystać w algorytmach graficznych, indeksowaniu sieci i projektowaniu kompilatorów.
Aby uzyskać wyjaśnienie, odwiedź poniższy kod wyszukiwania w głąb lub DFS:
klasa Wykres {
prywatny Połączona lista dodajwęzeł [ ] ;
prywatny logiczna Przemierzone [ ] ;
Wykres ( int wierzchołki ) {
dodajwęzeł = nowy Połączona lista [ wierzchołki ] ;
Przemierzone = nowy logiczna [ wierzchołki ] ;
Do ( int I = 0 ; I < wierzchołki ; I ++ )
dodajwęzeł [ I ] = nowy Połączona lista ( ) ;
}
próżnia dodaj krawędź ( int źródło, int początek ) {
dodajwęzeł [ źródło ] . dodać ( początek ) ;
}
Opis powyższego kodu:
- Najpierw klasa o nazwie „ Wykres ' jest tworzone. W środku deklaruje „ Połączona lista ' o imieniu ' dodajwęzeł[] ” i tablica typu boolowskiego o nazwie „ przejechany[] ”.
- Następnie podaj wierzchołki konstruktora „ Wykres klasa ” jako parametr.
- Następnie „ Do Pętla ” jest tworzona w celu poruszania się po każdym węźle wybranej gałęzi.
- W końcu pusty typ „ addEdge() ” służy do dodawania krawędzi między wierzchołkami. Ta funkcja przyjmuje dwa parametry: źródło wierzchołka „ źródło ” i wierzchołek docelowy “ początek ”.
Po utworzeniu grafu dodajmy teraz kod przeszukiwania w głąb lub DFS dla utworzonego powyżej grafu:
próżnia DFS ( int wierzchołek ) {
Przemierzone [ wierzchołek ] = PRAWDA ;
System . na zewnątrz . wydrukować ( wierzchołek + ' ' ) ;
Iterator Ten = dodajwęzeł [ wierzchołek ] . listIterator ( ) ;
chwila ( Ten. maNastępny ( ) ) {
int przym = Ten. Następny ( ) ;
Jeśli ( ! Przemierzone [ przym ] )
DFS ( przym ) ;
}
}
W powyższym bloku kodu:
- Po pierwsze ' DFS() ” tworzona jest funkcja, która pobiera „ wierzchołek ” jako parametr. Ten wierzchołek jest oznaczony jako odwiedzony.
- Następnie wydrukuj odwiedzony wierzchołek za pomocą „ wydruk.wydruk() ' metoda.
- Następnie utwórz instancję „ Iterator ”, która iteruje po sąsiednich wierzchołkach bieżącego wierzchołka.
- Jeśli wierzchołek nie jest odwiedzany, przekazuje ten wierzchołek do „ DFS() ” funkcja.
Teraz stwórzmy „ główny() ”, aby utworzyć wykres, a następnie zastosować do niego DFS:
publiczny statyczny próżnia główny ( Strunowy argumenty [ ] ) {
wykres k = nowy Wykres ( 4 ) ;
k. dodaj krawędź ( 0 , 1 ) ;
k. dodaj krawędź ( 1 , 2 ) ;
k. dodaj krawędź ( 2 , 3 ) ;
k. dodaj krawędź ( 3 , 3 ) ;
System . na zewnątrz . println ( „Podążanie za pierwszym przejściem to głębokość” ) ;
k. DFS ( 1 ) ;
}
}
Wyjaśnienie powyższego kodu:
- Najpierw utwórz obiekt „ k ' dla ' Wykres() ' metoda.
- Następnie „ addEdge() ” służy do dodawania krawędzi między wieloma wierzchołkami. Tworzy to strukturę naszego grafu.
- Na koniec przekaż dowolną wartość wierzchołka jako argument do już utworzonego „ DFS() ” funkcja. Aby znaleźć tę ścieżkę wierzchołka od korzenia, użyj algorytmu wyszukiwania w głąb. Na przykład wartość „ 1 ” przechodzi do „ DFS() ” funkcja.
Po zakończeniu fazy kompilacji:
Dane wyjściowe pokazują, że przeszukiwanie w głąb zostało pomyślnie zaimplementowane.
Wniosek
Depth First Search to algorytm przechodzenia przez graf, który stanowi podstawę wielu algorytmów grafowych, takich jak znajdowanie najkrótszej ścieżki, rozpinanie drzew i analiza połączeń. Zaczyna się od węzła głównego, a następnie przesuwa się tak głęboko, jak to możliwe, aż do węzła opuszczającego lub ostatniego węzła tej gałęzi przed cofnięciem. W tym artykule zademonstrowano procedurę implementacji przeszukiwania w głąb lub DFS dla grafu w Javie.