algorithm - 在 LogSpace 中检测给定图是否为树

Question

这是我用来检查给定图是否为树 (BFS) 的代码。问题是当我使用堆栈 S 时，它不会在 logSpace 中。在浏览一些引用资料时，我想我必须用一些计数器替换堆栈 S，但是怎么做呢？有没有办法修改这个算法以在 LogSpace 中运行？

 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如果在第一轮后发现任何节点未被访问，则这不是树，它是森林/非 TreeMap 。

希望对您有所帮助!

编辑

Is there any way to keep track of nodes without using stack?

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

您可以检查 Java 和/或 C++ 中的实现 here .