检测给定图形是否在日志空间中是树

Question

这是我检查给定图形是否是树(BFS)的代码。问题是当我使用堆栈S时，它不会在 logSpace 中。在浏览一些参考时，我认为我必须用一些计数器替换堆栈 S，但是如何？有没有办法修改这个算法以在日志空间中运行？

boolean isTree(G){
Given: G=(V,E)
pick first node s
mark s as visited
S is empty stack << (Problem-I)
S.push(v)
while( S is not empty)
v = S.pop()
for all neighbors W of v in G
//check if marked as already visited
if(W is not parent of v && W is visited)
return 0
else 
mark W as a visited
S.push(W)
end for
end while
return true
}

Answer 1

您没有考虑visited标志的空间，所以我假设您正在使用一些具有位屏蔽属性的数据结构，例如BitSet用于visited。

堆栈将在任何时候占用O(logn)空间，其中n只有当树是平衡的节点总数时(树的最大高度不会超过logn个节点)。在最坏的情况下，当树是平的(只在左边生长或只在右边生长)时，空间复杂度将O(n)。因此，除非树确定是平衡的树，否则无法保证对数空间。

此外，您假设给定的图形已连接。但是，如果给定的图形没有连接，这可能会变成森林(许多树)。因此，您需要检查每个节点而不是pick first node s，如果在第一轮后发现任何节点未访问，则这不是树，而是森林/非树图。

希望对您有所帮助！

编辑

有没有办法在不使用堆栈的情况下跟踪节点？

如果没有堆栈，要么你需要做递归/DFS，在函数堆栈中最坏的情况下会占用O(n)空间，要么你可以使用队列/BFS，它会再次占用O(n)空间。所以不，当树是任意的(不保证平衡)时，你至少需要O(n)空间。

您可以在此处检查 Java 和/或C++中的实现。