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
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](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8bf221b6-1639-48b5-921c-5559c65156e9%2F0327bcf6-ded0-40c8-8461-6575157099b8%2F2wefnj6_processed.jpeg&w=3840&q=75)
![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](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8bf221b6-1639-48b5-921c-5559c65156e9%2F0327bcf6-ded0-40c8-8461-6575157099b8%2Fl4xrm3_processed.png&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)