Limited access

Upgrade to access all content for this subject

You are setting up a minimum cost communication network between different offices in a building where each office has several different options for installing wires connecting them to other offices in the network. You can think of this setup as a graph where each office is a node in the graph and each wire connecting a pair of offices is an edge connecting the corresponding nodes in the graph.

Each edge in this graph would have a positive weight that is based on the length of the wire connecting the two offices. There is more than one way to do this.

Which of the following options is the best way of representing this graph?

A

A 2-dimensional array where the offices are the rows and columns of the array. An index in the array has a value of 1 if the row office has a wire connecting it to the column office and a 0 otherwise.

B

A 2-dimensional array where the offices are the rows and columns of the array. An index in the array has a value equal to the weight of the edge if the row office has a wire connecting it to the column office and a value of 0 otherwise.

C

A hash table where each office is hashed based on its closeness to the other offices in the network.

D

A binary heap where each office is ranked by the importance of the office's owner in the company.

Select an assignment template