for example: if i have a root with 30 children and each child has 35 children, how many times will I visit each node in total (including repeats) if I perform a depth first search?
I want to determine every path possible and I know that there are in total 30 * 35 total paths from root to leaf given my problem statement. However, I want to know how costly this is to calculate. So given a depth first search algorithm, how many times would you visit a node to calculate the total number of paths?
ie. imagine
root -> b -> c is 1 path total. and 3 nodes visited
root -> b -> d is 2 paths total and 5 nodes visited (since it backtracked to node b and visited d)
If you count backtracking to a node also as a visit, then you'll visit a leaf only once, but internal nodes are visited a first time and then after that as many times as they have children.
As the root node has 30 children, it will be visited 31 times.
As the 30 children of the root each have 35 children, they each get visited 36 times
Add to this the single visits to each of the leaves, i.e. 30 * 35
In total that gives:
31 + 30 * 36 + 30 * 35 = 2161 visits
Another way to arrive at this number is to realise that each edge represents two node visits: a visit of the connected child, and a (re)visit of the connected parent. The initial visit of the root has to be added to this. So then you just count the number of edges, multiply by 2 and add 1:
1 + (30 + 30 * 35) * 2 = 2161
If we generalise, and the root has 𝑛 children and each child has 𝑚 children -- which are leaves, then we get:
1 + 2(𝑛 + 𝑛𝑚) = 1 + 2𝑛(1+𝑚)