logo

TechCodeview

Hĺbkové prvé vyhľadávanie alebo DFS pre graf

Depth First Traversal (alebo DFS) pre graf je podobný Hĺbka Prvý prechod stromu. Jediným háčikom je, že na rozdiel od stromov môžu grafy obsahovať cykly (uzol možno navštíviť dvakrát). Ak sa chcete vyhnúť spracovaniu uzla viac ako raz, použite boolovské navštívené pole. Graf môže mať viac ako jeden prechod DFS.

Príklad:

Vstup: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Výkon: DFS z vrcholu 1 : 1 2 0 3
Vysvetlenie:
Diagram DFS:



Príklad 1

Príklad 1

Vstup: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Výkon: DFS z vrcholu 2 : 2 0 1 3
Vysvetlenie:
Diagram DFS:

Príklad 2

Príklad 2

Odporúčaná prax DFS of Graph Vyskúšajte to!

Ako funguje DFS?

Hĺbkové vyhľadávanie je algoritmus na prechádzanie alebo vyhľadávanie stromových alebo grafových dátových štruktúr. Algoritmus začína v koreňovom uzle (v prípade grafu vyberie nejaký ľubovoľný uzol ako koreňový uzol) a pred spätným sledovaním preskúma čo najďalej pozdĺž každej vetvy.

Poďme pochopiť fungovanie Hĺbkové prvé vyhľadávanie s pomocou nasledujúcej ilustrácie:

Krok 1: Na začiatku sú polia zásobníka a navštívené polia prázdne.

np bodka

Zásobník a navštívené polia sú spočiatku prázdne.

Krok 2: Navštívte 0 a vložte jej susedné uzly, ktoré ešte nie sú navštívené, do zásobníka.

Navštívte uzol 0 a vložte jeho susedné uzly (1, 2, 3) do zásobníka

Krok 3: Teraz je uzol 1 na vrchole zásobníka, takže navštívte uzol 1 a vyberte ho zo zásobníka a vložte všetky jeho susedné uzly, ktoré nie sú navštívené v zásobníku.

Navštívte uzol 1

Krok 4: teraz Uzol 2 v hornej časti zásobníka, takže navštívte uzol 2 a vyberte ho zo zásobníka a vložte všetky jeho susedné uzly, ktoré nie sú navštívené (t. j. 3, 4) do zásobníka.

Navštívte uzol 2 a vložte jeho nenavštívené susedné uzly (3, 4) do zásobníka

Krok 5: Teraz je uzol 4 na vrchole zásobníka, takže navštívte uzol 4 a vyberte ho zo zásobníka a vložte všetky jeho susedné uzly, ktoré nie sú navštívené v zásobníku.

Navštívte uzol 4

Krok 6: Teraz je uzol 3 na vrchole zásobníka, takže navštívte uzol 3 a vyberte ho zo zásobníka a vložte všetky jeho susedné uzly, ktoré nie sú navštívené v zásobníku.

Navštívte uzol 3

Teraz sa zásobník vyprázdni, čo znamená, že sme navštívili všetky uzly a náš prechod DFS končí.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++


c náhodné číslo



// C++ program to print DFS traversal from> // a given vertex in a given graph> #include> using> namespace> std;> // Graph class represents a directed graph> // using adjacency list representation> class> Graph {> public>:> >map<>int>,>bool>>navštívil;> >map<>int>, list<>int>>> adj;> >// Function to add an edge to graph> >void> addEdge(>int> v,>int> w);> >// DFS traversal of the vertices> >// reachable from v> >void> DFS(>int> v);> };> void> Graph::addEdge(>int> v,>int> w)> {> >// Add w to v’s list.> >adj[v].push_back(w);> }> void> Graph::DFS(>int> v)> {> >// Mark the current node as visited and> >// print it> >visited[v] =>true>;> >cout << v <<>' '>;> >// Recur for all the vertices adjacent> >// to this vertex> >list<>int>>::iterátor i;> >for> (i = adj[v].begin(); i != adj[v].end(); ++i)> >if> (!visited[*i])> >DFS(*i);> }> // Driver code> int> main()> {> >// Create a graph given in the above diagram> >Graph g;> >g.addEdge(0, 1);> >g.addEdge(0, 2);> >g.addEdge(1, 2);> >g.addEdge(2, 0);> >g.addEdge(2, 3);> >g.addEdge(3, 3);> >cout <<>'Following is Depth First Traversal'> >' (starting from vertex 2) '>;> >// Function call> >g.DFS(2);> >return> 0;> }> // improved by Vishnudev C>

prológový jazyk 
>

>

Java




// Java program to print DFS traversal> // from a given graph> import> java.io.*;> import> java.util.*;> // This class represents a> // directed graph using adjacency> // list representation> class> Graph {> >private> int> V;> >// Array of lists for> >// Adjacency List Representation> >private> LinkedList adj[];> >// Constructor> >@SuppressWarnings>(>'unchecked'>) Graph(>int> v)> >{> >V = v;> >adj =>new> LinkedList[v];> >for> (>int> i =>0>; i adj[i] = new LinkedList(); } // Function to add an edge into the graph void addEdge(int v, int w) { // Add w to v's list. adj[v].add(w); } // A function used by DFS void DFSUtil(int v, boolean visited[]) { // Mark the current node as visited and print it visited[v] = true; System.out.print(v + ' '); // Recur for all the vertices adjacent to this // vertex Iterator i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil(n, visited); } } // The function to do DFS traversal. // It uses recursive DFSUtil() void DFS(int v) { // Mark all the vertices as // not visited(set as // false by default in java) boolean visited[] = new boolean[V]; // Call the recursive helper // function to print DFS // traversal DFSUtil(v, visited); } // Driver Code public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println( 'Following is Depth First Traversal ' + '(starting from vertex 2)'); // Function call g.DFS(2); } } // This code is contributed by Aakash Hasija> 

