判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 是否有什麼好算法？？ 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 一般來說是使用步長 如一介一次走兩步 一個一次走一步 如果兩個最後重合的話 那麼表示有壞路 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 遍歷。然後做標記，凡是走過的節點就留腳印，如果遇到前面的節點已經有腳印了，就說明有環路。 [code]BOOL 探測環路（當前節點） {     if （此處發現腳印）         return TRUE;     針對每一個後繼： ||                 if （ 探測環路（後繼節點）＝＝TRUE）                   return TRUE;      return FALSE; } [/code] 腳印可以通過置 flag 實現。      返回 TRUE 表示發現環路。 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 標記需要內存 所以如果有向圖很大的話 那麼開銷是很大的 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ --> 很大嗎？真的很大嗎？的確很大嗎？ 既然圖都能表示了，還在乎一個小小的標記？一個標記只需要一個二進制位而已。況且只有遍歷後才能充分確定到底是否有環路。 不要裝做什麼都很專業似的。 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 如果節點數小於邊數+1,則必有回路存在.      看錯了,原來是有向圖. :oops: 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 完全同意「無雙」的算法，這是個很幫的注意！ 只用兩個兩即可判斷 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 無雙的算法沒看明白 能否給講一講，最後重合的這個最後指的是什麼。 一個走一次走一步，一個一次走兩步，那就是要做兩次遍歷了 那時間複雜度上可能不如flw的算法 flw的算法我看是教科書式的算法，這個看的比較清楚 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 無雙的算法把有向圖考慮的太簡單了。 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 無雙的算法是錯的。 他這個算法本來是用來判斷一個鏈表中是否有環路的。不能適用於現在的這個題目。 也就是說：他這個只適合沒有岔路（每個節點只有一個後繼節點）的情形，否則兩個指針可能會走岔。 這個道理其實也很簡單，試想一下：兩個人沿同一條路跑，一個人跑的快，另一個人跑的慢，那麼如果這條路是環形的話，兩個人肯定會相遇；但是如果這條路有分岔呢？如果是網狀的呢？那這兩個人相遇的機會會很小。 再次強烈懇求某些人不要再誤人子弟了！ 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 呵呵，鏈表裡有環路是簡單的有向圖。 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 如果我沒有猜錯的話，無雙這個算法還是去年年底在這個論壇學會的。只不過好像那時候還不是版主吧？難道到現在還沒有消化？而且轉手就變成了「判斷有向圖中有沒有環路」的算法。如此不負責任，看來真的得嚴肅批評一下！ 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 前兩周到亞信面試時學會的:) 另外你的方法需要增加變量 當然循環次數要少於我的方法 只是如果對一些結構已定下來 而且不想因此而改變結構的話 那麼沒法實現 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 如果你覺得別人錯了，指出來我覺得很好，搞技術的沒法含糊。 即使別人是對的，如果你覺得錯了，指出來我覺得也很好，搞技術的經常會和 別人爭論。 但是誤人子弟、嚴肅批評這樣的話就不必了吧，給人文革的感覺。 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 撇開flw說話的方式不談，他的意見我同意。因為在這樣一個罈子裡，越是高手越應該小心謹慎，因為你的不小心，對其它人而言可能就是災難。誤人子弟的事兒這裡也有不少，例子我就不舉了。技術論壇，應該比別的論壇注意些，沒有準確求證的結論要緩下，至少不能絕對化。 有很多帖子都沒有最後結論，甚至於有爭議的帖子不見了。這些都不是技術論壇該有的事情。誰也說服不了誰的，就應該實踐出真知；沒有確定答案的，就要列出盡可能多的答案，剖析原因，共同進步。 費話多了。 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ 呵呵，這是flw老大一向的風格，相信無雙老大也不會介意的。 判斷一個有向圖中是否存在一個閉合環路（如A->B->A）？ :D 無雙早已經不是第一次了 早就摸清了flw老大的「真面目」，相信不會生氣的。 其實圖這個東西，在設計他的時候就要考慮到後來的應用都有些什麼，以確定用什麼存儲方式。 因為不同的存儲方式對於不同的應用的實現差異太大了。 比如你在一個矩陣表示的圖上做遍歷顯然沒有在用十字連表表示的圖上做遍歷來的方便。 這是其一，其二，在應用中設計結構的時候一般總要留一些備用的字段吧。 所以我不同意無雙所說的結構已經定下來無法實現的情況。 即便是有這種情況，也是有辦法實現的，自己一邊遍歷一邊做一個與原始圖一樣的圖，結點只有標記就好了，空間複雜度上稍微差一點。時間複雜度上是一樣的。 無雙的算法偶還是沒想明白。:( [ 關閉窗口 ]