c++ - Minimizing memory usage of a breadth first search -

in following code, traversing graph through breadth first search. code constructs graph while traversing. large graph, fan out of 12. due this, time depth of breadth first search increases, want destruct layer above in attempt minimize memory usage. how design algorithm so?

string node::bfs(node * rootnode) { qqueue<cube *> q; q.enqueue(rootnode);  while (!(q.empty())) {     node * currnode = q.dequeue();     currnode->constructchildren();     foreach (node * child, currnode->getlistofchildren()) {         q.enqueue(child);     }     if (currnode->isgoalnode()) {         return currnode->path;     } } 

with constant fanout , assuming tree-like graph, number of nodes have been visited bfs same number of nodes on fringe. (e.g. in tree fanout k, each level n has k^n nodes, , number of nodes lower depth n theta(k^n)).

hence, storing fringe take alot of memory. if memory big problem, "equivalent" technique such iterative deepening dfs may better.

but if want destroy "visited" nodes, way of tracking has been visited (in case of general graph; if is tree there's no problem) needs devised. in case more information on graph needed.

edit on why iterative deepening dfs better.

the fringe (unvisited nodes adjacent visited nodes) in bfs o(k^n) in size, n being current depth. fringe dfs o(n) in size.

iterative deepening dfs has same fringe size dfs, , gives same result bfs, because "simulates" bfs.