對於圖中的每個頂點，找出距離內的所有頂點d

在我的具體情況下，圖表表示爲鄰接列表，並且是無向和稀疏的，n可以是數百萬，d是3.計算A^d（其中A是鄰接矩陣）並挑選出非零的條目，但我希望不涉及矩陣乘法的東西。在每個頂點上進行廣度優先搜索也是一種選擇，但速度很慢。對於圖中的每個頂點，找出距離內的所有頂點d

來源

2011-04-16 Robert D

在圖表執導？ – 2011-04-16 08:50:13

閱讀第一句 – 2011-04-16 10:20:35

由於圖表表示爲鄰接表，因此深度優先搜索（最多d = 3）應該可以工作，您不需要在每個頂點上工作，而只需要頂點可訪問 – Wei 2011-04-16 14:14:55

假設我們有一個函數verticesWithin(d,x)，它可以找到頂點x的距離d內的所有頂點。

對於像這樣的問題，揭示緩存/記憶機會的一個好策略是提出這樣一個問題：這個問題的子問題如何相互關聯？

在這種情況下，我們可以看到，如果verticesWithin(d,x)是d >= 1的vertices(d-1,y[i])的聯盟範圍內的所有i，其中y=verticesWithin(1,x)。如果d == 0那麼它只是{x}。（我假設一個頂點被認爲距離它自己的距離爲0）。

實際上，你會想看看案例d == 1的鄰接列表，而不是使用該關係來避免無限循環。您還需要避免考慮將x本身作爲y的成員。

此外，如果的verticesWithin(d,x)返回類型是從簡單的列表改變或設置，以代表從x的距離增加d集的列表，然後

verticesWithin(d,x) = init(verticesWithin(d+1,x))

其中init是函數，產率列表中除最後一個之外的所有元素。顯然這是一個非終止遞歸關係，如果字面轉換成代碼，所以你必須對你如何實現它有點聰明。

配備了這些子問題之間的關係，我們現在可以緩存verticesWithin的結果，並使用這些緩存的結果來避免執行冗餘遍歷（儘管需要執行一些設置操作的代價 - 我不完全確定這是一場勝利）。我將把它作爲練習來填寫實現細節。

來源

2011-04-16 09:12:15

您已經提到計算A^d的選項，但這比您需要的多得多（正如您已經說過的）。

然而，使用這個想法有一個更便宜的方法。假設你有一個（列）矢量v零和1，表示一組頂點。現在，矢量w := A v在每個節點上都有一個節點，可以在一個步驟中從起始節點到達該節點。迭代，u := A w有一個爲每個節點可以從起始節點正好有兩個步驟達到，等等

對於d=3，你可以做以下（MATLAB僞代碼）：

v = j'th unit vector 
w = v 
for i = (1:d) 
    v = A*v 
    w = w + v 
end

的矢量w現在對於每個節點具有肯定條目，可以從最多d步驟中的j節點訪問該節點。

來源

2011-04-19 11:25:41 Martijn

我不明白這比矩陣乘法更便宜（時間方面），因爲此過程必須是對於一個單獨的起始頂點，廣度優先搜索是一個更好的選擇，也不需要你的向量'w'。'A^d * v'（反覆計算或其他）零元素作爲'w' – 2011-04-19 22:48:57

你說得對，我以爲你想從一個頂點開始，但是，請不要在這種方法中沒有矩陣矩陣產品，只有矩陣向量產品（它比計算）。 – Martijn 2011-04-20 06:16:49

在這種情況下，從給定頂點開始的寬度第一次搜索是最佳解決方案。你會發現距離d內的所有頂點，而且你甚至不會訪問距離> = d + 2的任何頂點。

這裏是遞歸代碼，儘管如果需要的話，遞歸可以很容易地完成一個隊列。

// Returns a Set 
Set<Node> getNodesWithinDist(Node x, int d) 
{ 
    Set<Node> s = new HashSet<Node>(); // our return value 
    if (d == 0) { 
    s.add(x); 
    } else { 
    for (Node y: adjList(x)) { 
     s.addAll(getNodesWithinDist(y,d-1); 
    } 
    } 
    return s; 
}

來源

2011-04-19 11:56:57 Josh

這是1個起始頂點的最佳解決方案，但問題在於爲每個頂點執行此操作。 – 2011-04-19 20:14:53

@ Robert D.是的，你是對的。我錯過了 - 我的不好！ – Josh 2011-04-19 21:28:58

def find_d(graph, start, st, d=0): 

    if d == 0: 
     st.add(start) 
    else: 
     st.add(start) 
     for edge in graph[start]: 
      find_d(graph, edge, st, d-1) 

    return st 

graph = { 1 : [2, 3], 
     2 : [1, 4, 5, 6], 
     3 : [1, 4], 
     4 : [2, 3, 5], 
     5 : [2, 4, 6], 
     6 : [2, 5] 
    } 

print find_d(graph, 1, set(), 2)

來源

2013-10-11 18:05:53 cybertextron

對於圖中的每個頂點，找出距離內的所有頂點d

回答

相關問題