Reference no: EM1370648

Write a java program that will use breadth-first search (that you implement as part of your program) to find the closest broadcast vertex for each vertex in a graph. The graph represents a communication network, with vertices representing nodes in the network and edges representing links in the network. Some of the vertices are designated as broadcast, to indicate that any message arriving at the network will be broadcast from there; all entering messages would be broadcast from all such vertices simultaneously. What we would like to determine is, for each vertex in the graph, which of the broadcast vertices is the closest to it. Distance is measured by the number of links in the shortest path between nodes. If a vertex is itself a broadcast vertex, than it would be its own closest such vertex.

The graph is given by its adjacency list (input as discussed below), where all vertices are numbered with consecutive integers, starting at 0. Input specification: The input should be read from standard input. The first line of the input will be two integers, indicating the number of vertices n and the number of edges m. The second line lists the indices of the broadcast vertices. Each of the following m lines lists a pair of indices that correspond to the vertices of an edge.
Example input:

7 8
0 1 2
0 1
0 4
0 5
1 3
2 3
2 4
3 4
3 5

Output specification: The output should be written to standard output. It should consist of a single line that gives, in ascending vertex index order, which broadcast vertex is the closest for each vertex in the graph. Ties should be broken by giving the closest broadcast vertex with the smallest index. If there is no broadcast vertex that can reach a vertex, print N. Example output:

0 1 2 1 0 0 N

You can assume that the input is correct according to the specification. Hand in on paper: your source code, and three sample input/output file pairs.