Syvyys ensimmäinen läpikäynti (tai DFS) sillä kaavio on samanlainen kuin Syvyys Ensimmäinen puun läpikulku. Ainoa saalis tässä on se, että toisin kuin puut, graafit voivat sisältää jaksoja (solmussa voidaan käydä kahdesti). Voit välttää solmun käsittelyn useammin kuin kerran käyttämällä loogista vierailtua taulukkoa. Kaaviossa voi olla useampi kuin yksi DFS-läpikulku.
Esimerkki:
Graphin suositeltu DFS-käytäntö Kokeile sitä!Syöte: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Lähtö: DFS kärjestä 1 : 1 2 0 3
Selitys:
DFS-kaavio:
Esimerkki 1
Syöte: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Lähtö: DFS kärjestä 2: 2 0 1 3
Selitys:
DFS-kaavio:Esimerkki 2
Miten DFS toimii?
Syvyys-ensin haku on algoritmi puu- tai graafitietorakenteiden läpikulkuun tai etsimiseen. Algoritmi alkaa juurisolmusta (valitsee jokin mielivaltainen solmu juurisolmuksi graafin tapauksessa) ja tutkii niin pitkälle kuin mahdollista jokaista haaraa pitkin ennen paluuta.
Ymmärtäkäämme toiminta Syvyys ensimmäinen haku seuraavan kuvan avulla:
Vaihe 1: Aluksi pino ja vierailevat taulukot ovat tyhjiä.
paikallinen javaPino ja vieraillut taulukot ovat aluksi tyhjiä.
Vaihe 2: Vieraile 0:ssa ja laita sen viereiset solmut, joissa ei ole vielä vierailtu, pinoon.
Vieraile solmussa 0 ja laita sen viereiset solmut (1, 2, 3) pinoon
Vaihe 3: Nyt solmu 1 pinon yläosassa, joten käy solmussa 1 ja nosta se pinosta ja laita pinoon kaikki sen viereiset solmut, joissa ei käy.
Vieraile solmussa 1
Vaihe 4: Nyt, Solmu 2 pinon yläosassa, joten käy solmussa 2 ja poista se pinosta ja laita pinoon kaikki sen viereiset solmut, joissa ei käy (eli 3, 4).
rekha ikäVieraile solmussa 2 ja laita sen vierailemattomat vierekkäiset solmut (3, 4) pinoon
Vaihe 5: Nyt solmu 4 pinon yläosassa, joten käy solmussa 4 ja nosta se pinosta ja laita pinoon kaikki sen viereiset solmut, joissa ei käy.
Vieraile solmussa 4
Vaihe 6: Nyt solmu 3 pinon yläosassa, joten käy solmussa 3 ja nosta se pinosta ja laita pinoon kaikki sen viereiset solmut, joissa ei käy.
Vieraile solmussa 3
Nyt pinosta tulee tyhjä, mikä tarkoittaa, että olemme käyneet kaikissa solmuissa ja DFS-läpikulkumme päättyy.
Alla on yllä olevan lähestymistavan toteutus:
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>>vieraillut;> >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>>::iteraattori 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
mikä on monitori
// 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> |
>
>
Python 3
# 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#
perintöohjelma pythonissa
// 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>>[ in ];> >for> (>int> i = 0; i adj[i] = new List |
>
>
skriptien ajaminen linuxissa
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 |
>
>Lähtö
Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>
Ensimmäisen syvähaun monimutkaisuusanalyysi:
- Aika monimutkaisuus: O(V + E), jossa V on graafin kärkien lukumäärä ja E on graafin reunojen lukumäärä.
- Aputila: O(V + E), koska vaaditaan ylimääräinen vierailtu taulukko, jonka koko on V, ja pinon koko DFS-funktion iteratiivista kutsua varten.