Space 图中 DFS 和 BFS 的复杂度
Space Complexity of DFS and BFS in graph
我试图了解图中 DFS 和 BFS 的 space 复杂性。
我知道使用邻接矩阵时 BFS 的 space 复杂度为 O(v^2)
,其中 v
是顶点数。
通过使用邻接表 space,在一般情况下会降低复杂性,即 < v^2
。但在最坏的情况下,它会是 O(v^2)
。
即使包括 Queue,也是 O(n^2)
(忽略较低的值)
但是,DFS 的场景是什么?
即使我们使用邻接matrix/list。 Space 复杂度为 O(v^2)。但这似乎是一个非常宽松的界限,在不考虑堆栈框架的情况下也是如此。
关于复杂性,我是否正确?
如果不是,BFS/DFS 的 space 复杂度是多少?
在计算 DFS 的 Space 复杂度时,我们是否考虑堆栈框架?
图的 BFS 和 DFS 的 space 复杂度的紧界是什么
如伪代码1所示,space邻接矩阵或邻接表的消耗不在BFS算法中。邻接矩阵或邻接表是BFS算法的输入,因此不能计算space复杂度。 DFS也是。
伪代码1
输入:一个图 Graph 和 Graph
的起始顶点根
输出:目标状态。父链接追踪最短路径回到根
procedure BFS(G,start_v):
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty
v = Q.dequeue()
if v is the goal:
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered:
label w as discovered
w.parent = v
Q.enqueue(w)
BFS的space复杂度可以表示为O(|V|),其中|V|是顶点集的基数。在最坏的情况下,您需要将所有顶点保留在队列中。
DFS 的 space 复杂性取决于实现。具有最坏情况 space 复杂度 O(|E|) 的 DFS 的非递归实现如下所示,其中 E 是边集的基数:
procedure DFS-iterative(G,v):
let S be a stack
S.push(v)
while S is not empty
v = S.pop()
if v is not labeled as discovered:
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
广度优先搜索完成,深度优先搜索未完成。
我试图了解图中 DFS 和 BFS 的 space 复杂性。
我知道使用邻接矩阵时 BFS 的 space 复杂度为 O(v^2)
,其中 v
是顶点数。
通过使用邻接表 space,在一般情况下会降低复杂性,即 < v^2
。但在最坏的情况下,它会是 O(v^2)
。
即使包括 Queue,也是 O(n^2)
(忽略较低的值)
但是,DFS 的场景是什么? 即使我们使用邻接matrix/list。 Space 复杂度为 O(v^2)。但这似乎是一个非常宽松的界限,在不考虑堆栈框架的情况下也是如此。
关于复杂性,我是否正确? 如果不是,BFS/DFS 的 space 复杂度是多少? 在计算 DFS 的 Space 复杂度时,我们是否考虑堆栈框架?
图的 BFS 和 DFS 的 space 复杂度的紧界是什么
如伪代码1所示,space邻接矩阵或邻接表的消耗不在BFS算法中。邻接矩阵或邻接表是BFS算法的输入,因此不能计算space复杂度。 DFS也是。
伪代码1 输入:一个图 Graph 和 Graph
的起始顶点根输出:目标状态。父链接追踪最短路径回到根
procedure BFS(G,start_v):
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty
v = Q.dequeue()
if v is the goal:
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered:
label w as discovered
w.parent = v
Q.enqueue(w)
BFS的space复杂度可以表示为O(|V|),其中|V|是顶点集的基数。在最坏的情况下,您需要将所有顶点保留在队列中。
DFS 的 space 复杂性取决于实现。具有最坏情况 space 复杂度 O(|E|) 的 DFS 的非递归实现如下所示,其中 E 是边集的基数:
procedure DFS-iterative(G,v):
let S be a stack
S.push(v)
while S is not empty
v = S.pop()
if v is not labeled as discovered:
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
广度优先搜索完成,深度优先搜索未完成。