Breath First Search DistanceGiven a directed graph as an adjacency list, you will determine, in this challenge, the breath first search distance of all nodes from a starting vertex, s, assuming that the weight of each edge is 1.In the example graph belove, for s=0, the distances of each vertex from s are0 1 1 2 3The output includes the distances for the vertices, 0, 1, 2, 3, 4, in the order of the vertex number.If s=1, then the output will be-1 0 -1 1 2For the starting vertex 1, the vertex 0 and 2 are unreachable, so the corresponding BFS distances are -1 and -1.Input FormatFirst line in the input contains the starting vertex sEach of the subsequent lines contains two space-separated integers, v and w, that represents an edge from the node v to w.ConstraintsNode numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1.Output FormatPrint the distace of each vertex from the start vertex in the order of the vertex number.Sample Input 00 0 1 0 2 1 3 3 4Sample Output 00 1 1 2 3Sample Input 11 0 1 0 2 1 3 3 4Sample Output 1-1 0 -1 1 2 (1)(4(21 vimport java.io.*;2 import java.util.*;3 import java.util.stream.Collectors;45 vpublic class Solution {public static class DirectedGraph {/* Adjacency List representation of the given graph */private Map> adjList = new HashMap> ();10public String tostring() {StringBuffer s = new StringBuffer ();for (Integer v : adjlist.keySet())s. append ("\nreturn s.toString ();}111314" + v + " -> " + adjList.get (v));15161718public void add (Integer vertex) {if (adjList.containskey (vertex))1920return;21adjList.put(vertex, new Arraylist());}2223public void add (Integer source, Integer dest) {add (source);add (dest);adjList.get (source).add (dest);242526282930/* Indegree of each vertex as a Map */public Map inDegree () {Map result = new HashMap ();for (Integer v : adjlist.keySet ())result.put(v, 0);for (Integer from : adjList.keySet ()) {for (Integer to : adjlist.get(from)) {31323334353637result.put (to, result.get(to) + 1);383940return result;414243public Map outDegree () {Map result = new HashMap ();for (Integer v : adjList.keySet())result.put (v, adjList.get(v).size());return result;44454647484950}3.N34 n67 00 o 123 456 00 9 o 123mtn6 N 00 O o.IN2 233 m3m m3nmmo 4950515253// Complete the bfsDistance function below.public static Map bfsDistance (DirectedGraph digraph, Integer start) {Map distance = new HashMap ();545556return distance;}575859public static void main(String[] args) throws I0Exception {60Bufferedwriter bufferedwriter = new Bufferedwriter (new Filewriter (System.getenv ("OUTPUT_PATH")));616263BufferedReader bufferedReader = new BufferedReader (new InputStreamReader (System.in));6465int svertex = Integer.parseInt (bufferedReader.readLine ().trim ());6667DirectedGraph digraph = new DirectedGraph();6869String line;while ((line = bufferedReader.readline ()) != null) {String[] v = line.split(" ");digraph.add (Integer.parseInt(v[0]), Integer.parseInt (v[1]));7071727374Map bfsd = bfsDistance (digraph, sVertex);String s = bfsd.entrySet().stream ().map (e -> String.value0f(e.getValue())).collect(Collectors.joining(" "));bufferedwriter.write(s);7576777879bufferedReader.close();80bufferedwriter.close();81}82 }83

Here as the given graph is acyclic, we only visit a node for one time. If the graph is cyclic then…

Answered: Breath First Search Distance Given a…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Breath First Search Distance

Given a directed graph as an adjacency list, you will determine, in this challenge, the breath first search distance of all nodes from a starting vertex, s, assuming that the weight of each edge is 1.

In the example graph belove, for s=0, the distances of each vertex from s are

0 1 1 2 3

The output includes the distances for the vertices, 0, 1, 2, 3, 4, in the order of the vertex number.

If s=1, then the output will be

-1 0 -1 1 2

For the starting vertex 1, the vertex 0 and 2 are unreachable, so the corresponding BFS distances are -1 and -1.

Input Format

First line in the input contains the starting vertex s
Each of the subsequent lines contains two space-separated integers, v and w, that represents an edge from the node v to w.

Constraints

Node numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1.

Output Format

Print the distace of each vertex from the start vertex in the order of the vertex number.

Sample Input 0

0 0 1 0 2 1 3 3 4

Sample Output 0

0 1 1 2 3

Sample Input 1

1 0 1 0 2 1 3 3 4

Sample Output 1

-1 0 -1 1 2

(1)
(4
(2
1 vimport java.io.*;
2 import java.util.*;
3 import java.util.stream.Collectors;
4
5 vpublic class Solution {
public static class DirectedGraph {
/* Adjacency List representation of the given graph */
private Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>> ();
10
public String tostring() {
StringBuffer s = new StringBuffer ();
for (Integer v : adjlist.keySet())
s. append ("\n
return s.toString ();
}
11
13
14
" + v + " -> " + adjList.get (v));
15
16
17
18
public void add (Integer vertex) {
if (adjList.containskey (vertex))
19
20
return;
21
adjList.put(vertex, new Arraylist<Integer>());
}
22
23
public void add (Integer source, Integer dest) {
add (source);
add (dest);
adjList.get (source).add (dest);
24
25
26
28
29
30
/* Indegree of each vertex as a Map<vertex, IndegreeValue> */
public Map<Integer, Integer> inDegree () {
Map<Integer, Integer> result = new HashMap<Integer, Integer> ();
for (Integer v : adjlist.keySet ())
result.put(v, 0);
for (Integer from : adjList.keySet ()) {
for (Integer to : adjlist.get(from)) {
31
32
33
34
35
36
37
result.put (to, result.get(to) + 1);
38
39
40
return result;
41
42
43
public Map<Integer, Integer> outDegree () {
Map<Integer, Integer> result = new HashMap<Integer, Integer> ();
for (Integer v : adjList.keySet())
result.put (v, adjList.get(v).size());
return result;
44
45
46
47
48
49
50
}
3.
N34 n67 00 o 123 456 00 9 o 123mtn6 N 00 O o.
IN2 233 m3m m3nmmo

49
50
51
52
53
// Complete the bfsDistance function below.
public static Map<Integer, Integer> bfsDistance (DirectedGraph digraph, Integer start) {
Map<Integer, Integer> distance = new HashMap<Integer, Integer> ();
54
55
56
return distance;
}
57
58
59
public static void main(String[] args) throws I0Exception {
60
Bufferedwriter bufferedwriter = new Bufferedwriter (new Filewriter (System.getenv ("OUTPUT_PATH")));
61
62
63
BufferedReader bufferedReader = new BufferedReader (new InputStreamReader (System.in));
64
65
int svertex = Integer.parseInt (bufferedReader.readLine ().trim ());
66
67
DirectedGraph digraph = new DirectedGraph();
68
69
String line;
while ((line = bufferedReader.readline ()) != null) {
String[] v = line.split(" ");
digraph.add (Integer.parseInt(v[0]), Integer.parseInt (v[1]));
70
71
72
73
74
Map<Integer, Integer> bfsd = bfsDistance (digraph, sVertex);
String s = bfsd.entrySet().stream ().map (e -> String.value0f(e.getValue())).collect(Collectors.joining(" "));
bufferedwriter.write(s);
75
76
77
78
79
bufferedReader.close();
80
bufferedwriter.close();
81
}
82 }
83

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.