BFS vs DFS graph space complexity

algorithm sorting graph complexity-theory space

413 просмотра

1 ответ

1 Репутация автора

How much memory does a Depth first search and a Breadth first search require in a graph with edges and vertices when the breadth first search includes a queue?

Автор: user3226213 Источник Размещён: 08.11.2017 10:36

Ответы (1)

1 плюс

1514 Репутация автора

The recursive DFS is the most memory taxing as it requires a function call and a stack frame for every node currently processed. With explicit stack and queue data structures there are no big differences in consumed memory. Generally it depends on the shape of the graph and the number of nodes currently on the stack or in the queue. The nodes previously processed or not visited yet do not affect the memory consumed by the algorithm. Yet in some extreme cases (like a star shaped graph) it may happen that you will read in the whole graph. But once again it depends on the structure of the graph.

Автор: jszpilewski Размещён: 09.11.2017 10:17
Вопросы из категории :