A data structure consisting of a large number of nodes connected to each
other in the form of a graph, is to be searched.
• There is one special node called the root (this is slightly unusual for
graphs), and all searches start at the root.
Each node has a unique label, which acts as its name.
Each node is connected to no more than ten other nodes.
There is at least one path from the root to every other node.
So we might have
•
•
.
struct node
{ string label;
node pointer [10]; // from [0] to [nump-1] are all valid node pointers
int nump;
// all other positions are uninitialised.
node * root;
Write the code necessary to find the length of the shortest path from the root
to any other node.
• You should provide a function which takes two parameters, root and the
label of the node to be searched for, and returns an int.
•
The return value is the length of the shortest path from the root to that
node, or -1 if the node can not be found.
•
The length of a path is simply the number of pointers that have to be
followed, so this is a simple breadth-first search.
• If you need a stack or queue, you must implement it.
Fig: 1