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

n1s, n1d, w1 //n1s and n1d are the source node and destination node and w1 is the weight

nKs, nKd, wK

---

The output file of the program has to be

---

m // the number of non-leaf node

n11, n12, n13, , n1k // n11 is the root node and n11, n12, n13, , n1k are the child node of n11

n21, n22, n23, , n2k // n21 is an internal node and n21, n22, n23, , n2k are its child nodes of

nm1, nm2, nm3, , nmk  

---

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

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