I'm trying to determine the maximum memory consumption of the data structure (pending nodes) (stack / queue) for both trips: BFS and DFS (in pre-order).

Since moving BFS and DFS have node discovery control (no loops), we can analyze the problem by thinking in terms of trees instead of graphs, your starting node being taken as root, as habit.

I began by assuming that the resulting displacement is a complete tree (all leaves have the same depth), with a height $ h $, $ n $ nodes, and thus all nodes having a degree $ d $ (except the leaves).

Of course, since the tree is complete, $ n $ can be calculated from $ h $ and $ d $:

$$ n = frac {1 – d ^ {h + 1}} {1 – d} $$

Under this assumption, the worst case scenario for DFS is when you are in the deepest non-leaf node of the first branch of the tree: every time you eject a node, you insert all of its children, for each level, you have $ D – $ 1 knots waiting in the stack except in the last non-leaf element where all his children are inserted.

If you, instead of being in the first limb, were in another, you would have a limb with less than $ d – $ 1 children waiting in the stack and so you have fewer nodes in the stack.

The maximum memory consumption of DFS for a complete graph with homogeneus degree is therefore ($ ms $ represent `maximum space`

):

$$ ms = h * (d – 1) + 1 $$

This last `+ 1`

represents the extra child for the last non-leaf node. For example, for a tree with $ d = $ 4 and $ h = $ 20 nodes, a DFS stack would require at most:

$$ ms_ {DFS} = 20 * 3 + 1 = 81 nodes $$

Given the fact that this graph would have $ n = 1.4660155e ^ {12} $ nodes, this is an amount more than eligible. This is the adventure of logarithmic spatial complexity ($ h = lfloor log_d ((d-1) n) rfloor $).

However, for BFS, which has exponential space complexity, the worst case is when all the leaves are waiting for discovery, while all other nodes have been discovered, so your queue contains all leaves. discovered but nothing else):

$$ ms_ {BFS} = d h nodes $$

which, in our example, is equal to 1.0995116e ^ {12} $.

My problem now is to loosen the restriction of the graph to be complete, so $ d $ is no longer a homogeneous degree, but a medium degree (which may now contain decimals), and the tree may exhibit an imbalance, even in the form of a list. As a result, the number of nodes is free, so it is not related to `d`

and `h`

like before.

Yes $ d $ is a medium degree and $ n $ whatever the number of nodes, I have tried to somehow model an upper limit of space consumption by first modeling a complete tree with a homogeneous $ lfloor d rfloor $ degree and then adding the kids to the last sheet until that $ d $ (I guess the resulting number of nodes must be equal to $ n $but I'm not sure either; I even tried to calculate, given some $ d $ and $ n $, a lower and upper limit for the height of the tree).

Since $ d $ is an average, if a node has more than $ d $ kids is because another node has less of $ d $ children and the idea was to find the worst case scenario for DFS and BFS by removing the children from one node and moving the cut branch as a child from another node or, in general, looking for the upper bound as close as possible to memory consumption, but I could not find a way.

The fact is, if you apply this pitch increase repeatedly by moving the sibling branches to the deepest levels, you will probably get many parent or sister paths, consisting of only lists, that would be quickly removed from the stack. of the queue, and so there must be a state of the tree where you can not make the consumption of space worse than that. I suppose, however, that the "worst tree" can be different from DFS and BFS.

Is it possible to perform this calculation of the upper limit (or even the exact amount)? Or is the worst case the one that is balanced?