Prvo prečkanje globine (ali DFS) za graf je podoben Globina Prvi prehod drevesa. Edina zanka pri tem je, da za razliko od dreves lahko grafi vsebujejo cikle (vozlišče je lahko obiskano dvakrat). Če se želite izogniti večkratni obdelavi vozlišča, uporabite logično obiskano matriko. Graf ima lahko več kot eno prečkanje DFS.
primer:
Priporočena praksa DFS of Graph Poskusite!Vnos: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Izhod: DFS iz točke 1 : 1 2 0 3
Pojasnilo:
Diagram DFS:
Primer 1
Vnos: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Izhod: DFS iz točke 2 : 2 0 1 3
Pojasnilo:
Diagram DFS:Primer 2
Kako deluje DFS?
Iskanje najprej v globino je algoritem za prečkanje ali iskanje drevesnih ali grafičnih podatkovnih struktur. Algoritem se začne pri korenskem vozlišču (izbere neko poljubno vozlišče kot korensko vozlišče v primeru grafa) in raziskuje, kolikor je mogoče vzdolž vsake veje, preden se vrne nazaj.
Razumejmo delovanje Najprej iskanje po globini s pomočjo naslednje ilustracije:
Korak 1: Prvotni sklad in obiskani nizi so prazni.
string find c++Sklad in obiskani nizi so na začetku prazni.
2. korak: Obiščite 0 in postavite njegova sosednja vozlišča, ki še niso obiskana, v sklad.
Obiščite vozlišče 0 in postavite njegova sosednja vozlišča (1, 2, 3) v sklad
3. korak: Zdaj je vozlišče 1 na vrhu sklada, zato obiščite vozlišče 1 in ga odstranite iz sklada ter postavite vsa njegova sosednja vozlišča, ki niso obiskana, v sklad.
Obiščite vozlišče 1
4. korak: zdaj, Vozlišče 2 na vrhu sklada, zato obiščite vozlišče 2 in ga odstranite iz sklada ter postavite vsa njegova sosednja vozlišča, ki niso obiskana (tj. 3, 4), v sklad.
Obiščite vozlišče 2 in postavite njegova neobiskana sosednja vozlišča (3, 4) v sklad
5. korak: Zdaj je vozlišče 4 na vrhu sklada, zato obiščite vozlišče 4 in ga odstranite iz sklada ter postavite vsa njegova sosednja vozlišča, ki niso obiskana, v sklad.
Obiščite vozlišče 4
6. korak: Zdaj je vozlišče 3 na vrhu sklada, zato obiščite vozlišče 3 in ga odstranite iz sklada ter postavite vsa sosednja vozlišča, ki niso obiskana, v sklad.
vrste strojnega učenjaObiščite vozlišče 3
Zdaj postane Stack prazen, kar pomeni, da smo obiskali vsa vozlišča in naše prečkanje DFS se konča.
Spodaj je izvedba zgornjega pristopa:
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>>obiskano;> >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>>::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
// 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> |
>
sončna deol starost
>
Python3
številke v abecedi
# 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>>[ v ];> >for> (>int> i = 0; i adj[i] = new List |
>
>
prenesite videoposnetke youtube na vlc
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 |
>
>Izhod
Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>
Analiza kompleksnosti iskanja najprej po globini:
- Časovna zahtevnost: O(V + E), kjer je V število vozlišč in E število robov v grafu.
- Pomožni prostor: O(V + E), ker je potrebna dodatna obiskana matrika velikosti V in velikost sklada za iterativni klic funkcije DFS.