使用包含給定節點集的節點數量最少的圖確定包含附加條件的節點圖

Question

我有一個未加權的有向圖，其中可能有也可能沒有循環。現在給定一組節點，我需要返回一個具有給定節點和最少數量節點的圖形，以便它們連接。我無法創造新的邊緣，所以我需要使用現有的邊緣。

希望這些照片說清楚。與圖開始，

比方說，我們希望有節點C，F和G的圖形，該函數將返回該圖

然而，有一個條件。每個邊都有一個名爲required的布爾變量。如果設置爲true，則此邊和相應的節點也需要包含在圖中。

這裏是另一張圖片來說明 黑邊不是必需的，但紅色的是必需的 假設我們給出了一個和c作爲包含的節點。

因此，而不是返回圖是A-> C， 它將返回這個

爲了使點更清楚，如果我們想與B的圖和c，它也會返回該圖，因爲該邊是必需的。

如何才能返回此圖？我不希望有一個循環返回的圖形，但我意識到這並不總是可行的，因爲循環的邊緣可能全部被標記爲需要。

我最初的想法是將圖形的副本保留在所需的邊上，然後試圖將不相交的圖形拼接在一起。但是，在我將所有圖形拼湊在一起的嘗試中，我能夠找到一個反例來表明這不是最小圖。

Answer 1

在第一個例子中，您的預期輸出是否包含節點e，其中所有其他節點都可以到達？或者你的意思是弱連通性（意思是邊的方向無關緊要）？我想第二個是的情況下（從A，B，C例如判斷），然後就可以

1. 只是忽略該邊緣被引導（線性時間），
2. contract的「必需的」邊緣（線性時間），
3. 計算pairwise shortest paths關於所需點的子集（O（| V |³），但我想你可以把它推到O（r | V |²），r是所需點的數量） ，然後
4. 在要求的點上找到一個minimum spanning tree（O（r²））

這就是你想要的嗎？