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.
Given a complete binary tree \(T\) with \(n\) nodes, which of the following best describes the time it takes to find a path using breadth first search from a root \(V\) to another node \(s\) (\(s \in T\))?
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\).