logo

TechCodeview

Prima ricerca della profondità o DFS per un grafico

Prima traversata in profondità (o DFS) per un grafico è simile a Profondità Primo attraversamento di un albero. L'unico problema qui è che, a differenza degli alberi, i grafi possono contenere cicli (un nodo può essere visitato due volte). Per evitare di elaborare un nodo più di una volta, utilizzare un array visitato booleano. Un grafico può avere più di un attraversamento DFS.

Esempio:

Ingresso: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Produzione: DFS dal vertice 1: 1 2 0 3
Spiegazione:
Diagramma DFS:



Esempio 1

Esempio 1

Ingresso: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Produzione: DFS dal vertice 2: 2 0 1 3
Spiegazione:
Diagramma DFS:

Esempio 2

Esempio 2

Pratica consigliata DFS del grafico Provalo!

Come funziona il DFS?

La ricerca Depth-First è un algoritmo per l'attraversamento o la ricerca di strutture di dati ad albero o grafo. L'algoritmo inizia dal nodo radice (selezionando un nodo arbitrario come nodo radice nel caso di un grafico) ed esplora il più lontano possibile lungo ciascun ramo prima di tornare indietro.

Cerchiamo di capire il funzionamento di Prima ricerca in profondità con l'aiuto della seguente illustrazione:

Passo 1: Inizialmente lo stack e gli array visitati sono vuoti.

cos'è myspace

Lo stack e gli array visitati sono inizialmente vuoti.

Passo 2: Visita 0 e metti nello stack i suoi nodi adiacenti che non sono ancora stati visitati.

Visita il nodo 0 e metti i suoi nodi adiacenti (1, 2, 3) nello stack

Passaggio 3: Ora, il nodo 1 è in cima allo stack, quindi visita il nodo 1, estrailo dallo stack e metti tutti i suoi nodi adiacenti che non sono visitati nello stack.

Visita il nodo 1

Passaggio 4: Ora, Nodo 2 in cima allo stack, quindi visita il nodo 2, estrailo dallo stack e metti tutti i suoi nodi adiacenti che non sono visitati (cioè 3, 4) nello stack.

Visita il nodo 2 e metti nella pila i suoi nodi adiacenti non visitati (3, 4).

Passaggio 5: Ora, il nodo 4 è in cima allo stack, quindi visita il nodo 4, estrailo dallo stack e metti tutti i suoi nodi adiacenti che non sono visitati nello stack.

Visita il nodo 4

Passaggio 6: Ora, il nodo 3 è in cima allo stack, quindi visita il nodo 3, estrailo dallo stack e metti tutti i suoi nodi adiacenti che non sono visitati nello stack.

Visita il nodo 3

Ora lo Stack diventa vuoto, il che significa che abbiamo visitato tutti i nodi e il nostro attraversamento DFS termina.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++


l'età di salman khan



// 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>>visitato;> >map<>int>, list<>int>>> agg;> >// 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>>::iteratore 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>

ordinamento dell'heap 
>

>

Giava




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

cos'è il computer 

>

>

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>>[] agg;> >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> List<>int>>[ in ];> >for> (>int> i = 0; i adj[i] = new List (); } // Funzione per aggiungere un bordo al grafico void AddEdge(int v, int w) { // Aggiungi w alla lista di v. adj[v].Add(w); } // Una funzione utilizzata da DFS void DFSUtil(int v, bool[] visitato) { // Contrassegna il nodo corrente come visitato // e stampalo visitato[v] = true; Console.Write(v + ' '); // Ricorre per tutti i vertici // adiacenti a questa lista di vertici vLista = agg[v]; foreach(var n in vList) { if (!visited[n]) DFSUtil(n, visitato); } } // La funzione per eseguire l'attraversamento DFS. // Utilizza DFSUtil() ricorsivo void DFS(int v) { // Contrassegna tutti i vertici come non visitati // (impostato come falso per impostazione predefinita in C#) bool[] visitato = new bool[V]; // Chiama la funzione di supporto ricorsiva // per stampare DFS traversal DFSUtil(v,visited); } // Codice driver public static void Main(String[] args) { Graph g = new Graph(4); g.AggiungiBordo(0, 1); g.AggiungiBordo(0, 2); g.AggiungiBordo(1, 2); g.AggiungiBordo(2, 0); g.AggiungiBordo(2, 3); g.AggiungiBordo(3, 3); Console.WriteLine( 'Segue la prima traversata della profondità ' + '(a partire dal vertice 2)'); // Chiamata di funzione g.DFS(2); Console.ReadKey(); } } // Questo codice è fornito da techno2mahi> 

>

>

come ottenere il piccione selvatico su Android

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 

>

>

Produzione 

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

Analisi della complessità della profondità Prima ricerca:

  • Complessità temporale: O(V + E), dove V è il numero di vertici ed E è il numero di archi nel grafico.
  • Spazio ausiliario: O(V + E), poiché è richiesto un array extra visitato di dimensione V e la dimensione dello stack per la chiamata iterativa alla funzione DFS.