本文概述

• 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的最新文章

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

推荐阅读

• 

  长期用盐水泡脚行不行，听说可以杀菌！
• 

  邯郸市科技馆参观注意事项是什么 邯郸市科技馆参观注意事项
• 

  环球影城|联想1月21日包场环球影城，耗资或超800万元
• 

  医保|打一针要70万，这种药为什么没入医保？
• 

  给特别的学术会议 学术会议邀请函
• 

  北京交通大学2021-2022校历 北京交通大学2022-2023学年校历一览
• 

  西藏下雪会封山吗 十月份西藏会下雪吗
• 

  生姜贴脚底能去湿气吗
• 

  如何激活保德服务器的网卡？ 保德服务器网卡怎么激活
• 

  深圳直播教程培训，深圳直播教程培训机构
• 

  初中生用手机能提高学习成绩吗？
• 

  国际高中学校里,校风和教学好的有哪些？
• 

  留给国美的时间不多了
• 

  平常的书法08
• 

  小客厅装修效果图欣赏
• 

  在游戏中以下不属于超新星势力的是 航海王燃烧意志微信每日一题11月30日答案
• 

  本图文详细教程教你如何安装一款好用的windows10
• 

  前列腺炎吃三七粉效果好吗
• 

  栗子烧白菜 栗子烧白菜的烹调方法
• 

  回归分析中rmse与R

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