DepthFirstSearchorDFSforaGraph
package depthfirstsearchordfsforagraph;
// 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
public class DepthFirstSearchorDFSforaGraph {
private int V; // No. of vertices
// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];
// Constructor
DepthFirstSearchorDFSforaGraph(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[])
{
DepthFirstSearchorDFSforaGraph g = new DepthFirstSearchorDFSforaGraph(8);
g.addEdge(0, 1);
g.addEdge(1, 0);
g.addEdge(0, 4);
g.addEdge(1, 6);
g.addEdge(5, 1);
g.addEdge(2, 5);
g.addEdge(6, 2);
g.addEdge(4, 2);
g.addEdge(5, 3);
g.addEdge(6, 4);
g.addEdge(4,6);
g.addEdge(5, 7);
System.out.println("Following is Depth First Traversal "+
"(starting from vertex 5)");
g.DFS(5);
}
}
// This code is contributed by Aakash Hasija
Download here
https://drive.google.com/file/d/1BxZ87bGyWDANY7ZokyYSsw1ZVDz4Yrm9/view?usp=sharing
