El primer recorrido en profundidad (o búsqueda) de un gráfico es similar al primer recorrido en profundidad de un árbol. El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos (un Node puede visitarse dos veces). Para evitar procesar un Node más de una vez, use una array visitada booleana.
Ejemplo:
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 {
public:
map<int, bool> visited;
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)
{
adj[v].push_back(w); // Add w to v’s list.
}
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>::iterator 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) \n";
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; // 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);
}
// 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)");
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 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
Javascript
<script>
// 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 < v; 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;
document.write(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 < this.V; i++)
visited[i] = false;
// Call the recursive helper
// function to print DFS
// traversal
this.DFSUtil(v, visited);
}
}
// Driver Code
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);
document.write("Following is Depth First Traversal " +
"(starting from vertex 2)<br>");
g.DFS(2);
// This code is contributed by avanitrachhadiya2155
</script>
C++
// C++ program to print DFS
// traversal for a given
// graph
#include <bits/stdc++.h>
using namespace std;
class Graph {
// A function used by DFS
void DFSUtil(int v);
public:
map<int, bool> visited;
map<int, list<int> > adj;
// function to add an edge to graph
void addEdge(int v, int w);
// prints DFS traversal of the complete graph
void DFS();
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(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>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i);
}
// The function to do DFS traversal. It uses recursive
// DFSUtil()
void Graph::DFS()
{
// Call the recursive helper function to print DFS
// traversal starting from all vertices one by one
for (auto i : adj)
if (visited[i.first] == false)
DFSUtil(i.first);
}
// Driver Code
int main()
{
// Create a graph given in the above diagram
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 9);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(9, 3);
cout << "Following is Depth First Traversal \n";
g.DFS();
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; // 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);
}
// 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");
g.DFS();
}
}
// This code is contributed by Aakash Hasija
Python3
'''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.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):
# create a set to store all visited vertices
visited = set()
# call the recursive helper function to print DFS traversal starting from all
# vertices one by one
for vertex in self.graph:
if vertex not in visited:
self.DFSUtil(vertex, visited)
# Driver code
# create a graph given in the above diagram
print("Following is Depth First Traversal \n")
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)
g.DFS()
# Improved by Dheeraj Kumar
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
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
Javascript
<script>
// 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).fill([]);
}
// Function to Add an edge into the graph
AddEdge(v, w) {
this.adj[v].push(w); // Add w to v's list.
}
// A function used by DFS
DFSUtil(v, visited)
{
// Mark the current
// node as visited and print it
visited[v] = true;
document.write(v + " ");
// Recur for all the
// vertices adjacent to this
// vertex
for (const n of this.adj[v]) {
if (!visited[n]) this.DFSUtil(n, visited);
}
}
// The function to do
// DFS traversal. It uses recursive
// DFSUtil()
DFS()
{
// Mark all the vertices as not visited(set as
var visited = new Array(this.V).fill(false);
// Call the recursive helper
// function to print DFS
// traversal starting from
// all vertices one by one
for (var i = 0; i < this.V; ++i)
if (visited[i] == false) this.DFSUtil(i, visited);
}
}
// Driver Code
var 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);
document.write("Following is Depth First Traversal<br>");
g.DFS();
// This code is contributed by rdtank.
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA