Description
Write a program to do the following:
(a) Read a description of a graph and create its adjacency list representation. The information at each node consists of a string no longer than 16 characters. Data for the program will be supplied as follows:
• the names of the nodes; each name is a one-word string consisting of letters and/or digits, for example, London. This portion of the data is terminated by the ‘name’ END. The number of nodes is unknown beforehand. The nodes are to be kept in a binary search tree (BST).
• the description of the edges of the graph. The edges emanating from a node are specified by the name of the node, followed by an integer, n, (indicating the number of edges leaving the node), followed by n pairs of values. Each pair consists of a node name (the child) and a positive integer weight (the cost of going from the node to the child). The number of edges is unknown beforehand. Edges from a node must be stored in alphabetical order by node name but they may be given in arbitrary order in the data. However, the names of the nodes are NOT to be stored in the adjacency list; instead, the BST location of the node must be stored. Data is terminated by a node END.
Output the graph, listing the nodes in alphabetical order. Each node is followed by the name and weight of the edges leaving it.
(b) Read the names of two nodes and give the depth-first and breadth-first traversals of the graph from each of these nodes. Print only the names of the nodes.
(c) Read the names of several nodes (one per line) and, for each node, find the minimal cost path to all the other nodes. Data is terminated by END. Use a heap structure to maintain the priority queue. Output the path and the minimal cost to each node. Use 9999 to represent an infinite cost.
Some sample input
England Greece Antigua
Dominica France Canada Belarus
END
France 3 England 25 Greece 45 Belarus 40
Canada 1 Antigua 20
Greece 1 Canada 15
Antigua 0
Dominica 3 France 30 England 20 Belarus 80
Belarus 3 Antigua 50 Canada 15 England 10
England 2 Greece 5 Canada 45
END
Dominica England
Antigua
Dominica
END
Sample output
Antigua
Belarus Antigua 50 Canada 15 England 10
Canada Antigua 20
Dominica Belarus 80 England 20 France 30
England Canada 45 Greece 5
France Belarus 40 England 25 Greece 45
Greece Canada 15
Depth-first: Dominica Belarus Antigua Canada England Greece France
Breadth-first: Dominica Belarus England France Antigua Canada Greece
Depth-first: England Canada Antigua Greece Belarus Dominica France
Breadth-first: England Canada Greece Antigua Belarus Dominica France
Minimal cost path from Antigua:
to Belarus: 9999 path: unreachable
to Canada: 9999 path: unreachable
to Dominica:9999 path: unreachable
to England: 9999 path: unreachable
to France: 9999 path: unreachable
to Greece: 9999 path: unreachable
Minimal cost path from Dominica:
to Antigua: 60 path: Dominica England Greece Canada Antigua
to Belarus: 70 path: Dominica France Belarus
to Canada: 40 path: Dominica England Greece Canada
to England: 20 path: Dominica England
to France: 30 path: Dominica France
to Greece: 25 path: Dominica England Greece
