图的深度优先搜索或DFS算法如何实现？

2021年3月29日14:09:08 发表评论 1,038 次浏览

本文概述

深度优先遍历(或搜索)对于图类似于一棵树的深度优先搜索。唯一的问题是, 与树不同, 图可能包含循环, 一个节点可能被访问两次。为避免多次处理节点, 请使用布尔访问数组。

例子：

输入：n = 4, e = 6
0-> 1, 0-> 2, 1-> 2, 2-> 0, 2-> 3, 3-> 3
输出：来自顶点的DFS 1：1 2 0 3
说明：DFS图：
输入：n = 4, e = 6
2-> 0, 0-> 2, 1-> 2, 0-> 1, 3-> 3, 1-> 3
输出：来自顶点2的DFS：2 0 1 3
说明：DFS图：

先决条件：看到这个帖子适用于深度优先搜索的所有应用。

以下是简单的深度优先搜索的实现。 C ++实现使用邻接表表示图。STL‘s列出容器用于存储相邻节点的列表。

解：

方法：

深度优先搜索是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始(在图形的情况下, 选择任意节点作为根节点), 并在回溯之前沿每个分支尽可能地探索。因此, 基本思想是从根节点或任意节点开始, 标记该节点, 然后移至相邻的未标记节点, 然后继续此循环, 直到没有未标记的相邻节点为止。然后回溯并检查其他未标记的节点并搜索它们。最后打印路径中的节点。

算法：

  1. 创建一个递归函数, 该函数采用节点和已访问数组的索引。
  2. 将当前节点标记为已访问并打印该节点。
  3. 遍历所有相邻和未标记的节点, 并使用相邻节点的索引调用递归函数。

实现

C ++

// C++ program to print DFS traversal from
// a given vertex in a  given graph
#include<bits/stdc++.h>
using namespace std;
  
// Graph class represents a directed graph
// using adjacency list representation
class Graph
{
     int V;    // No. of vertices
  
     // Pointer to an array containing
     // adjacency lists
     list< int > *adj;
  
     // A recursive function used by DFS
     void DFSUtil( int v, bool visited[]);
public :
     Graph( int V);   // Constructor
  
     // 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);
};
  
Graph::Graph( int V)
{
     this ->V = V;
     adj = new list< int >[V];
}
  
void Graph::addEdge( int v, int w)
{
     adj[v].push_back(w); // Add w to v’s list.
}
  
void Graph::DFSUtil( int v, bool visited[])
{
     // 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])
             DFSUtil(*i, visited);
}
  
// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS( int v)
{
     // Mark all the vertices as not visited
     bool *visited = new bool [V];
     for ( int i = 0; i < V; i++)
         visited[i] = false ;
  
     // Call the recursive helper function
     // to print DFS traversal
     DFSUtil(v, visited);
}
  
// Driver code
int main()
{
     // Create a graph given in the above diagram
     Graph g(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);
  
     cout << "Following is Depth First Traversal"
             " (starting from vertex 2) \n" ;
     g.DFS(2);
  
     return 0;
}

Java

// Java program to print DFS traversal from a given given graph
import java.io.*;
import java.util.*;
  
// This class represents a directed graph using adjacency list
// representation
class Graph
{
     private int V;   // No. of vertices
  
     // Array  of lists for Adjacency List Representation
     private LinkedList<Integer> adj[];
  
     // Constructor
     @SuppressWarnings ( "unchecked" )
     Graph( int v)
     {
         V = v;
         adj = new LinkedList[v];
         for ( int i= 0 ; i<v; ++i)
             adj[i] = new LinkedList();
     }
  
     //Function to add an edge into the graph
     void addEdge( int v, int w)
     {
         adj[v].add(w);  // Add w to v's list.
     }
  
     // 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<Integer> 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);
     }
  
     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)" );
  
         g.DFS( 2 );
     }
}
// This code is contributed by Aakash Hasija

Python3

# Python3 program to print DFS traversal 
# from a given 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[v] = True
         print (v, end = ' ' )
  
         # Recur for all the vertices 
         # adjacent to this vertex
         for i in self .graph[v]:
             if visited[i] = = False :
                 self .DFSUtil(i, visited)
  
     # The function to do DFS traversal. It uses
     # recursive DFSUtil()
     def DFS( self , v):
  
         # Mark all the vertices as not visited
         visited = [ False ] * ( max ( self .graph) + 1 )
  
         # Call the recursive helper function 
         # to print DFS traversal
         self .DFSUtil(v, visited)
  
# Driver code
  
# Create a graph given 
# in the above diagram
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 DFS from (starting from vertex 2)" )
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; // No. of vertices 
  
     // 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 < v; ++i)
             adj[i] = new List< int >();
     }
  
     //Function to Add an edge into the graph 
     void AddEdge( int v, int w)
     {
         adj[v].Add(w); // Add w to v's list. 
     }
  
     // A function used by DFS 
     void DFSUtil( int v, bool [] visited)
     {
         // Mark the current node as visited
         // and print it 
         visited[v] = true ;
         Console.Write(v + " " );
  
         // Recur for all the vertices 
         // adjacent to this vertex 
         List< int > vList = adj[v];
         foreach ( var n in vList)
         {
             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 c#) 
         bool [] visited = new bool [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);
  
         Console.WriteLine( "Following is Depth First Traversal " +
                           "(starting from vertex 2)" );
  
         g.DFS(2);
         Console.ReadKey();
     }
}
  
// This code is contributed by techno2mahi

输出如下：

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

复杂度分析：

  • 时间复杂度：O(V + E), 其中V是顶点数, E是图形中边的数量。
  • 空间复杂度：O(V)。
    由于需要一个额外的访问数组, 其大小为V。

处理断开的图

解：

