Я пытаюсь понять, какова сложность пространства DFS и BFS в графе.
Я понимаю, что сложность пространства BFS при использовании матрицы смежности будет O(v^2), где v - количество вершин.
При использовании пространства списка смежности сложность в среднем уменьшится, т. Е. < v^2. Но в худшем случае это будет O(v^2).
Даже с учетом очереди это будет O(n^2) (без учета нижнего значения)
Но каков сценарий с DFS?
Даже если мы используем матрицу смежности / список. Сложность пространства будет O (v ^ 2). Но это, кажется, очень слабая граница, без учета стековых фреймов.
Я прав относительно сложностей?
Если нет, то каковы пространственные сложности BFS / DFS?
и при расчете сложности пространства для DFS мы рассматриваем кадр стека или нет?
Что такое жесткая граница сложности пространства, для BFS и DFS для графа