圖論算法尋找頂點的度數爲0和度數爲（n-1）

我在想如何確定一個有向圖是否有一個get-stuck頂點，它被定義爲頂點，度數n-1和度數0.圖論算法尋找頂點的度數爲0和度數爲（n-1）

我猜啞巴的方式是打印圖中每個頂點的入度和出度，但這是O（m + n）。我對O（n）算法感興趣。有任何想法嗎？

謝謝！

2014-03-31 AmazingVal

你想知道*是否有這樣一個頂點，或者哪些頂點是這樣的？ – Beta

@Beta是否有這樣一個頂點 – AmazingVal

這不就是一個數組散步尋找（僞）count（in）> 1 && out == null？我認爲是0（n）;在比賽早期發現時更快。不是嗎？ – krowe

（我假設n爲頂點，m是邊。）

注意，有在圖表最多一個GET-卡住頂點。

假設我們有一個O（n）算法。如果m很大，我們必須得出結論，而不考慮每條邊。

如果我們得出結論，得到卡住的頂點存在，我們斷言沒有未考慮的邊緣導出它，我們不知道。

因此我不認爲O（n）是可能的。

O（m）非常簡單。

2014-03-31 02:30:05 Beta

我知道這絕對有可能 – AmazingVal

@AmazingVal：你怎麼知道這一點？假設我給出了一個由兩個節點{A，B}和許多邊組成的圖。在給出判決之前，你怎麼能設置一個上限來檢查你要檢查的邊界？ – Beta

我同意Beta，你不可能通過o（n）來解決這個問題，因爲你必須至少訪問一次邊緣來驗證它是一個get-stuck節點。

2017-08-17 22:29:51 Ghasem

回答