找出環的演算法
① 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，求有環的鏈表的第一個在環里的節點。