Implement Depth-First Search (DFS) and Breadth-First
Search
(BFS) algorithms for a graph in Java.(Can be any graph, just an
example of DFS and BFS is sufficient)
If it cannot be done for a graph, then just an example of DFS and BFS are enough.
// Program to print Breadth First Search and Depth First Search
for a given grapgh vertex
import java.io.*;
import java.util.*;
// This class represents a graph
class Graph
{
private int V; // No. of
vertices
private LinkedList<Integer> adj[];
//Adjacency Lists
// Constructor to initialize a grapgh
Graph(int v)
{
V = v;
adj = new
LinkedList[v];
for (int i=0; i<v;
++i)
adj[i] = new LinkedList();
}
// Function to add edge into the graph
void addEdge(int v,int w)
{
adj[v].add(w);
}
// Algorith to do breath first search for a
provided vertex s
void BFS(int s)
{
// By default mark all
vertices as false
boolean visited[] = new
boolean[V];
// Create a queue for
BFS
LinkedList<Integer> queue = new
LinkedList<Integer>();
// Mark the current 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
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
}
// Function used by depth first search
void DFSInner(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])
DFSInner(n, visited);
}
}
// Algorith to do depth first search for a
provided vertex s
void DFS(int v)
{
// By
default mark all vertices as false
boolean visited[] = new
boolean[V];
// Call the recursive
helper function to print depth frst search traversal
DFSInner(v,
visited);
}
// Invoke the search algorhtms
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("Breadth First Traversal (starting from vertex
2)");
g.BFS(2);
System.out.println("------------------------------------------------------------------");
System.out.println("Depth First
Traversal (starting from vertex 2)");
g.DFS(2);
}
}
Output:
Following is Breadth First Traversal (starting from vertex 2)
2 0 3 1
------------------------------------------------------------------
Following is Depth First Traversal (starting from vertex 2)
2 0 1 3
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms for a graph in Java....
From the given graph discover the structure of the graph using 1. breadth first search(BFS) a. depth first search(DFS) b. Show the steps and techniques used for each method (20 points) From the given graph discover the structure of the graph using 1. breadth first search(BFS) a. depth first search(DFS) b. Show the steps and techniques used for each method (20 points)
You will be implementing a Breadth-First Search (BFS) and a Depth-First Search (DFS) algorithm on a graph stored as an adjacency list. The AdjacencyList class inherits from the Graph class shown below. class Graph { private: vector _distances; vector _previous; public: Graph() { } virtual int vertices() const = 0; virtual int edges() const = 0; virtual int distance(int) const = 0; virtual void bfs(int) const = 0; virtual void dfs(int) const = 0; virtual void display() const = 0;...
1. In BFS (or DFS), there is an for-loop that invokes the sub-routine bfs (G, s) (dfs(G,s)) Given an undirected graph of n nodes and m edges. If the sub-routine bfs(G, s) (dfs (G,s)) is called k times from BFS (or DFS), how many breadth-first (depth-first) trees have been con- structed? How many edges are there in this forest of breadth-first (depth-first) trees? 1. In BFS (or DFS), there is an for-loop that invokes the sub-routine bfs (G, s) (dfs(G,s))...
Show the operation of depth-first search (DFS) on the graph of Figure 1 starting from vertex q. Always process vertices in alphabetical order. Show the discovery and finish times for each vertex, and the classification of each edge. (b) A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first search (BFS) tree can also be used to classify the edges reachable from the source of the search into the same four categories....
please I need it urgent thanks algorithms second picture is the graph 2.3 Graphs and BFS-DFS 5 points each I. Draw the adjacency matrix for the graph A on the last page. 2. Show the order in which a breadth first traversal will print out the vertices? Assume that if the algorithm has a choice of which vertex to visit, it visits the vertex with the lower number. 3. Find a topological ordering for the graph B on the last...
JAVA LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents the graph. Your code should contain a function called addEdgelint i, int j). Use this function to add the appropriate edges in your matrix. Write code to implement Depth-First-Search (DFS) and Breadth-First-Search (BFS) of your graph. Let 0 be the source Node . Traverse the graph using DFS, print the Nodes as they are visited. . Traverse the...
Solve (a) and (b) using BFS and DFS diagram BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS BFS Given an undirected graph...
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS BFS Given an undirected graph below (a) Show the shortest distance to each vertex...
/* Graph read from file, and represnted as adjacency list. To implement DFS and BFS on the graph */ #include <iostream> #include <sstream> #include <fstream> #include <vector> #include <utility> #include <unordered_map> #include <set> #include <queue> using namespace std; // Each vertex has an integer id. typedef vector<vector<pair<int,int>>> adjlist; // Pair: (head vertex, edge weight) adjlist makeGraph(ifstream& ifs); void printGraph(const adjlist& alist); vector<int> BFS(const adjlist& alist, int source); // Return vertices in BFS order vector<int> DFS(const adjlist& alist, int source); //...
Discuss graph representation, Breadth-first search and Depth-first search. Use examples to highlight pros and cons.