logo

TechCodeview

Pirmā dziļuma meklēšana vai diagrammas DFS

Pirmā dziļuma šķērsošana (vai DFS) jo grafiks ir līdzīgs Dziļums Pirmā koka šķērsošana. Vienīgā fiksācija šeit ir tāda, ka atšķirībā no kokiem grafikos var būt cikli (mezglu var apmeklēt divas reizes). Lai izvairītos no mezgla apstrādes vairāk nekā vienu reizi, izmantojiet Būla apmeklēto masīvu. Diagrammā var būt vairāk nekā viena DFS šķērsošana.

Piemērs:

Ievade: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Izvade: DFS no 1. virsotnes: 1 2 0 3
Paskaidrojums:
DFS diagramma:



1. piemērs

1. piemērs

Ievade: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Izvade: DFS no 2. virsotnes: 2 0 1 3
Paskaidrojums:
DFS diagramma:

2. piemērs

2. piemērs

Ieteicamā prakse Graph DFS Izmēģiniet to!

Kā darbojas DFS?

Meklēšana pēc dziļuma ir algoritms koka vai grafika datu struktūru šķērsošanai vai meklēšanai. Algoritms sākas saknes mezglā (grafa gadījumā izvēloties kādu patvaļīgu mezglu kā saknes mezglu) un pēc iespējas tālāk izpēta katru atzaru pirms atkāpšanās.

Ļaujiet mums saprast darbību Pirmā dziļuma meklēšana ar šādas ilustrācijas palīdzību:

1. darbība: Sākotnēji kaudze un apmeklētie masīvi ir tukši.

kā centrēt attēlu uz css

Stack un apmeklētie masīvi sākotnēji ir tukši.

2. darbība: Apmeklējiet 0 un ievietojiet tai blakus esošos mezglus, kas vēl nav apmeklēti, kaudzē.

Apmeklējiet mezglu 0 un ievietojiet tā blakus esošos mezglus (1, 2, 3) kaudzē

3. darbība: Tagad mezgls 1 atrodas steka augšpusē, tāpēc apmeklējiet 1. mezglu un izņemiet to no steka un ievietojiet kaudzē visus blakus esošos mezglus, kas nav apmeklēti.

Apmeklējiet 1. mezglu

4. darbība: Tagad 2. mezgls steka augšdaļā, tāpēc apmeklējiet 2. mezglu un izņemiet to no steka un ievietojiet kaudzē visus blakus esošos mezglus, kas nav apmeklēti (t.i., 3., 4.).

celtnieka dizaina modelis

Apmeklējiet 2. mezglu un ievietojiet tā neapmeklētos blakus mezglus (3, 4) kaudzē

5. darbība: Tagad 4. mezgls atrodas steka augšdaļā, tāpēc apmeklējiet 4. mezglu un izņemiet to no steka un ievietojiet kaudzē visus blakus esošos mezglus, kas nav apmeklēti.

Apmeklējiet 4. mezglu

6. darbība: Tagad 3. mezgls steka augšpusē, tāpēc apmeklējiet 3. mezglu un izņemiet to no steka un ievietojiet kaudzē visus blakus esošos mezglus, kas nav apmeklēti.

Apmeklējiet 3. mezglu

Tagad Stack kļūst tukšs, kas nozīmē, ka esam apmeklējuši visus mezglus un mūsu DFS šķērsošana beidzas.

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

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>>apmeklēja;> >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>>::iterators 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> 

>

>

virknes apakšvirkne

Python3




java izlauzās no cilpas
# 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>>[in ];> >for> (>int> i = 0; i adj[i] = new List (); } // Funkcija malas pievienošanai grafikam void AddEdge(int v, int w) { // Pievienot w v's sarakstam. adj[v].Pievienot(w); } // DFS izmantotā funkcija void DFSUtil(int v, bool[] apmeklēts) { // Atzīmēt pašreizējo mezglu kā apmeklētu // un izdrukāt to apmeklēto[v] = true; Console.Write(v + ' '); // Atkārtot visām virsotnēm //, kas atrodas blakus šim virsotņu sarakstam vList = adj[v]; foreach(var n in vList) { if (!visited[n]) DFSUtil(n, apmeklēja); } } // Funkcija DFS pārvietošanai. // Tas izmanto rekursīvu DFSUtil() void DFS(int v) { // Atzīmēt visas virsotnes kā neapmeklētas // (pēc noklusējuma c# iestatīts kā false) bool[] visited = new bool[V]; // Izsauciet rekursīvo palīgfunkciju // lai izdrukātu DFS traversal DFSUtil(v, apmeklēts); } // Draivera kods public static void Main(String[] args) { Graph g = new Graph(4); g.PievienotEdge(0, 1); g.PievienotEdge(0, 2); g.PievienotEdge(1, 2); g.PievienotEdge(2, 0); g.PievienotEdge(2, 3); g.PievienotEdge(3, 3); Console.WriteLine( 'Seko dziļuma pirmā apbraukšana ' + '(sākot no 2. virsotnes)'); // Funkcijas izsaukums g.DFS(2); Console.ReadKey(); } } // Šo kodu nodrošina techno2mahi> 

>

>

kas ir Android Lieldienu ola

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 

>

>

Izvade 

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

Pirmās padziļinātās meklēšanas sarežģītības analīze:

  • Laika sarežģītība: O(V + E), kur V ir virsotņu skaits un E ir grafa malu skaits.
  • Palīgtelpa: O(V + E), jo ir nepieciešams papildu apmeklētais masīvs V izmērā, kā arī steka lielums iteratīvai DFS funkcijas izsaukšanai.