这将通过处理极端情况来发生。

上面的代码仅遍历从给定源顶点可到达的顶点。像"断开图"的情况一样, 可能无法从给定的顶点到达所有顶点。要完成此类图的DFS搜索, 请在DFS之后从所有未访问的节点运行DFS。

递归函数保持不变。

算法：

  1. 创建一个递归函数, 该函数采用节点和已访问数组的索引。
  2. 将当前节点标记为已访问并打印该节点。
  3. 遍历所有相邻和未标记的节点, 并使用相邻节点的索引调用递归函数。
  4. 运行从0到顶点数的循环, 并检查是否在以前的DFS中未访问该节点, 然后使用当前节点调用递归函数。

实现

C ++

// C++ program to print DFS traversal for a given given graph
#include<bits/stdc++.h>
using namespace std;
  
class Graph
{
     int V;    // No. of vertices
     list< int > *adj;    // Pointer to an array containing adjacency lists
     void DFSUtil( int v, bool visited[]);  // A function used by DFS
public :
     Graph( int V);   // Constructor
     void addEdge( int v, int w);   // function to add an edge to graph
     void DFS();    // prints DFS traversal of the complete graph
};
  
Graph::Graph( int V)
{
     this ->V = V;
     adj = new list< int >[V];
}
  
void Graph::addEdge( int v, int w)
{
     adj[v].push_back(w); // Add w to v’s list.
}
  
void Graph::DFSUtil( int v, bool visited[])
{
     // 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])
             DFSUtil(*i, visited);
}
  
// The function to do DFS traversal. It uses recursive DFSUtil()
void Graph::DFS()
{
     // Mark all the vertices as not visited
     bool *visited = new bool [V];
     for ( int i = 0; i < V; i++)
         visited[i] = false ;
  
     // Call the recursive helper function to print DFS traversal
     // starting from all vertices one by one
     for ( int i = 0; i < V; i++)
         if (visited[i] == false )
             DFSUtil(i, visited);
}
  
int main()
{
     // Create a graph given in the above diagram
     Graph g(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);
  
     cout << "Following is Depth First Traversaln" ;
     g.DFS();
  
     return 0;
}

Java

// Java program to print DFS traversal from a given given graph
import java.io.*;
import java.util.*;
  
// This class represents a directed graph using adjacency list
// representation
class Graph
{
     private int V;   // No. of vertices
  
     // Array  of lists for Adjacency List Representation
     private LinkedList<Integer> adj[];
  
     // Constructor
     @SuppressWarnings ( "unchecked" )
     Graph( int v)
     {
         V = v;
         adj = new LinkedList[v];
         for ( int i= 0 ; i<v; ++i)
             adj[i] = new LinkedList();
     }
  
     //Function to add an edge into the graph
     void addEdge( int v, int w)
     {
         adj[v].add(w);    // Add w to v's list.
     }
  
     // 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<Integer> 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()
     {
         // 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
         // starting from all vertices one by one
         for ( int i= 0 ; i<V; ++i)
             if (visited[i] == false )
                 DFSUtil(i, 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 );
  
         System.out.println( "Following is Depth First Traversal" );
  
         g.DFS();
     }
}
// This code is contributed by Aakash Hasija

python

# Python program to print DFS traversal for complete 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[v] = True
         print v, # Recur for all the vertices adjacent to
         # this vertex
         for i in self .graph[v]:
             if visited[i] = = False :
                 self .DFSUtil(i, visited)
  
  
     # The function to do DFS traversal. It uses
     # recursive DFSUtil()
     def DFS( self ):
         V = len ( self .graph)  #total vertices
  
         # Mark all the vertices as not visited
         visited = [ False ] * (V)
  
         # Call the recursive helper function to print
         # DFS traversal starting from all vertices one
         # by one
         for i in range (V):
             if visited[i] = = False :
                 self .DFSUtil(i, visited)
  
  
# Driver code
# Create a graph given in the above diagram
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"
g.DFS()
  
# This code is contributed by Neelam Yadav

C#

// C# program to print DFS traversal from a given given graph 
using System;
using System.Collections.Generic;
  
// This class represents a directed graph using adjacency list 
// representation 
public class Graph 
{ 
     private int V; // No. of vertices 
  
     // 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 < v; ++i) 
             adj[i] = new List< int >(); 
     } 
  
     //Function to add an edge into the graph 
     void addEdge( int v, int w) 
     { 
         adj[v].Add(w); // Add w to v's list. 
     } 
  
     // A function used by DFS 
     void DFSUtil( int v, bool []visited) 
     { 
         // Mark the current node as visited and print it 
         visited[v] = true ; 
         Console.Write(v + " " ); 
  
         // Recur for all the vertices adjacent to this vertex 
         foreach ( int i in adj[v])
         { 
             int n = i; 
             if (!visited[n]) 
                 DFSUtil(n, visited); 
         } 
     } 
  
     // The function to do DFS traversal. It uses recursive DFSUtil() 
     void DFS() 
     { 
         // Mark all the vertices as not visited(set as 
         // false by default in java) 
         bool []visited = new bool [V]; 
  
         // Call the recursive helper function to print DFS traversal 
         // starting from all vertices one by one 
         for ( int i = 0; i < V; ++i) 
             if (visited[i] == false ) 
                 DFSUtil(i, 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); 
  
         Console.WriteLine( "Following is Depth First Traversal" ); 
  
         g.DFS(); 
     } 
} 
  
// This code is contributed by PrinciRaj1992

输出如下：

Following is Depth First Traversal
0 1 2 3

复杂度分析：

  • 时间复杂度：O(V + E), 其中V是顶点数, E是图形中边的数量。
  • 空间复杂度：O(V)。
    由于需要一个额外的访问数组, 其大小为V。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: