本文概述

• C ++
• Java
• Python3
• C#
• C ++
• Java
• python
• C#

【图的深度优先搜索或DFS算法如何实现（）】深度优先遍历(或搜索)对于图类似于一棵树的深度优先搜索。唯一的问题是, 与树不同, 图可能包含循环, 一个节点可能被访问两次。为避免多次处理节点, 请使用布尔访问数组。
例子：

输入：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 agiven 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// Arrayof 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// Arrayof 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。

• DFS的应用。
• 图的广度优先搜索
• 关于DFS的最新文章

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

推荐阅读

• 

  南京牌照是什么开头 南京牌照开头是什么
• 

  健康码过了14天隔离期怎么没变色
• 

  红烧茄子买什么茄子
• 

  百得燃气灶不打火是什么原因
• 

  杞人忧天有什么道理的的 杞人忧天成语介绍
• 

  诺曼底号遇难记作者资料
• 

  洛隆县景点
• 

  餐厅文雅点的别名
• 

  《德道经》曰：“圣人无为而无不为”,其中“有为”和“无为”分别是什么意思呢？
• 

  汉成帝迷恋赵合德到什么程度 汉成帝和赵合德
• 

  周昱彤loly是谁
• 

  能上qq不能上网站 能上qq不能上网
• 

  脸部怎么修护
• 

  全脂牛奶好还是脱脂牛奶好？
• 

  抖音寅子是谁 寅子唱过什么歌
• 

  凉薯吃了会胀气吗为什么 凉薯吃了会胀气吗
• 

  袋鼠爸爸安全座椅好不好用？袋鼠爸爸安全座椅值得入手吗
• 

  关于近几年来中印边境冲突不断,你怎么看,会发生战争吗？
• 

  送给朋友的元宵节祝福语2021
• 

  百身何赎是什么意思 百身何赎的解释

• 如何使用递归实现打印给定总和的所有子集（）
• C/C++中的函数如何使用（通俗解释和代码示例）
• jQuery如何使用bind()方法（代码示例）
• 移除最小数量的元素，使两个数组中不存在公共元素
• 苏格兰皇家银行面试经验（校园）
• win10正式版安装最新推荐
• 本图文详细教程教你如何安装windows10的镜像
• win10官网安装最新推荐
• 本图文详细教程教你win10安装win7