The diameter of the tree T is defined as the length of the longest path of the tree. Write an efficient linear time algorithm to find the diameter of the tree.
Hint: You can apply DFS as part of your solution.
One interesting way to implement topological sort in a directed acyclic graph G is to repeatedly finding nodes of in-degree 0. Describe how you would implement this idea to implement a fully functional topological sort. Write the pseudo-code of the algorithm. Please make sure the runtime of the algorithm is at least O(V+E).
Gracie is a civil engineer in charge of constructing an underground fiber network in the state of Michisota. Michisota has N cities and M roads and you can always travel from one city to any other city in the state through these M roads. Each one of the M roads connects two town and has a distance marked for each road. The cost of network construction is directly proportional to the total length of the wires laid down under the road. Gracie has to figure out a unique scheme to connect all cities and lay out the fiber with the least possible cost.
Given the list of towns T and roads R connecting them along with their distances D, write an algorithm to design an efficient network construction construction scheme for Gracie that minimizes the overall construction cost.
While designing a robust cellular network, Alice was worried that a single point of failure may completely break the network. A single point of failure is defined as a node in the network graph, which if removed (along with its edges), will cause the number of connected components in the graph to increase. Let us see this with an example:
The graph below is a single connected component. If you remove node 2and edges (2-1, 2-3, 2-4), the resulting graph will still be a single connected component. However, if you remove node 1 and edges (1-0, 1-2, 1-3), you will have two connected components: one with nodes (0,5) and other with nodes (2,3,4). Hence node 1 is a single point of failure.
Write an algorithm to find out all nodes that are a single point of failure in a given graph, as there can be more than one. In the example below, these nodes are: 0 & 1.
Figure: see image.