r******l
发帖数: 10760 | 1 换句话说判断一个图是否是一棵树（或者一个森林，如果图不联通的话）。
这个题是不是可以看做那个著名的判断链表中是否有环的题目的二维扩展？有什么好办
法吗？ |
r*********r
发帖数: 53 | 2 判断图是否有环：
我觉得可以直接用dfs，每一步记录当前访问的node，如果当前访问的node之前被访问
过那么就是有环的。
如果图是有向图，我们还可以用topological sorting 来判断。 |
L********d
发帖数: 3820 | 3 有向图还是无向图？
【在 r******l 的大作中提到】
: 换句话说判断一个图是否是一棵树（或者一个森林，如果图不联通的话）。
: 这个题是不是可以看做那个著名的判断链表中是否有环的题目的二维扩展？有什么好办
: 法吗？
|
r******l
发帖数: 10760 | 4 每步记录的话需要O(n)的空间，基本相当于链表那题的naive解法。有没有可能更好呢？
【在 r*********r 的大作中提到】
: 判断图是否有环：
: 我觉得可以直接用dfs，每一步记录当前访问的node，如果当前访问的node之前被访问
: 过那么就是有环的。
: 如果图是有向图，我们还可以用topological sorting 来判断。
|
r*********r
发帖数: 53 | 5 空间是省不了的吧……
如果是有向图，那么可以用topological sorting, 时间复杂度会低一些，大概是O(V+E
). 但是空间还是省不了。
呢？
【在 r******l 的大作中提到】
: 每步记录的话需要O(n)的空间，基本相当于链表那题的naive解法。有没有可能更好呢？
|
r*g
发帖数: 186 | 6 不可能不记录
因为你不知道是哪个节点重复了
每步记录的话需要O(n)的空间，基本相当于链表那题的naive解法。有没有可能更好呢？
【在 r******l 的大作中提到】
: 每步记录的话需要O(n)的空间，基本相当于链表那题的naive解法。有没有可能更好呢？
|
r******d
发帖数: 308 | 7 图是由node跟edge组成的。 现在需要的是在node里面加一个flag来表示访问过了还是
没有访问到。实在想省空间就把node no.跟这个flag共享同一个变量?呵呵
呢？
【在 r******l 的大作中提到】
: 每步记录的话需要O(n)的空间，基本相当于链表那题的naive解法。有没有可能更好呢？
|