>

>

Python3




# Python3 program to print DFS traversal> # from a given graph> from> collections>import> defaultdict> # This class represents a directed graph using> # adjacency list representation> class> Graph:> ># Constructor> >def> __init__(>self>):> ># Default dictionary to store graph> >self>.graph>=> defaultdict(>list>)> > ># Function to add an edge to graph> >def> addEdge(>self>, u, v):> >self>.graph[u].append(v)> > ># A function used by DFS> >def> DFSUtil(>self>, v, visited):> ># Mark the current node as visited> ># and print it> >visited.add(v)> >print>(v, end>=>' '>)> ># Recur for all the vertices> ># adjacent to this vertex> >for> neighbour>in> self>.graph[v]:> >if> neighbour>not> in> visited:> >self>.DFSUtil(neighbour, visited)> > ># The function to do DFS traversal. It uses> ># recursive DFSUtil()> >def> DFS(>self>, v):> ># Create a set to store visited vertices> >visited>=> set>()> ># Call the recursive helper function> ># to print DFS traversal> >self>.DFSUtil(v, visited)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph()> >g.addEdge(>0>,>1>)> >g.addEdge(>0>,>2>)> >g.addEdge(>1>,>2>)> >g.addEdge(>2>,>0>)> >g.addEdge(>2>,>3>)> >g.addEdge(>3>,>3>)> >print>(>'Following is Depth First Traversal (starting from vertex 2)'>)> > ># Function call> >g.DFS(>2>)> # This code is contributed by Neelam Yadav>

ako používať pracovný stôl mysql 

>

>

C#




// C# program to print DFS traversal> // from a given graph> using> System;> using> System.Collections.Generic;> // This class represents a directed graph> // using adjacency list representation> class> Graph {> >private> int> V;> >// Array of lists for> >// Adjacency List Representation> >private> List<>int>>[] adj;> >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> List<>int>>[ v ];> >for> (>int> i = 0; i adj[i] = new List (); } // Funkcia na pridanie hrany do grafu void AddEdge(int v, int w) { // Pridať w do zoznamu v. adj[v].Add(w); } // Funkcia používaná DFS void DFSUtil(int v, bool[] navštívené) { // Označenie aktuálneho uzla ako navštívené // a vytlačenie navštívených[v] = true; Console.Write(v + ' '); // Opakuje sa pre všetky vrcholy // susediace s týmto zoznamom vrcholov vList = adj[v]; foreach(var n in vList) { if (!navštívené[n]) DFSUtil(n, navštívené); } } // Funkcia na prechod DFS. // Používa rekurzívne DFSUtil() void DFS(int v) { // Označí všetky vrcholy ako nenavštívené // (štandardne nastavené ako false v c#) bool[] navštívené = new bool[V]; // Zavolaním rekurzívnej pomocnej funkcie // vytlačíme prechod DFS DFSUtil(v, visit); } // Kód ovládača public static void Main(String[] args) { Graph g = new Graph(4); g.AddEdge(0, 1); g.AddEdge(0; 2); g.AddEdge(1, 2); g.AddEdge(2; 0); g.AddEdge(2, 3); g.AddEdge(3, 3); Console.WriteLine( 'Nasleduje prvý prechod do hĺbky ' + '(začínajúc od vrcholu 2)'); // Volanie funkcie g.DFS(2); Console.ReadKey(); } } // Tento kód prispel techno2mahi> 

>

>

večera vs čas na večeru

Javascript




// Javascript program to print DFS> // traversal from a given> // graph> // This class represents a> // directed graph using adjacency> // list representation> class Graph> {> > >// Constructor> >constructor(v)> >{> >this>.V = v;> >this>.adj =>new> Array(v);> >for>(let i = 0; i this.adj[i] = []; } // Function to add an edge into the graph addEdge(v, w) { // Add w to v's list. this.adj[v].push(w); } // A function used by DFS DFSUtil(v, visited) { // Mark the current node as visited and print it visited[v] = true; console.log(v + ' '); // Recur for all the vertices adjacent to this // vertex for(let i of this.adj[v].values()) { let n = i if (!visited[n]) this.DFSUtil(n, visited); } } // The function to do DFS traversal. // It uses recursive // DFSUtil() DFS(v) { // Mark all the vertices as // not visited(set as // false by default in java) let visited = new Array(this.V); for(let i = 0; i 

>

>

Výkon 

Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>

Analýza zložitosti prvého hĺbkového vyhľadávania:

  • Časová zložitosť: O(V + E), kde V je počet vrcholov a E je počet hrán v grafe.
  • Pomocný priestor: O(V + E), pretože je potrebné ďalšie navštívené pole veľkosti V a veľkosť zásobníka pre iteratívne volanie funkcie DFS.