Computer Science
# Graph Algorithms

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$.