Pirmasis gylis (arba DFS) nes grafikas yra panašus į Gylis Pirmasis medžio apvažiavimas. Vienintelis dalykas čia yra tas, kad, skirtingai nei medžiai, diagramose gali būti ciklai (mazgas gali būti aplankytas du kartus). Kad mazgas nebūtų apdorotas daugiau nei vieną kartą, naudokite loginį aplankytą masyvą. Diagrama gali turėti daugiau nei vieną DFS perėjimą.
Pavyzdys:
Rekomenduojama praktika DFS of Graph Išbandykite!Įvestis: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Išvestis: DFS iš 1 viršūnės: 1 2 0 3
Paaiškinimas:
DFS diagrama:
1 pavyzdys
Įvestis: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Išvestis: DFS iš 2 viršūnės: 2 0 1 3
Paaiškinimas:
DFS diagrama:2 pavyzdys
Kaip veikia DFS?
Paieška pagal gylį yra medžio ar grafiko duomenų struktūrų perėjimo arba paieškos algoritmas. Algoritmas pradedamas nuo šakninio mazgo (parenkant kokį nors savavališką mazgą kaip šakninį mazgą grafiko atveju) ir kiek įmanoma išnagrinėja kiekvieną šaką prieš grįžtant atgal.
Leiskite mums suprasti, kaip veikia Gylis pirmoji paieška šios iliustracijos pagalba:
1 žingsnis: Iš pradžių stack ir lankomi masyvai yra tušti.
"kruskal algoritmas"Stack ir aplankytos masyvai iš pradžių yra tušti.
2 žingsnis: Apsilankykite 0 ir įdėkite gretimus mazgus, kurie dar nėra aplankę, į krūvą.
Apsilankykite mazge 0 ir įdėkite gretimus mazgus (1, 2, 3) į krūvą
3 veiksmas: Dabar 1 mazgas yra krūvos viršuje, todėl apsilankykite 1 mazge ir iškelkite jį iš dėklo ir įdėkite visus gretimus mazgus, kurie nėra aplankomi.
Apsilankykite 1 mazge
4 veiksmas: Dabar 2 mazgas krūvos viršuje, todėl apsilankykite 2 mazge ir iškelkite jį iš dėklo ir įdėkite į krūvą visus gretimus mazgus, kurie nėra aplankomi (t. y. 3, 4).
Apsilankykite 2 mazge ir įdėkite jo nelankytus gretimus mazgus (3, 4) į krūvą
5 veiksmas: Dabar 4 mazgas yra krūvos viršuje, todėl apsilankykite 4 mazge ir iškelkite jį iš dėklo ir įdėkite visus gretimus mazgus, kurie nėra aplankomi.
šališkumas ir dispersijaApsilankykite 4 mazge
6 veiksmas: Dabar 3 mazgas yra krūvos viršuje, todėl apsilankykite 3 mazge ir iškelkite jį iš krūvos ir įdėkite į krūvą visus gretimus mazgus, kurie nėra lankomi.
Apsilankykite 3 mazge
Dabar „Stack“ tampa tuščia, o tai reiškia, kad aplankėme visus mazgus ir mūsų DFS perkėlimas baigiasi.
Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:
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>>aplankė;> >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>>::iteratorius 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> |
>
daryti būdami java
>
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> |
>
int į eilutę konvertavimas java
>
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>>[į ];> >for> (>int> i = 0; i adj[i] = new List |
>
>
žemėlapis vs rinkinys
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 |
>
>Išvestis
Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>
Pirmosios paieškos išsamios analizės sudėtingumo analizė:
- Laiko sudėtingumas: O(V + E), kur V – viršūnių skaičius, o E – kraštinių skaičius grafe.
- Pagalbinė erdvė: O(V + E), nes reikalingas papildomas V dydžio lankomas masyvas, o dėklo dydis pasikartojančiam DFS funkcijos iškvietimui.