ПОШУК ЗА ГЛИБИНОЮ АБО DFS ДЛЯ ГРАФІКА

Перший обхід глибини (або DFS) для графіка подібний до Глибина Перший обхід дерева. Єдина заковика тут полягає в тому, що, на відміну від дерев, графи можуть містити цикли (вузол можна відвідати двічі). Щоб уникнути обробки вузла більше одного разу, використовуйте булевий відвіданий масив. Граф може мати більше одного обходу DFS.

приклад:

введення: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Вихід: DFS з вершини 1 : 1 2 0 3
Пояснення:
Діаграма DFS:

Приклад 1

введення: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Вихід: DFS з вершини 2 : 2 0 1 3
Пояснення:
Діаграма DFS:

Приклад 2

Рекомендована практика DFS of Graph Спробуйте!

Як працює DFS?

Пошук у глибину — це алгоритм для обходу або пошуку структур даних дерева або графа. Алгоритм починається з кореневого вузла (вибираючи довільний вузол як кореневий вузол у випадку графа) і досліджує, наскільки це можливо, вздовж кожної гілки перед зворотним відстеженням.

Давайте зрозуміємо роботу Пошук спочатку на глибину за допомогою наступної ілюстрації:

Крок 1: Спочатку стек і відвідані масиви порожні.

Стек і відвідані масиви спочатку порожні.

Крок 2: Відвідайте 0 і помістіть його сусідні вузли, які ще не відвідано, у стек.

Відвідайте вузол 0 і помістіть його суміжні вузли (1, 2, 3) у стек

крок 3: Тепер вузол 1 у верхній частині стеку, тому відвідайте вузол 1, витягніть його зі стеку та помістіть у стек усі сусідні вузли, які не були відвідані.

Відвідайте вузол 1

крок 4: тепер, Вузол 2 у верхній частині стеку, тому перейдіть до вузла 2 і витягніть його зі стеку та помістіть у стек усі суміжні вузли, які не відвідуються (тобто 3, 4).

Відвідайте вузол 2 і помістіть його невідвідані сусідні вузли (3, 4) у стек

крок 5: Тепер вузол 4 у верхній частині стеку, тож відвідайте вузол 4, витягніть його зі стеку та помістіть у стек усі сусідні вузли, які не були відвідані.

Відвідайте вузол 4

Крок 6: Тепер вузол 3 у верхній частині стеку, тож відвідайте вузол 3, витягніть його зі стеку та помістіть у стек усі сусідні вузли, які не були відвідані.

Відвідайте вузол 3

Тепер стек стає порожнім, що означає, що ми відвідали всі вузли, і наш обхід DFS завершується.

Нижче наведено реалізацію вищезазначеного підходу:

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> >відвідав;> > 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> >::ітератор 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>

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>

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 ();  } // Функція для додавання ребра в граф void AddEdge(int v, int w) { // Додавання w до списку v.  adj[v].Add(w);  } // Функція, яка використовується DFS void DFSUtil(int v, bool[] visited) { // Позначити поточний вузол як відвіданий // і надрукувати його visited[v] = true;  Console.Write(v + ' ');  // Повторюється для всіх вершин // суміжних із цим списком вершин vList = adj[v];  foreach(var n in vList) { if (!visited[n]) DFSUtil(n, visited);  } } // Функція для обходу DFS.  // Він використовує рекурсивний DFSUtil() void DFS(int v) { // Позначає всі вершини як невідвідані // (встановлено як false за замовчуванням у C#) bool[] visited = new bool[V];  // Виклик рекурсивної допоміжної функції // для друку обходу DFS DFSUtil(v, visited);  } // Код драйвера 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);  Console.WriteLine( 'Далі йде перший обхід глибини ' + '(починаючи з вершини 2)');  // Виклик функції g.DFS(2);  Console.ReadKey();  } } // Цей код створено techno2mahi>

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

Вихід

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

Аналіз складності пошуку в глибину:

Часова складність: O(V + E), де V — кількість вершин, а E — кількість ребер у графі.
Допоміжний простір: O(V + E), оскільки потрібен додатковий відвіданий масив розміру V, а також розмір стека для ітераційного виклику функції DFS.