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

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
icon
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
Transcribed Image Text:(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
Transcribed Image Text: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

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Maximum Flow
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.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education