logo

TechCodeview

Depth First Search sau DFS pentru un grafic

Adâncimea prima traversare (sau DFS) pentru un grafic este similar cu Adâncimea Prima traversare a unui copac. Singura captură aici este că, spre deosebire de copaci, graficele pot conține cicluri (un nod poate fi vizitat de două ori). Pentru a evita procesarea unui nod de mai multe ori, utilizați o matrice booleană vizitată. Un grafic poate avea mai mult de o traversare DFS.

Exemplu:

Intrare: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Ieșire: DFS de la vârful 1 : 1 2 0 3
Explicaţie:
Diagrama DFS:



Exemplul 1

Exemplul 1

Intrare: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Ieșire: DFS de la vârful 2 : 2 0 1 3
Explicaţie:
Diagrama DFS:

Exemplul 2

Exemplul 2

Practică recomandată DFS of Graph Încercați!

Cum funcționează DFS?

Căutarea în profunzime este un algoritm pentru parcurgerea sau căutarea structurilor de date arborescente sau grafice. Algoritmul începe de la nodul rădăcină (selectând un nod arbitrar ca nod rădăcină în cazul unui grafic) și explorează cât mai departe posibil de-a lungul fiecărei ramuri înainte de a reveni.

Să înțelegem funcționarea lui Profunzime prima căutare cu ajutorul următoarei ilustrații:

Pasul 1: Inițial, stiva și matricele vizitate sunt goale.

obj în java

Stiva și matricele vizitate sunt goale inițial.

Pasul 2: Vizitați 0 și puneți în stivă nodurile adiacente care nu sunt încă vizitate.

Vizitați nodul 0 și puneți nodurile adiacente (1, 2, 3) în stivă

Pasul 3: Acum, nodul 1 în partea de sus a stivei, deci vizitați nodul 1 și scoateți-l din stivă și puneți toate nodurile adiacente care nu sunt vizitate în stivă.

Vizitați nodul 1

Pasul 4: Acum, Nodul 2 în partea de sus a stivei, deci vizitați nodul 2 și scoateți-l din stivă și puneți toate nodurile sale adiacente care nu sunt vizitate (adică, 3, 4) în stivă.

Vizitați nodul 2 și puneți nodurile adiacente nevizitate (3, 4) în stivă

Pasul 5: Acum, nodul 4 în partea de sus a stivei, deci vizitați nodul 4 și scoateți-l din stivă și puneți toate nodurile adiacente care nu sunt vizitate în stivă.

Vizitați nodul 4

Pasul 6: Acum, nodul 3 în partea de sus a stivei, deci vizitați nodul 3 și scoateți-l din stivă și puneți toate nodurile adiacente care nu sunt vizitate în stivă.

Vizitați nodul 3

Acum, Stiva devine goală, ceea ce înseamnă că am vizitat toate nodurile și se termină traversarea DFS.

Mai jos este implementarea abordării de mai sus:

C++

java long to string




// 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>>vizitat;> >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>>::iteratorul 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




// 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> 

>

exemplu de clasă java 

>

Python3


comanda chown



# 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#




// 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>>[ în ];> >for> (>int> i = 0; i adj[i] = new List (); } // Funcție pentru a adăuga o margine în grafic void AddEdge(int v, int w) { // Adăugați w la lista v. adj[v].Add(w); } // O funcție folosită de DFS void DFSUtil(int v, bool[] vizitat) { // Marcați nodul curent ca vizitat // și imprimați-l vizitat[v] = true; Consolă.Scrie(v + ' '); // Recură pentru toate nodurile // adiacente acestei liste de vârfuri vList = adj[v]; foreach(var n in vList) { if (!visited[n]) DFSUtil(n, vizitat); } } // Funcția pentru a face traversarea DFS. // Folosește recursiv DFSUtil() void DFS(int v) { // Marchează toate nodurile ca nevizitate // (setate implicit ca false în c#) bool[] visited = new bool[V]; // Apelați funcția de ajutor recursivă // pentru a imprima traversarea DFS DFSUtil(v, vizitat); } // Cod driver 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( 'Urmeaza Depth First Traversal ' + '(începând de la vârful 2)'); // Apel de funcție g.DFS(2); Console.ReadKey(); } } // Acest cod este contribuit de techno2mahi> 

>

>

cum se transformă char în șir

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 

>

>

Ieșire 

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

Analiza complexității a adâncimii prima căutare:

  • Complexitatea timpului: O(V + E), unde V este numărul de vârfuri și E este numărul de muchii din grafic.
  • Spațiu auxiliar: O(V + E), deoarece este necesară o matrice suplimentară vizitată de dimensiunea V și dimensiunea stivei pentru apelul iterativ la funcția DFS.