Menu

Pierwsze przeszukiwanie w głąb (DFS) C ++ Program do przechodzenia przez wykres lub drzewo

  • Główny
  • Inny
  • Pierwsze przeszukiwanie w głąb (DFS) C ++ Program do przechodzenia przez wykres lub drzewo

depth first search c program traverse graph

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Ten samouczek obejmuje wyszukiwanie wgłębne (DFS) w języku C ++, w którym wykres lub drzewo jest przemierzane wgłębnie. Nauczysz się również algorytmu i implementacji DFS:

Przeszukiwanie w głąb (DFS) to kolejna technika używana do przechodzenia przez drzewo lub wykres.

DFS rozpoczyna się od węzła głównego lub węzła początkowego, a następnie bada sąsiednie węzły bieżącego węzła, wchodząc głębiej w wykres lub drzewo. Oznacza to, że w DFS węzły są eksplorowane w głąb, dopóki nie zostanie napotkany węzeł bez dzieci.

Po osiągnięciu węzła liścia DFS cofa się i zaczyna eksplorować więcej węzłów w podobny sposób.

=> Obejrzyj przewodnik szkoleniowy dla początkujących C ++ tutaj.

Przeszukiwanie w głąb

Czego się nauczysz:

Pierwsze wyszukiwanie w głębi (DFS) w C ++

W przeciwieństwie do BFS, w którym eksplorujemy węzły wszerz, w DFS badamy węzły w głąb. W DFS używamy struktury danych stosu do przechowywania badanych węzłów. Krawędzie, które prowadzą nas do niezbadanych węzłów, nazywane są „krawędziami odkrywania”, podczas gdy krawędzie prowadzące do już odwiedzonych węzłów nazywane są „krawędziami bloków”.

Następnie zobaczymy algorytm i pseudokod dla techniki DFS.

Algorytm DFS

  • Krok 1: Wstaw węzeł główny lub węzeł początkowy drzewa lub wykresu do stosu.
  • Krok 2: Zdejmij górny przedmiot ze stosu i dodaj go do listy odwiedzonych.
  • Krok 3: Znajdź wszystkie sąsiednie węzły węzła oznaczonego jako odwiedzone i dodaj te, które nie są jeszcze odwiedzone, do stosu.
  • Krok 4 : Powtarzaj kroki 2 i 3, aż stos będzie pusty.

Pseudo kod

Pseudokod dla DFS jest podany poniżej.

Pseudokod dla DFS

Z powyższego pseudokodu zauważamy, że algorytm DFS jest wywoływany rekurencyjnie na każdym wierzchołku, aby zapewnić, że wszystkie wierzchołki są odwiedzane.

Przejścia z ilustracjami

Zilustrujmy teraz przechodzenie wykresu przez DFS. Dla jasności użyjemy tego samego wykresu, którego użyliśmy na ilustracji BFS.

Ilustracje DFS z trawersami

Niech 0 będzie początkowym węzłem lub węzłem źródłowym. Najpierw oznaczamy go jako odwiedzony i dodajemy do listy odwiedzonych. Następnie wsuwamy wszystkie sąsiednie węzły w stos.

Wepchnij wszystkie sąsiednie węzły w stos

Następnie bierzemy do przetworzenia jeden z sąsiednich węzłów, tj. Wierzchołek stosu, który jest 1. Oznaczamy go jako odwiedzony, dodając go do listy odwiedzonych. Teraz poszukaj sąsiednich węzłów o wartości 1. Ponieważ 0 jest już na liście odwiedzonych, ignorujemy je i odwiedzamy 2, które jest szczytem stosu.

Ilustracja DFS - krok 3

Następnie oznaczamy węzeł 2 jako odwiedzony. Jego sąsiedni węzeł 4 jest dodawany do stosu.

Ilustracja DFS Krok 4

Następnie zaznaczamy 4, który jest szczytem stosu jako odwiedzony. Węzeł 4 ma tylko węzeł 2 jako sąsiedni, który jest już odwiedzony, dlatego go ignorujemy.

Ilustracja DFS Krok 5

Na tym etapie w stosie występuje tylko węzeł 3. Jego sąsiedni węzeł 0 jest już odwiedzony, dlatego go ignorujemy. Teraz oznaczamy 3 jako odwiedzone.

Ilustracja DFS Krok 6

Teraz stos jest pusty, a lista odwiedzonych pokazuje sekwencję przemierzania w głąb danego wykresu.

Jeśli obserwujemy dany wykres i sekwencję przemierzania, zauważymy, że w przypadku algorytmu DFS rzeczywiście przechodzimy przez wykres w głębi, a następnie cofamy się go ponownie, aby zbadać nowe węzły.

Implementacja wyszukiwania w głębi

Zaimplementujmy technikę przechodzenia DFS w C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Wynik:

Przechodzenie w głąb w pierwszej kolejności dla danego wykresu:

0 1 2 4 3

