**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_{1} //n_{1s} and n_{1d} are the
source node and destination node and w_{1} 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_{11},
n_{12}, n_{13}, ¡¦, n_{1k }// n_{11}
is the root node and n_{11}, n_{12}, n_{13}, ¡¦, n_{1k}
are the child node of n_{11}

n_{21},
n_{22}, n_{23}, ¡¦, n_{2k }// n_{21}
is an internal node and n_{21}, n_{22}, n_{23}, ¡¦, 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