cycle-detection

3熱度

3回答

最近我參加了一個採訪，並討論了以下我無法弄清楚的問題。問題-1：按照我讀龜移動1步和野兔移動2步在時刻證明。我明白這一點，他們會在兔子以兩倍於烏龜的速度移動之後的某個時候見面。他們不能有任何像2和3或3和5或2和4這樣的隨機值。如果是這樣，他們是否會知道這個循環？選擇龜和野兔值的條件是什麼？我們可以選擇任何隨機值嗎？問題2：是否有烏龜和野兔進入循環的情況？假設如果烏龜和兔子有以下值說2和

2熱度

2回答

鄰接鏈接列表週期檢測 - Java

我有一些問題，檢查我的鄰接列表是否有周期。我想做一個函數，檢查我的鄰接表是否有至少存在一個循環。基於我的程序。首先，我必須輸入根節點，然後輸入許多節點，圖中的節點，邊的數量以及表示邊的邊的鄰接表。鄰接列表中的每個條目都包含一對節點。樣品輸入： Root node: "A" Number of nodes: 3 Vertices/Nodes: A B C Number of edg

0熱度

1回答

在有向圖中找出一個循環中的所有頂點

我有一個有向圖，例如n×n階矩陣。我需要找到其中存在的所有循環以及循環中涉及的頂點。下面是一個例子： A B C D 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 輸出應該類似於： No.of cycles found : 4 A->B->A A->B->C->A A->C->A A->D->A

0熱度

1回答

爲什麼Floyd的循環尋找算法在某些指針增量速度下失敗？

考慮以下鏈表： 1->2->3->4->5->6->7->8->9->4->...->9->4..... 上面所列內容具有循環如下： [4->5->6->7->8->9->4] 繪製在白板上的鏈表，我試圖手動解決它對於不同的指針的步驟，以看到指針如何走動 - (slow_pointer_increment, fast_pointer_increment) 所以，differen指針噸情況如

-1熱度

2回答

我們可以將兩個節點的地址分配爲C＃中一個LinkedListNode的下一個節點嗎？

我正在解決C＃中鏈接列表數據結構中的一個程序，我需要檢查給定的鏈接列表是NULL終止還是循環結束。我想檢查它與不同的測試用例，但無法將循環鏈表作爲輸入。如何傳遞循環鏈表作爲輸入？ Problem from hackerrank會給你一個想法，我試圖實現什麼？這裏是我的代碼來實現鏈表中image private static LinkedList<int> InitializeLinkedLi

1熱度

1回答

如何實驗性地模擬和比較各種圖形週期檢測算法？

我研究了增量式搜索，強連通組件，BFS，雙向搜索等有向圖中的循環檢測算法的各種算法。現在我想模擬它並比較性能。每當我插入一個邊時，我都會調用循環檢測函數。所以，我的問題是我應該考慮什麼樣的數據集。如果我考慮隨機圖，那麼評估各種算法的標準應該是什麼。一些隨機圖可能是巨大的;但他們可能導致循環進行幾次迭代。如果有人能夠提出如何解決這個問題，這將會很有幫助。此外，爲了比較性能，是否有意義刪除循環，然

1熱度

2回答

BFS循環檢測

有人可以通過使用BFS在有向/無向圖中搜索循環來提供逐步僞代碼嗎？它能得到O（| V | + | E |）的複雜性嗎？到目前爲止，我只看到過DFS的實現。