Ponownie wykorzystaliśmy wykres w programie, którego użyliśmy do celów ilustracyjnych. Widzimy, że algorytm DFS (podzielony na dwie funkcje) jest wywoływany rekurencyjnie na każdym wierzchołku wykresu, aby zapewnić odwiedzanie wszystkich wierzchołków.

Analiza czasu działania

Złożoność czasowa DFS jest taka sama jak BFS, tj. O (| V | + | E |) gdzie V to liczba wierzchołków, a E to liczba krawędzi na danym wykresie.

Podobnie jak w przypadku BFS, w zależności od tego, czy wykres jest słabo zapełniony, czy gęsto wypełniony, dominującym czynnikiem będą odpowiednio wierzchołki lub krawędzie w obliczaniu złożoności czasowej.

Iteracyjny DFS

Przedstawiona powyżej implementacja techniki DFS ma charakter rekurencyjny i wykorzystuje stos wywołań funkcji. Mamy inną odmianę implementacji DFS, tj. „ Iteracyjne przeszukiwanie w głąb ”. W tym przypadku używamy jawnego stosu do przechowywania odwiedzonych wierzchołków.

Poniżej pokazaliśmy implementację iteracyjnego systemu plików DFS. Zauważ, że implementacja jest taka sama jak BFS, z wyjątkiem tego, że używamy struktury danych stosu zamiast kolejki.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Wynik:

Dane wyjściowe iteracyjnego przejścia w głąb w pierwszej kolejności:

0 3 2 4 1

Używamy tego samego wykresu, którego używaliśmy w naszej rekurencyjnej implementacji. Różnica w wynikach polega na tym, że używamy stosu w iteracyjnej implementacji. Gdy stosy podążają za kolejnością LIFO, otrzymujemy inną sekwencję DFS. Aby uzyskać tę samą sekwencję, możemy chcieć wstawić wierzchołki w odwrotnej kolejności.

BFS vs DFS

Do tej pory omawialiśmy obie techniki przechodzenia dla wykresów, tj. BFS i DFS.

Przyjrzyjmy się teraz różnicom między nimi.

BFSDFS
Oznacza „wyszukiwanie wszerz”Oznacza „wyszukiwanie w głąb”
Węzły są eksplorowane wszerz po poziomie.Węzły są badane w głąb, aż istnieją tylko węzły liści, a następnie cofane w celu zbadania innych nieodwiedzonych węzłów.
BFS jest wykonywany za pomocą struktury danych kolejki.DFS jest wykonywany za pomocą struktury danych stosu.
Wolniejsza wydajność.Szybszy niż BFS.
Przydatne do znajdowania najkrótszej ścieżki między dwoma węzłami.Używany głównie do wykrywania cykli na wykresach.

Zastosowania DFS

  • Wykrywanie cykli na wykresie: Jeśli podczas wykonywania DFS na wykresie znajdziemy tylną krawędź, możemy wywnioskować, że wykres ma cykl. Stąd DFS jest używany do wykrywania cykli na wykresie.
  • Znalezienie drogi: Mając dwa wierzchołki x i y, możemy znaleźć ścieżkę między x i y za pomocą DFS. Zaczynamy od wierzchołka x, a następnie przesuwamy wszystkie wierzchołki w drodze do stosu, aż napotkamy y. Zawartość stosu wyznacza ścieżkę między x i y.
  • Minimalne drzewo rozpinające i najkrótsza ścieżka: Przechodzenie przez DFS nieważonego wykresu daje nam minimalne drzewo rozpinające i najkrótszą ścieżkę między węzłami.
  • Sortowanie topologiczne: Używamy sortowania topologicznego, gdy musimy zaplanować zadania na podstawie danych zależności między zadaniami. W dziedzinie informatyki używamy go głównie do rozwiązywania zależności symboli w linkerach, serializacji danych, planowania instrukcji itp. DFS jest szeroko stosowany w sortowaniu topologicznym.

Wniosek

W ostatnich kilku samouczkach zbadaliśmy więcej na temat dwóch technik przechodzenia dla wykresów, tj. BFS i DFS. Widzieliśmy różnice, a także zastosowania obu technik. BFS i DFS w zasadzie osiągają ten sam wynik odwiedzania wszystkich węzłów grafu, ale różnią się kolejnością danych wyjściowych i sposobem, w jaki jest to zrobione.

Widzieliśmy również implementację obu technik. Podczas gdy BFS używa kolejki, DFS używa stosów do implementacji tej techniki. Na tym kończymy samouczek dotyczący technik przechodzenia przez wykresy. Możemy również używać BFS i DFS na drzewach.

jak wybrać przycisk radiowy w selenie

Dowiemy się więcej o łączeniu drzew i kilku algorytmach, aby znaleźć najkrótszą ścieżkę między węzłami wykresu w naszym nadchodzącym samouczku.

=> Zobacz tutaj, aby poznać pełną listę samouczków języka C ++.

rekomendowane lektury

^