Use the breadth first strategy to traverse the graph below

List the vertices in the order in which breadth first search traverses them.

- Start from the node \(1\).
- With the choice of two children, visit first the one of higher value.

Consider the above tree. Using breadth first search, we can trace the path \(P\) from any node \(S\) to any other node \(V\). For example the path from \(S=1\) to \(V=15\) is \(\{1,2,15\}\).

Let us define a function \(sP(S,V)\) that returns the sum of the nodes in the path \(P\). So for \(S=1\) and \(V=15\), \(sP(1,15)=sum(\{1,2,15\})=18\).

Find the value of \(\sum_{i=1}^{12} sP(1,v_i)\) where \(v_i\) is the \(i\)th node in the tree and \(v_i \neq 1\).

×

Problem Loading...

Note Loading...

Set Loading...