Java program use breadth-first search closest broadcast

Assignment Help JAVA Programming
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. 

Reference no: EM1370648

Previous Q& A

  Description of monopolistic competition

A restaurant industry has a market structure that comes closest to

  Differences between monopolistic competition-pure monopoly

If the economy is at point C, what is the cost of one more automobile? One more rocket? Explain how the production possibilities curve reflects the law of increasing opportunities costs

  Calculate atm fees

A bank in a mediumsized Midwestern city, Company X, currently charges$1 per transaction at it's ATM's. To determine whether to increase price,

  Conflicts of interest faced by an investment advisor

Discuss and explain two conflicts of interest faced by an Investment Advisor who is employed by a commercial bank or an investment bank?

  Explain in the satirical petition on behalf of french

Explain in the satirical petition on behalf of french candlemakers, frederic bastiat, a french economist, called attention to cheap competition from afar

  Calculate maximum amount of new loan

Make an analysis by answering questions below. Suppose that the Bank of Ecoville has the following balance sheet and the Fed has a 10% reserve requirement in place:

  Find maximum value of l if tcp sequence number not exhausted

Determine the maximum value of L such that TCP sequence numbers are not exhausted? Recall that TCP sequence number field has 4 bytes.

  Explain could an investor beat the stock market

Explain Could an investor beat the stock market and generate a superior return with companies that have formulated and implemented a blue ocean strategy

  Computing marginal revenue from advertising

The Smith's Company's marketing manager has determine that the price elasticity of demand for its product equals -2.2. According to the studies he has performed, the relationship between the amount spent by firm on advertising and its sales as fol..

  Explain what are some of the aspects that determine success

Explain What are some of the aspects that determine their success in their contributions? What would success mean to leadership?


Write a Review


Similar Q& A

  Write a recursive program

Write a recursive program to compute the number of ways in which an integer k can be written as sum

  Design and implement a small and simple email server

Design and implement a small and simple email server using the concept of web based information system (WBIS).

  Prepare executable program and a dictionary program

Prepare executable program and a dictionary Program.

  Develop java applet that will help elementary school student

Develop a Java applet that will help an elementary school student learn multiplication. Use the Math.random method or a Random object to produce two positive one-digit integers.

  Write java program to compute how much federal need to pay

Write a java application to calculate how much federal and state tax you need to pay. The program should accomplish the following task.

  Implement a card game in java

In this assignment, you will be asked to implement a card game. You will need to make several design decisions for your code. It will be expected that all classes you write will utilize the principle of encapsulation.

  Simulate a simple multiuser computer system

Prepare a java program to simulate a simple multiuser computer system

  Please write the code in java

Please write the code in java for  Recursion,  Sorting and Searching

  Java program to ask user to enter favorite color

Write a Java program to ask the user to enter favorite color, a favorite food, favorite animal, and first name of a friend or relative.

  Implement a fish-lake simulation

Implement a Fish/Lake simulation similar to the previous assignment. You will then make adjustments to accommodate class hierarchies and make use of inheritance as well as a JAVA interface.

  Write a program that shows the current time and date

Write a program that shows the current time and date

  Create a class safestack that implements a stack of strings

Create a class SafeStack that implements a stack of strings

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd