Assignment 4: Tree and Graph

For a given undirected weighted graph, write a program in C++, which first finds the center of the graph and converts it to a BFS tree. The center of the graph is defined as the node that the maximum distance to other node in the graph is minimum such as where is the set of nodes, is the number of nodes, and is the distance of the shortest path from to .

And when you visit the graph by BFS to convert it to a tree, the node with the lowest number is to be visited.

The input of the program (graph.inp) is given as follows;

---

N // the number of nodes, where node label is given from 1 to N

K // the number of edges

n_1s, n_1d, w₁ //n_1s and n_1d are the source node and destination node and w₁ is the weight

…

n_Ks, n_Kd, w_K

---

The output file of the program has to be

---

m // the number of non-leaf node

n₁₁, n₁₂, n₁₃, …, n_1k // n₁₁ is the root node and n₁₁, n₁₂, n₁₃, …, n_1k are the child node of n₁₁

n₂₁, n₂₂, n₂₃, …, n_2k // n₂₁ is an internal node and n₂₁, n₂₂, n₂₃, …, n_2k are its child nodes of

…

n_m1, n_m2, n_m3, …, n_mk

---

This output file contains only non-leaf nodes and NOT the leaf nodes.

Submission: via ESPA
Due date: Dec. 24 4:00 pm