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

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

## 本文概述

0-> 1, 0-> 2, 1-> 2, 2-> 0, 2-> 3, 3-> 3

2-> 0, 0-> 2, 1-> 2, 0-> 1, 3-> 3, 1-> 3

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
class Graph
{
int V;    // No. of vertices

// Pointer to an array containing

// 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)
{
}

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;
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);

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

// Constructor
@SuppressWarnings ( "unchecked" )
Graph( int v)
{
V = v;
for ( int i= 0 ; i<v; ++i)
}

//Function to add an edge into the graph
void addEdge( int v, int 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
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 );

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
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
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()

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
class Graph
{
private int V; // No. of vertices

// Array of lists for

// 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)
{
}

// 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
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);

Console.WriteLine( "Following is Depth First Traversal " +
"(starting from vertex 2)" );

g.DFS(2);
}
}

// 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。

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)
{
}

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;
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);

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

// Constructor
@SuppressWarnings ( "unchecked" )
Graph( int v)
{
V = v;
for ( int i= 0 ; i<v; ++i)
}

//Function to add an edge into the graph
void addEdge( int v, int 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
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 );

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()

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

// 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)
{
}

// 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);

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。