Consider the java code for BFS and DFS provided: DFS: // Java program to print DFS //
Question:
Consider the java code for BFS and DFS provided:
DFS:
// Java program to print DFS // mtraversal 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 private LinkedListadj[];
// Constructor @SuppressWarnings("unchecked") Graph(intv) { V = v; adj = newLinkedList[v]; for (int i = 0;i < v; ++i) adj[i]= new LinkedList(); }
// Function to add an edge into thegraph 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, booleanvisited[]) { // Mark thecurrent node as visited and print it visited[v] =true; System.out.print(v+ " ");
// Recur for allthe vertices adjacent to this // vertex Iteratori = adj[v].listIterator(); while(i.hasNext()) { intn = i.next(); if(!visited[n]) DFSUtil(n,visited); } }
// The function to do DFS traversal. // It uses recursive // DFSUtil() void DFS(int v) { // Mark all thevertices as // notvisited(set as // false bydefault in java) booleanvisited[] = new boolean[V];
// Call therecursive helper // function toprint DFS // traversal DFSUtil(v,visited); }
// Driver Code public static void main(Stringargs[]) { Graph g = newGraph(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( "Followingis Depth First Traversal " +"(starting from vertex 2)");
g.DFS(2); } } BFS: // Java program to print BFS traversal from a given sourcevertex. // BFS(int s) traverses vertices reachable from s. import java.io.*; import java.util.*;
// This class represents a directed graph using adjacencylist // representation class Graph { private int V; // No. ofvertices private LinkedList adj[];//Adjacency Lists
// Constructor Graph(int v) { V = v; adj = newLinkedList[v]; for (int i=0;i adj[i]= new LinkedList(); }
// Function to add an edge into thegraph void addEdge(int v,int w) { adj[v].add(w); }
// prints BFS traversal from a givensource s void BFS(int s) { // Mark all thevertices as not visited(By default // set asfalse) booleanvisited[] = new boolean[V];
// Create aqueue for BFS LinkedListqueue = new LinkedList();
// Mark thecurrent node as visited and enqueue it visited[s]=true; queue.add(s);
while(queue.size() != 0) { //Dequeue a vertex from queue and print it s= queue.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 Iteratori = adj[s].listIterator(); while(i.hasNext()) { intn = i.next(); if(!visited[n]) { visited[n]= true; queue.add(n); } } } }
// Driver method to public static void main(Stringargs[]) { Graph g = newGraph(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("Followingis Breadth First Traversal "+ "(startingfrom vertex 2)");
g.BFS(2); } } |
Business Data Communications Infrastructure Networking and Security
ISBN: 978-0133023893
7th edition
Authors: William Stallings, Tom Case