logo

TechCodeview

Diepte eerst zoeken of DFS voor een grafiek

Diepte eerste traversal (of DFS) voor een grafiek is vergelijkbaar met Diepte Eerste verplaatsing van een boom. Het enige probleem hier is dat grafieken, in tegenstelling tot bomen, cycli kunnen bevatten (een knooppunt kan twee keer worden bezocht). Om te voorkomen dat een knooppunt meerdere keren wordt verwerkt, gebruikt u een Booleaanse bezochte array. Een grafiek kan meer dan één DFS-traversal hebben.

Voorbeeld:

Invoer: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Uitgang: DFS vanaf hoekpunt 1: 1 2 0 3
Uitleg:
DFS-diagram:



voorbeeld 1

voorbeeld 1

Invoer: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Uitgang: DFS vanaf hoekpunt 2: 2 0 1 3
Uitleg:
DFS-diagram:

Voorbeeld 2

Voorbeeld 2

Aanbevolen praktijk DFS van Graph Probeer het!

Hoe werkt DFS?

Depth-first search is een algoritme voor het doorkruisen of doorzoeken van boom- of grafiekdatastructuren. Het algoritme begint bij het hoofdknooppunt (waarbij in het geval van een grafiek een willekeurig knooppunt als hoofdknooppunt wordt geselecteerd) en verkent zo ver mogelijk langs elke tak voordat het teruggaat.

Laten we de werking ervan begrijpen Diepte eerste zoekopdracht met behulp van de volgende illustratie:

Stap 1: Aanvankelijk zijn de stapel- en bezochte arrays leeg.

gelinkte lijst in Java

Stack- en bezochte arrays zijn aanvankelijk leeg.

Stap 2: Bezoek 0 en plaats de aangrenzende knooppunten die nog niet zijn bezocht in de stapel.

Bezoek knooppunt 0 en plaats de aangrenzende knooppunten (1, 2, 3) in de stapel

Stap 3: Nu staat knooppunt 1 bovenaan de stapel, dus bezoek knooppunt 1, haal het van de stapel en plaats alle aangrenzende knooppunten die niet worden bezocht in de stapel.

Bezoek knooppunt 1

Stap 4: Nu, Knooppunt 2 bovenaan de stapel, dus bezoek knooppunt 2, haal het van de stapel en plaats alle aangrenzende knooppunten die niet worden bezocht (d.w.z. 3, 4) in de stapel.

Bezoek knooppunt 2 en plaats de niet-bezochte aangrenzende knooppunten (3, 4) in de stapel

Stap 5: Nu staat knooppunt 4 bovenaan de stapel, dus bezoek knooppunt 4 en haal het van de stapel en plaats alle aangrenzende knooppunten die niet worden bezocht in de stapel.

Bezoek knooppunt 4

Stap 6: Nu staat knooppunt 3 bovenaan de stapel, dus bezoek knooppunt 3, haal het van de stapel en plaats alle aangrenzende knooppunten die niet worden bezocht in de stapel.

Bezoek knooppunt 3

Nu wordt Stack leeg, wat betekent dat we alle knooppunten hebben bezocht en dat onze DFS-traversal eindigt.

powershell kleiner dan of gelijk aan

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++




// 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>>bezocht;> >map<>int>, list<>int>>> bijvoeglijk naamwoord;> >// 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>>::iterator 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> 

>

>

Java




tekenreeks invoeren in 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> 

>

>

C#




mijnlivecricket in

// 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>>[] bijvoeglijk naamwoord;> >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> List<>int>>[in];> >for> (>int> i = 0; i adj[i] = new List (); } // Functie om een ​​rand toe te voegen aan de grafiek void AddEdge(int v, int w) {// Voeg w toe aan de lijst van v. bijvoeglijk naamwoord[v].Toevoegen(w); } // Een functie gebruikt door DFS void DFSUtil(int v, bool[] bezocht) {// Markeer het huidige knooppunt als bezocht // en druk het af bezocht[v] = true; Console.Write(v + ''); // Terugkerend voor alle hoekpunten // grenzend aan deze hoekpuntenlijst vLijst = bijvoeglijk naamwoord[v]; foreach(var n in vList) { if (!bezocht[n]) DFSUtil(n, bezocht); } } // De functie om DFS-traversal uit te voeren. // Het gebruikt recursieve DFSUtil() void DFS(int v) {// Markeer alle hoekpunten als niet bezocht // (standaard ingesteld als false in c#) bool[] bezocht = nieuwe bool[V]; // Roep de recursieve helperfunctie op // om DFS-traversal DFSUtil(v, visit) af te drukken; } // Stuurprogrammacode 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.Edge toevoegen(2, 3); g.AddEdge(3, 3); Console.WriteLine( 'Het volgende is Depth First Traversal ' + '(beginnend vanaf hoekpunt 2)'); // Functieaanroep g.DFS(2); Console.ReadKey(); } } // Deze code is bijgedragen door techno2mahi> 

>

>

middelste afbeelding in css

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 

>

>

Uitvoer 

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

Complexiteitsanalyse van diepte Eerste zoekopdracht:

  • Tijdcomplexiteit: O(V + E), waarbij V het aantal hoekpunten is en E het aantal randen in de grafiek.
  • Hulpruimte: O(V + E), aangezien een extra bezochte array van grootte V vereist is, en stapelgrootte voor iteratieve aanroep van de DFS-functie.