在圖的任意兩個頂點之間存在循環

Question

找到有向圖的兩個特定頂點之間的路徑數量，如果它們之間存在一個循環，那麼路徑的數量是無限的，所以我知道算法在整個圖中找到循環，但不是任何兩個特定的頂點，所以如果有人解釋它，這對我會有幫助。

Answer 1

所以，我們可以把這個問題分成兩個子部分。
如果在U（來源）和V（目的地）之間有一個循環，那麼答案將是無限的。因此，在一個DFS中，我們將從U開始，直到我們得到V。同樣從V開始，直到我們得到U.如果我們從兩種方式得到兩個方面，那麼期望的答案是無限的。

現在的主要部分。從源U運行一個正常的DFS，並開始訪問每個節點爲真，如果遇到V的目標節點不標記爲真，然後從那裏繼續。 （這個過程之間的週期很容易被檢測到）。