在圖中找到一組頂點，使每個頂點可以到達其他k個頂點

Question

設G =（V，E）爲有向圖，k爲整數。我需要在線性時間內找到頂點組，以便該組中的每個頂點可以精確到達k個頂點（包括它自己）。

我想到的第一件事就是使用Kosaraju的算法來查找圖的強連通組件。連接組件內部的每個頂點至少可以有效地到達此連接組件中的頂點，因此剩下的就是看組件是如何連接的。但是，我沒有想出一個線性解決方案。

任何提示？

謝謝。

Answer 1

您的第一步是正確的。每個強連通的組件可以用一個頂點代替，爲此，起始的可到達頂點數是該組件中元素的數量。替代操作後，我們得到有向無環圖。現在，對於每個超級頂點，我們想要找到可以從中達到多少個頂點。一個想法是對拓撲圖進行排序。在此操作之後，所有箭頭指向一個方向。不失一般性，我們可以假設它們指向正確的，所以我們的圖形看起來或多或少是這樣的：

a -> b ----> e -> f -> g 
    \   /
    -> c -> d - 

對於我們有我們從組裝頂點的第一階段得到了一個強烈出發櫃檯每個頂點連接的組件。我們現在想要做的是從右到左，並且每個頂點都有一組可達的頂點。我們需要的操作是這套快速合併。這裏的幫助來自Find-Union數據結構。您可以將一個字段添加到通常的size和rank，這將存儲＃個可到達頂點並將其更新爲union兩組。

這將導致幾乎線性時間：O(n * alpha(n))其中alpha(n)是非常小的阿克曼函數的逆。對於龐大的數據，它不會大於5，所以你可以認爲它是不變的。

我不知道有人能沒有alpha。

Answer 2

我認爲第一個答案是不正確的。你可能能夠從scc圖中其兒子的可重複聯盟中爲每個節點創建可達到的節點組，但是你需要製作兒子組的副本才能做到這一點（否則你會搞砸他們的可反覆使用的東西）。所以複雜度是n * n最小或者實際上n * E如果我沒有錯。這是因爲拷貝需要在聯合操作之前進行*，因此您需要爲每個節點通過n *（數目的兒子）。其複雜度爲n * E + n（alpha（n）） 。完全冗餘，因此使用聯合查找..您可以爲每個節點使用n個大小的陣列。