t*****k
发帖数: 390 | 1 For a undirected graph, how can we detect whether there is a cycle using
minimum space? We do not care how much time it will take and the graph is
stored in the form of adjacent lists.
THANKS!! |
g*****g
发帖数: 34805 | 2 classical jump one jump two until match or end.
【在 t*****k 的大作中提到】
: For a undirected graph, how can we detect whether there is a cycle using
: minimum space? We do not care how much time it will take and the graph is
: stored in the form of adjacent lists.
: THANKS!!
|
t****t
发帖数: 6806 | 3 图,不是链表
定义一下cycle先?
a->b->d
a->c->d
算不算cycle?
【在 g*****g 的大作中提到】
: classical jump one jump two until match or end.
|
g*****g
发帖数: 34805 | 4 oh, sorry, 没注意看。他说的是无向图，环的定义是很明确的。
我觉得数边和顶点就够了。
对于每个连通图，如果边>=顶点，就有环。
问题大致等于图遍历如何使用空间最少。
我能想到的是DFS，标记所有度大于2的点。
【在 t****t 的大作中提到】
: 图,不是链表
: 定义一下cycle先?
: a->b->d
: a->c->d
: 算不算cycle?
|
t****t
发帖数: 6806 | 5 哦,无向图啊,看错了
【在 g*****g 的大作中提到】
: oh, sorry, 没注意看。他说的是无向图，环的定义是很明确的。
: 我觉得数边和顶点就够了。
: 对于每个连通图，如果边>=顶点，就有环。
: 问题大致等于图遍历如何使用空间最少。
: 我能想到的是DFS，标记所有度大于2的点。
|
t****t
发帖数: 6806 | 6 首先要看是不是连通的...
【在 g*****g 的大作中提到】
: oh, sorry, 没注意看。他说的是无向图，环的定义是很明确的。
: 我觉得数边和顶点就够了。
: 对于每个连通图，如果边>=顶点，就有环。
: 问题大致等于图遍历如何使用空间最少。
: 我能想到的是DFS，标记所有度大于2的点。
|
k*k
发帖数: 508 | 7 那 goodbug 的说法得改成，如果边的个数大于等于非零度的顶点个数
【在 t****t 的大作中提到】
: 首先要看是不是连通的...
|
t****t
发帖数: 6806 | 8 不对,非连通的图不一定有0度的顶点
要看有几个非连通的部分...
【在 k*k 的大作中提到】
: 那 goodbug 的说法得改成，如果边的个数大于等于非零度的顶点个数
|
|
k*k
发帖数: 508 | 9 就算是有几个部分非连通，如果边数大于非零度顶点数，也一定
会有环的吧。
【在 t****t 的大作中提到】
: 不对,非连通的图不一定有0度的顶点
: 要看有几个非连通的部分...
|
t****t
发帖数: 6806 | 10 当然,不过就不是充要条件了
【在 k*k 的大作中提到】
: 就算是有几个部分非连通，如果边数大于非零度顶点数，也一定
: 会有环的吧。
|
|
|
k*k
发帖数: 508 | 11 充分条件就够了啊，人家就想知道有没有环
【在 t****t 的大作中提到】
: 当然,不过就不是充要条件了
|
t****t
发帖数: 6806 | 12 可是不是必要条件,所以有时有环的会误判成没环
【在 k*k 的大作中提到】
: 充分条件就够了啊，人家就想知道有没有环
|
g*****g
发帖数: 34805 | 13 用链表实现的图根本不会有这样问题。
【在 t****t 的大作中提到】
: 可是不是必要条件,所以有时有环的会误判成没环
|
t****t
发帖数: 6806 | 14 为什么?
【在 g*****g 的大作中提到】
: 用链表实现的图根本不会有这样问题。
|
k*k
发帖数: 508 | 15 sorry，我糊涂了
我觉得这个条件就算是有几个不连通的部分，也还是充要条件
【在 t****t 的大作中提到】
: 可是不是必要条件,所以有时有环的会误判成没环
|
g*****g
发帖数: 34805 | 16 实现无向图的链表，所有连通子图至少要给你一个顶点吧，否则你怎么搜？
如果这些顶点本身是用一个链表连起来，那么就只有一个连通图，没有
这个问题。如果这些顶点是用一个数组给出的，那么对每个数组的元素
做一次检查，确保都有向外的连接即可。注意，如果有一条边连向自己也算环。
如果没有就排除完事。
【在 t****t 的大作中提到】
: 为什么?
|
c*****t
发帖数: 1879 | 17 题目说了，是 adjacency list 。因为有可能有几个分开的图，所以
我觉得得用 O(n) 的空间。但是用 clever engineering 的话，可以
只用 O (1) 。也就是改动这个 adjacency list，变成 direct graph 。
用多出来的空间做其中的步骤。然后解完再将 adjacency list 还原。
【在 g*****g 的大作中提到】
: 实现无向图的链表，所有连通子图至少要给你一个顶点吧，否则你怎么搜？
: 如果这些顶点本身是用一个链表连起来，那么就只有一个连通图，没有
: 这个问题。如果这些顶点是用一个数组给出的，那么对每个数组的元素
: 做一次检查，确保都有向外的连接即可。注意，如果有一条边连向自己也算环。
: 如果没有就排除完事。
|
t****t
发帖数: 6806 | 18 a--b--c--a
d
4个点,三个边,一个环
【在 k*k 的大作中提到】
: sorry，我糊涂了
: 我觉得这个条件就算是有几个不连通的部分，也还是充要条件
|
k*k
发帖数: 508 | 19 零度的点要排除的啊
三个点，三条边
【在 t****t 的大作中提到】
: a--b--c--a
: d
: 4个点,三个边,一个环
|
t****t
发帖数: 6806 | 20 a--b--c--a
d--e
你怎么不开窍呢...
【在 k*k 的大作中提到】
: 零度的点要排除的啊
: 三个点，三条边
|
k*k
发帖数: 508 | 21 开了，开了..
【在 t****t 的大作中提到】
: a--b--c--a
: d--e
: 你怎么不开窍呢...
|
