Expert Answer

General Guidance

The answer provided below has been developed in a clear step by step manner.Step: 1

To print DFS of a graph:
Code in JAVA:

import java.io.*;

import java.util.*;

class Graph {

private int V; // No. of vertices

private LinkedList adj[]; //Adjacency Lists

// Constructor

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 u, int v)

{

adj[u].add(v);

}

// A function used by DFS

void calc(int v, boolean vis[])

{

// Mark the current node as visited and print it

vis[v] = true;

System.out.print(v + " ");

// Recur for all the vertices adjacent to this vertex

Iterator i = adj[v].listIterator();

while (i.hasNext())

{

int n = i.next();

if (!vis[n])

calc(n, vis);

}

}

void DFS(int v)

{

// Mark all the vertices as not visited(set as false by default in java)

boolean vis[] = new boolean[V];

// Call the recursive function to print DFS traversal.

calc(v, vis);

}

public static void main(String args[])

{

Graph g = new Graph(8);

g.addEdge(0, 1);

g.addEdge(3, 2);

g.addEdge(5, 2);

g.addEdge(3, 5);

g.addEdge(3, 4);

g.addEdge(4, 6);

g.addEdge(6, 3);

g.addEdge(6, 7);

g.addEdge(7, 1);

System.out.print("DFS traversal from vertex 3 is: ");

g.DFS(3);

}

}

Input:
Vertex a = 0 Vertex b = 1
Vertex c = 2 Vertex d = 3
Vertex e = 4 Vertex f = 5
Vertex g = 6 Vertex h = 7
Output:
DFS traversal from vertex 3 is: 3 2 5 4 6 7 1
DFS is d c f e g h a
Time complexity: O(V + E)
Auxiliary Space: O(V)
Explanation:Please refer to solution in this step.Step: 2

To print BFS of a graph:
Code in JAVA:

import java.io.*;

import java.util.*;

class Graph

{

private int V; // No. of vertices

private LinkedList adj[]; //Adjacency Lists

// Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

for (int i=0; i
adj[i] = new LinkedList();

}

// Function to add an edge into the graph

void addEdge(int u,int v)

{

adj[u].add(v);

}

// prints BFS traversal from a given source s

void BFS(int s)

{

// Mark all the vertices as not visited(By default set as false)

boolean vis[] = new boolean[V];

// Create a queue for BFS

LinkedList q = new LinkedList();

// Mark the current node as visited and enqueue it

vis[s]=true;

q.add(s);

while (q.size() != 0)

{

// Dequeue a vertex from queue and print it

s = q.poll();

System.out.print(s+" ");

// Get all adjacent vertices of the dequeued vertex s if a adjacent has not been visited, then mark it visited and enqueue it

Iterator i = adj[s].listIterator();

while (i.hasNext())

{

int n = i.next();

if (!vis[n])

{

vis[n] = true;

q.add(n);

}

}

}

}

public static void main(String args[])

{

Graph g = new Graph(8);

g.addEdge(0, 1);

g.addEdge(3, 2);

g.addEdge(5, 2);

g.addEdge(3, 5);

g.addEdge(3, 4);

g.addEdge(4, 6);

g.addEdge(6, 3);

g.addEdge(6, 7);

g.addEdge(7, 1);

System.out.print("BFS traversal from vertex 0 is: ");

g.BFS(0);

}

}

Input:
Vertex a = 0 Vertex b = 1
Vertex c = 2 Vertex d = 3
Vertex e = 4 Vertex f = 5
Vertex g = 6 Vertex h = 7
Output:
BFS traversal from vertex 0 is: 0 1
BFS is a b Time Complexity: O(V+E)
Auxiliary Space: O(V)
Explanation:
The above code is for printing bfs(breadth first search) of a graph.

Answer:

I have added code for both DFS and BFS of a graph.
You can directly copy and paste the code in any JAVA compiler.
DFS is d c f e g h a (from node d)
BFS is a b (from node a)
Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V)