找出环的算法

① c语言，有向图里如何检测是否有环

1、为其定义一个名称，就叫【StackEmpty】。

② 【链表】若单链表存在环，如何找到环的入口点。

s = x + y 2s = nr + s（假设环的周长为r，在相遇前快指针走了n圈） 由公式2推导出s = nr，带入公式1得到nr = x + y === x = nr -y； 现在再设两个指针p1、p2，步长均为1，p1从单链表起点开始遍历，p2从相遇点开始遍历（相遇点可以得到），根据公式x=nr-y，当p1移动x步时（移动到了入口处），p2移动了nr-y步，由于p2是从相遇点开始遍历的，故nr表示又回到了相遇点，-y表示倒退y步（表示入口点到相遇点的距离），由此可以得到p1和p2是同时到达入口点的。 故算法可以写为：

③ 判断一个图是否有负环以及找出负环

盾构始发时，在始发竖井里盾构机的后端是一个反力架，盾构机向前推进时需拼装管片环并向后安装到位以给盾构机掘进提供反作用力，那么从反力架到始发竖井井壁之间安装的管片就是负环管片，负环管片段实际上全部在始发竖井中。

随着隧洞掘进的不断加深，负环管片已经完成了其使命。拆除负环管片是为下一步下放后配套台车提供井下施工空间。

④ 设计一算法判断其是否有环

对于无向图，使用DFS进行遍历，如果有环，从某点出发，一定使用DFS一定可以回到起点。
对于有向图，还可以使用topological sort，如果不能完成拓扑排序，则说明有环。

⑤ 无向图中查找环的算法有哪些

比较直观的办法是，从初始结点 S 开始，用深度优先的方法遍历图的结点，如果在这个过程中，你遇到了一个先前就已经发现过的结点（假定它叫 V），说明存在一个环。
如果你想输出这个环，那么就从 V 沿路返回，直到又遇到 V，途中经过的所有结点就组成了这个环。

⑥ 无向图中找所有环（最好有程序PASCAL)

如果要输出所有解得用DFS搜索（递归实现）
算法大致如下：

1、搜索以x[1]开头的，标记x[1]访问，
2、递归处理x[2]
3、停止条件，碰到访问过的就输出一组解然后跳出

procere dfs(dep:longint);
var i:longint;
begin
if dep=n then exit;
for i:=1 to n do
if v[i] then
begin
for i:=1 to dep do write(x[i]); writeln;
end;
else
begin
x[dep+1]:=i;
dfs(dep+1);
x[dep+1]:=0;
end;
end;
begin
读入图；
dfs(0);
end.

时间复杂度O（n!)

有问题qq 343182185

⑦ C中怎么判断链表中是否有环

用两个指针来遍历这个单向链表，第一个指针p1，每次走一步；

第二个指针p2，每次走两步；
当p2 指针追上p1的时候，就表明链表当中有环路了。
A.判断链表是否有环
设置两个指针p1和p2,初始值均指向链表头,p1每次向前走一步,而p2每次向前走两步。
如果链表有环,则p2先进入环里,而p1后进入环里,两个指针在环中必定相遇。
如果p1与p2没有相遇,p2遍历到链表的尾部,则表示链表没有环。

B.链表有环,确定环的入口点
设置p1指针指向链表头,p2指向相遇点,每次两个指针都是只走一步,两个指针必定相遇,
则相遇第一点为环入口点。

C.计算环长
在环的入口点设置一个指针和一个计数器,让这个指针在环里面走,每走一步,计数器就加1,
当这个指针回到环的入口点的时候,计数器的值就是环长。
例如：
int testLinkRing(Link *head)
{
Link *t1=head,*t2=head;while( t1->next && t2->next)
{
t1 = t1->next;if (NULL == (t2 = t2->next->next))return 0; // 无环 if (t1 == t2)return 1;
}
return 0;
}

⑧ c++判断有向图是否有环的算法

通常是用邻接矩阵来表示一个有向图。从图中的每一个点出发，用深度优先遍历的算法，如果能够回到出发点，图中就是有环的；如果每一个点都不能回到出发点，那么它就是无环的。

⑨ 判断单链表有没有环的算法中，至少需要几个指针

算法的思想是设定两个指针p,
q，其中p每次向前移动一步，q每次向前移动两步。那么如果单链表存在环，则p和q相遇；否则q将首先遇到null。
这里主要理解一个问题，就是为什么当单链表存在环时，p和q一定会相遇呢？
假定单链表的长度为n，并且该单链表是环状的，那么第i次迭代时，p指向元素i
mod
n，q指向2i
mod
n。因此当i≡2i(mod
n)时，p与q相遇。而i≡2i(mod
n)
=>
(2i
-
i)
mod
n
=
0
=>
i
mod
n
=
0
=>
当i=n时，p与q相遇。这里一个简单的理解是，p和q同时在操场跑步，其中q的速度是p的两倍，当他们两个同时出发时，p跑一圈到达起点，而q此时也刚
好跑完两圈到达起点。
那么当p与q起点不同呢？假定第i次迭代时p指向元素i
mod
n，q指向k+2i
mod
n，其中0<k<n。那么i≡(2i+k)(mod
n)
=>
(i+k)
mod
n
=
0
=>
当i=n-k时，p与q相遇。
解决方案：
推广：
1.
如果两个指针的速度不一样，比如p，q，(
0<p<q)二者满足什么样的关系，可以使得两者肯定交与一个节点？

Sp(i)
=
pi

Sq(i)
=
k
+
qi

如果两个要相交于一个节点，则
Sp(i)
=
Sq(i)
=>
(pi)
mod
n
=
(
k+
qi
)
mod
n
=>[
(q
-p)i
+
k
]
mod
n
=0

=>
(q-p)i
+
k
=
Nn
[N
为自然数]

=>
i
=
(Nn
-k)
/(p-q)

i取自然数，则当
p，q满足上面等式
即
存在一个自然数N，可以满足Nn
-k
是
p
-
q
的倍数时，保证两者相交。

特例：如果q
是p
的步长的两倍，都从同一个起点开始，即
q
=
2p
,
k
=0,
那么等式变为：
Nn=i：
即可以理解为，当第i次迭代时，i是圈的整数倍时，两者都可以交，交点就是为起点。
2.如何判断单链表的环的长度？

这个比较简单，知道q
已经进入到环里，保存该位置。然后由该位置遍历，当再次碰到该q
位置即可，所迭代的次数就是环的长度。
3.
如何找到链表中第一个在环里的节点？

假设链表长度是L，前半部分长度为k-1，那么第一个再环里的节点是k，环的长度是
n，
那么当q=2p时，
什么时候第一次相交呢？当q指针走到第k个节点时，q指针已经在环的第
k
mod
n
的位置。即p和q
相差k个元素，从不同的起点开始，则相交的位置为
n-k
从图上可以明显看到，当p从交点的位置（n-k)
,向前遍历k个节点就到到达环的第一个几点，节点k.
算法就很简单：
一个指针从p和q
中的第一次相交的位置起（n-k)，另外一个指针从链表头开始遍历，其交点就是链表中第一个在环里的交点。
4.
如果判断两个单链表有交？第一个交点在哪里？

这个问题画出图，就可以很容易转化为前面的题目。

将其中一个链表中的尾节点与头节点联系起来，则很容发现问题转化为问题3，求有环的链表的第一个在环里的节点。